книги из ГПНТБ / Васильев Ф.П. Лекции по методам решения экстремальных задач

являются параметрами алгоритма. Вектор рп называют статисти­ ческим градиентом. Если U = E m, s — m и векторы ^ я вл я ю тся не­ случайными и совпадают с соответствующими единичными вектора­ ми в {= ( 0 , . . , 0, 1, 0 , . . , 0), £ =1 , 2 , . . , /п, то описанный алгоритм,

как нетрудно видеть, превращается в разностный аналог градиент­ ного метода.

2. В описанных вариантах а), б), в) метода случайного пои ка предполагается, что закон распределения случайного вектора £ не зависит от номера итераций. Такой поиск называют случайным поиском без обучения. Алгоритмы случайного поиска без обучения не обладают «способностью» анализировать результаты предыду­ щих итераций и выделять, направления, более перспективные в смысле убывания минимизируемой функции, и сходятся, вообще го­ воря, медленно.

Между тем ясно, что от метода случайного поиска можно ожи­ дать большей эффективности, если на каждой итерации учитывать накопленный опыт поиска минимума на предыдущих итерациях и перестраивать вероятностные свойства поиска так, чтобы направле­ ния £, более перспективные в смысле убывания функции, станови­ лись более вероятными. Иначе говоря, желательно иметь алгорит­ мы случайного поиска, которые обладают способностью к самообу­ чению и самоусовершенствованию в процессе поиска минимума' в зависимости от конкретных особенностей минимизируемой функ­ ции. Такой поиск называют случайным поиском с обучением [204].

Обучение алгоритма осуществляют посредством целенаправленного изменения закона распределения случайного вектора £ в зависимо­ сти от номера итерации и результатов предыдущих итераций таким образом, чтобы «хорошие» направления, по которым функция убы­ вает, стали более вероятными, а другие направления — менее ве­ роятными. Таким образом, на различных этапах метода случайного поиска с обучением приходится иметь дело с реализациями случай­ ных векторов | с различными законами распределения. Имея в ви­

минимизируемой функции. Если такая информация отсутствует, то поиск обычно начинают от случайного вектора = (|о, ••■, £сГ),

компоненты |о,£= 1, 2 , . . . , пг, которого представляют собой незави­ симые случайные величины, распределенные равномерно на отрез­

§ 12] О методе случайного поиска и некоторые других методах 151

ке [— 1, 1]. Для обучения алгоритма в процессе поиска часто берут

точке « „ _ 1 привел к уменьшению значения функции, то вероятность выбора направления ип- Х— и„_2 на следующем шаге увеличивается. И наоборот, если при переходе от ип- 2 к i значение функции увеличится, то вероятность выбора направления ип- 1— ип- 2 на сле­ дующем шаге уменьшается. Таким образом, формулы (4) осуще­ ствляют обучение алгоритма. Величина 6 ^ 0 в (4) регулирует ско­ рость обучения: чем больше 6 > 0 , тем быстрее обучается алгоритм; при 6 = 0, как видно, обучения нет. Величина в формулах (4) регулирует влияние предыдущих значений параметров на обуче­ ние алгоритма; при |3 = 0 алгоритм «забывает» предыдущие значе­

152 МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [Гл. 2

ния шл_|. Для устранения возможного чрезмерного детерминиро­ вания алгоритма и сохранения способности алгоритма к достаточно'

ci являются параметрами алгоритма.

Вместо формул (4), посредством которых производится обу­

Описанный алгоритм покоординатного обучения имеет тот не­ достаток, что поиск и обучение происходят лишь по одному из 2т направлений £ = (|‘, . . . , £т ), где либо £’ = 1 , либо £* = — 1. Отсутст­ вие «промежуточных» направлений делает покоординатное обуче­ ние немобильным в областях с медленно изменяющимися направ­ лениями спуска. От этого недостатка свободен следующий алго­ ритм.

б) Алгоритм непрерывного самообучения [204]. Пусть имее

чайный вектор, координаты rf которого представляют собой неза­ висимые случайные величины, распределенные равномерно на отрезке [ - U ] . Поиск начинается с рассмотрения случайных векторов £о = £(0), £i = £(0), реализации которых используются при определении приближений u0, ut по формулам (2). Обучение алгоритма при 2 призводится так же, как в алгоритме поко­ ординатного обучения, с помощью формул (4) или (5). При боль­

близким к направлению шп. Во избежание излишней детермини­

Более подробные рассмотрения различных вариантов метода случайного поиска, их сравнительные характеристики, вычисли­ тельные аспекты метода случайного поиска см. в работах [79],. [204].

3. Приведенные алгоритмы случайного поиска с обучение показывают, что процесс обучения в ходе поиска сопровождается уменьшением фактора случайности и увеличением степени детер­ минированности алгоритма поиска минимума, направляя поиск.

возможность алгоритму «переучиваться», если свойства функции в районе поиска изменились или предыдущее обучение было не­ точным. Случайный поиск с обучением в некотором смысле зани­ мает промежуточное положение между случайным поиском без обучения и детерминированными методами поиска минимума из предыдущих параграфов. Разумеется, и в методах предыдущих параграфов можно обнаружить в том или ином виде элементы самообучения алгоритма, однако наличие случайного фактора в алгоритме делает метод случайного поиска более гибким и поэто­ му более приспособленным к поиску минимума многоэкстремаль­ ных функций, т. е. функций со многими глобальными и локальны­ ми минимумами в рассматриваемой области.

Следует сказать, что задача отыскания глобального миниму­ ма многоэкстремальных функций существенно более трудна, и ме­ тоды решения таких задач в настоящее время разработаны недо­ статочно. Для изучения поведения многоэкстремальных функций и

здесь можно предложить метод, обобщающий метод ломаных из главы 1, однако его реализация с возрастанием размерности про­ странства весьма усложняется [85]. Другие методы минимизации многоэкстремальных функций изложены в работах [103, 174, 214].

4.Весьма усложняет решение задачи минимизации функц

многих переменных наличие помех, когда на значения функции J (и) в каждой точке и накладываются случайные ошибки. В этих случаях можно использовать метод стохастической аппроксимации

([45, 79, 230] и др.). Одним из вариантов этого метода является процедура Кифера — Вольфовица, краткое описание которой бы­ ло дано в § 1.12 применительно к задачам минимизации функций одной переменной. Для функций m переменных эта процедура приводит к построению последовательности {«„} по закону

Z О/, + С„е,) — Z (и„ — с„е,)

Un-\-1 —

Сп

i = 1, 2, . . . , m; п = 0, 1, . . . ,

где = ( 0 , . . . , 0, 1, 0 , . . . , 0), z(u) — наблюдаемые в эксперимен­ те значения функции J (и) в точке и, последовательности {а„}, {с„} удовлетворяют условиям (1.12.2). Различные варианты мето­ да стохастической аппроксимации, строгое обоснование этого ме­ тода и различные приложения можно найти в работе [45]. Для минимизации функции при наличии помех могут быть использо­ ваны также метод случайного поиска [204] и некоторые другие методы [ПО, 214].

5.В заключение настоящей главы следует сказать, что в да

ной главе мало или даже совсем ие затронуты важные, но пока, к сожалению, малоизученные вопросы устойчивости изложенных методов по отношению к различным погрешностям вычисления и округления, вопросы накопления, анализа и использования инфор­ мации в процессе счета, критерии точности и окончания счета и другие вопросы, требующие немалого искусства вычислителя при решении задачи минимизации конкретной функции с помощью того или иного метода.

В стороне остались также вопросы, связанные с выбором оп­ тимальных стратегий поиска минимума на определенных классах функций. Следует сказать, что оптимальные стратегии поиска ми­ нимума функций многих переменных зачастую имеют довольно' сложное описание, что затрудняет их практическое использование. Заметим, что задача поиска экстремума функций многих перемен­ ных хорошо укладывается в общую схему исследования операций, разработанную в работе [69]. Это обстоятельство используется

1в работах [215, 216] для построения оптимальных стратегий поис­ ка экстремума на классе функций, удовлетворяющих обобщенному условию Липшица. Обзор оптимальных методов минимизации на различных классах функций см. в работе [120]. Общий обзор

методов минимизации функций конечного числа переменных и биб­

156 П Р И Н Ц И П МАКСИМУМА Л. С. ПОНТРЯГИНА [Гл. ■?

Кроме того, на фазовые траектории также могут быть наложены: некоторые ограничения, вытекающие, например, из условий того,, чтобы вес аппарата был не меньше определенной величины, или1 траектория полета проходила вне определенных областей космиче­

ным ограничениям и, кроме того, некоторый целевой функционал принимал свое минимальное или максимальное значение. Напри­ мер, возможны задачи [75]: 1) попасть в заданную точку или об­ ласть космического пространства за минимальное время; 2) в за ­ данный момент попасть в заданную область пространства с задан­ ной скоростью и с максимальным весом аппарата или с минималь­

дый момент t и называемые фазовыми координатами управляемо­

объекта и учитывающие различные внешние факторы, предполага­

принадлежат некоторой области управлений V(t), которая может быть любым множеством некоторого r-мерного евклидова прост­

Под решением этого уравнения будем понимать непрерывное ре­ шение интегрального уравнения

ловиях может быть доказано существование и единственность ре­

Теперь перейдем к непосредственной формулировке задачи оп­ тимального управления. Пусть в пространстве Е п заданы многооб­ разия S0(t), Si(t) и некоторое множество G (t), и пусть задан функционал

. J ( u ) = jf* ( x ,u ,t ) d t + 0 (x (T )), 1О

где функция /° (х, и, t) определена и непрерывна вместе с частными производными /°у (]' = 1,2, . . . ,п) при (х, u,t)£.G (t) х V (t) X [^0, Т],

Ф (х) — определена и непрерывна при х 6 G (Т) f| S/ (Т ).

Задача оптимального управления заключается в том, чтобы найти такое допустимое управление и = и * (t)^ U , чтобы соответ­ ствующая ему траектории x — x * (t) — x(d,u*) удовлетворяла усло­ виям х* (t0)^ S o (t0), x*(T )e= Si(T ), х* (t)^ G (t), и функ­ ционал J (и) достигал своей точной нижней грани: J (и*) = inf 1(и) —

158 ПРИНЦИП МАКСИМУМА Л. С. ПОНТРЯГИНА [ Гл. 3

= /*; здесь нижняя грань берется по всем u (t)^ U , для которых соот­

•называется задачей оптимального управления без ограничений на

ют задачей оптимального управления с ограничениями на фазовые координаты.

могут быть неизвестны, тогда они зависят от управления и подле­ ж ат определению. В частности, если /°=1, Ф (а) = 0 , т о / ( « ) =

мального управления рассматриваются задачи с запаздыванием, с

ния непрерывное решение уравнения (6) абсолютно непрерывно и почти всюду удовлетворяет уравнению (5). -

§2. ФОРМУЛИРОВКА ПРИНЦИПА МАКСИМУМА Л. С. ПОНТРЯГИНА

где функции gi (х, t) непрерывно-дифференцируемы по (х, t) £ ЕпX [£0, 7]

Сначала рассмотрим случай, когда моменты £0. Т закреплены. ДЛЯ формулировки принципа максимума наряду с системой (1.8) рассмотрим следующую систему линейных дифференциаль­ ных уравнений относительно вспомогательных (дополнительно

вводимых) переменных ф(£) = (Ф1 (£). •••>фп ( 0 ) :