Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 18
Текст из файла (страница 18)
На основе получаемых в процессе поиска оценок параметров можно управлять длиной рабочего шага поиска с целью более точного нахождения экстремума функции качества и сокращения среднего времени поиска экстремума. Если имеется априорная информация о неизвестном параметре Х, то его оценку целесообразно находить по максимуму апостериорной вероятности, которая определяется в каждом рм состоянии объекта по статистике, собираемой в результате измерений прп т случайных пробах. Прн этом в качестве апрнор- 1!О Результаты эксперимента с учетом поправки на смещение дают более приемлемые оценки искомых параметров.
Для сопоставления оценки (4.6.33) с оценкой в линейном поле найден значение соотношения (4.5.33) в случае, если выборка будет использована для линейного поля. Определив математическое ожидание М[г), получим, что ной информации для !'-го состояния объекта можно использовать оценку Хн. „полученную в предыдущем ! — 1-м состоянии. Такой подход к оценке параметров экстремального объекта целесообразен в случае существенной корреляции между соседними состояниями. В [214) показано, что в среднем оценка параметра А по формуле Бейеса сходится к действительному значению оцениваемого параметра. $4.7. стАтистический пОиск с АдлптлциеЙ При экстремальном управлении многомернымп зашумленными объектами и отыскании экстремума функций и-переменных с,наложенными на них случайными возмущениями скорость оптимизации существенно снижается нз-за ошибок в определении вектора градиента н его модуля.
Одним из методов повышения скорости сходимости детерминированных и стохастических методов поиска в задачах с шумами является локальное накопление [2!5 †2], на основе которого удается оценить полезный сигнал -- приращение функции качества — или определить усредненное направление вектора градиента. 11иже предлагается метод оптимизации, в котором используется оценка как направления градиента [МО), так и его модуля, получаемая путем обработки локальной статистики на каждом шаге поиска (4.6.5). Такой алгоритм назовем статистическим поиском с адаптацией.
Рассмотрим подробнее данный алгоритм. Пусть объект описывается одноэкстремальной функцией качества (4.7.1) Я =О(Х,А), где Х= (хь хь...,х„) — и-мерный вектор состояния объекта; Х вЂ” вектор неизвестных параметров объекта, которые должны определятьсн во время поиска. В канале связи на функцию качества накладывается помеха, и в экстремальный регулятор поступает значение функции качества Я'=Я(Х, 1.) +е. (4.7.2) Помеха является стационарным пекоррелированпым случайным процессом с нормальным законом распределения и известными параметрами (О,оз!2).
Рассматриваемый алгоритм поиска состоит в следующем. Из текущего состояния Х! делается щ случайных проб + яЕ! и вычисляются соответствующие приращения функции качества [210! Лд !!!!= д" (Х, +дВл Л) — д*(Х! — дВн л), ! = 1, 2,..., и, (4.7.3) х!„—. х!+лхг+,, д ЛХ, =- — — -' ).„и!, РЧ (4.7.4) (4.7.5) Ъ'! — т-ыер- градиентного где а — масштабный коэффициент рабочего шага; ный вектор, являющийся статистической оценкой направления и, согласно [2!О), у;= Х е!Ла~!(!!.
/-! (4,7.6) Как видно из (4.7.5), длина рабочего шага определяетсялокальиой оценкой модуля градиента функции качества. В данном алгоритме используется оценка, полученная для линейного поля. По своей структуре она проще соответствующей оценки для центрального поля. Выбирая пробный шаг достаточно малым, можно приближенно считать центральное поле линейным в окрестности исследуемой точки и применять алгоритм с линейной оценкой модуля градиента для оптимизации нелинейных функций качества. Данный алгоритм применяется в предположении, что помеха относится к классу нормально распределенных случайных процессов (величин! с нулевым средним значением и известной !!з где л — величина пробного шага в пространстве оптимизируемых параметров; Е;= (с!!!!, с;о!,..., с„!л) — единичный случайный вектор, равномерно распределенный в пространстве оптимизируемых параметров.
При этом Х в (4.7.1) является скаляром. На основе последовательности ЛЯ,"(!), ЛЯ!"!э!,..., ЛЯ,~ыи определяется оценка модуля градиента (4.6.10), являющаяся функцией локальной статистики н числа оптимизируемых параметров. Тогда алгоритм можно представить в виде следующих рекуррептиых выражеш!й: дисперсией. Если дисперсия помехи неизвестна, ее легко оценить на основе многократного замера функции качества в ~'-м и 1+1-м состояниях: л и'=- — ~, (ЛЯ"'Р> — Р4ч )' э=1,2,..., й, (4.7.7) Й-1,=, где й — число замеров функции качества в каждом состоянии; Ло',и1=0 ел(Хгзы) — 1~ в~(Х,); По формуле (4.7.7) оценивается требуемое удвоенное значение дисперсии.
Такую оценку необходимо сделать один раз, при этом й следует выбрать достаточно большим с тем, чтобы получить оценку высокой точности. Рассмотрим два вида статистического поиска. Ранее отмел чалось, что,некоторые оценки Х„<'~ вследствие конечности объема выборки могут оказаться мнимыми. Выборки, приводящие к мнимым оценкам, назовем неудачными.
В алгоритме первого вида неудачная выборка отбрасывается и из того же состояния системы проводится повторная выборка до получения действительной оценки модуля градиента. Алгоритм второго вида характеризуется тем, что при неудачной выборке повторное накопление в данном 1-м состоянии не проводится, а делается рабочий шаг '~/. л ЛХ;+~ — — — а — ' Х„п " Ж! с использованием оценки модуля градиента в предыдущем! — 1-и состоянии.
Данный алгоритм исследован экспериментально путем моделирования поиска на ЭЦВМ БЭСМ-ЗМ. Модель объекта описывается функцией качества 4 Я(х) = ~, аххх'. (4.7.8) Крнгерием останова поиска является первое попадание 8 — м системы в е-окрестность экстремума, равнукз О,!. Исходные данные таковы: а,=аз=аз —— 1; а4 — — О,5; х,0==хза=хзч=х4Р 25; а2=4. База каждого просчета равнялась 500 вариантам. Масштабный коэффициент пробного шага а=1. Будем характеризовать качество метода поиска средним числом экспериментов Л'. Мгу =пи~, (4.7.9) хв ! Ю зо 40 га !!4 где пг — - выбранное число проб (иакоплений) в каждом состоянии системы; и -- среднее число выборок на один цикл поиска, включа~ощее в себя как среднее число удачных,таки среднее количество неудачных выборок.
Ясно, что математическое ожидание числа экспериментов пропорционально времени поиска экстремума. При моделировании рассмотрен вопрос о влиянии масштабного коэффипиента рабочего шага на затрачиваемое число экспернментов )у. Результаты моделнрованин отражены на рнс. 4.9, из которого видно, что существует оптимальное значение а, „ при котором МЛ' минимально. Однако величина а,ч, зависит от положения исходной точки в пространстве параметров. Кривая ! соответствует указанным выше исходным координатам, а кривая 2попэ ! лучена при поиске из начальной точки, расположенной в два раза ближе, чем в случае кривой Таким образом, при настройке экстремальной системы управления с использованием данного алгоритма поиска необходим подбор оптимального масштаба раРас.
4.4 бочего шага. Увеличивая число накоплений т, можно точнее оценить вектор и модуль градиента. Однако прн этом будет возрастать число экспериментов йГ. С другой стороны, при малом числе накоплений и оценки параметра Х будут производиться с боль- ма юа яю яэ~ юла юа а г с а а ююиюютэюммммт шими ошибками, вследствие чего число экспериментов может увеличиться. Поэтому возникает вопрос о выборе оптимального числа накоплений. На рнс. 4.10 представлены в виде кривых результаты моделирования — зависимость среднего числа экспериментов при поиске от числа накоплений. Кривая 1 относится к алгоритму первого вида, а кривая 2 — ко второму. Эксперимент показал, что при обоих видах поиска существует опти- мальное значение числа накоплений, при котором среднее число экспериментов минимально, что подтверждает ранее сделанньш вывод о малости оптимального объема выборки. На этом же рисунке для сравнения приводится кривая д, характеризующая скорость оптимизации методом случайного поиска с пакопле- Н О/ дзд405 ОбдглЗ ЗЭ Щ В Ф 6 К М 6 Рис, 4.1/.
нием, для которого также определен оптимальный масштабный коэффициент рабочего шага (рис. 4.11). Длина пробного шага в сравниваемых алгоритмах выбиралась единичной. Найдено путем моделирования оптимальное число накоплений для случайного поиска. Из кривой 3 (см. рис. 4.!0) видно, что объем экспериментов минимален при числе накоплений т= 1. Сравнивая оптимальное число экспериментов для рассматриваемых алгоритмов, можно отметить, что статистический поиск с адаптацией в среднем имеет большую скорость сходимости.
Известно, что чем меньше отношение «сигнал)помеха», тем медленнее сходится процесс поиска. Зависимость среднего числа экспериментов при поиске от величины дисперсии помехи, полученная для алгоритма первого вида, показана на рис. 4.12. Как следует из графика, при малых помехах средние затраты экспериментов мало отличаются от затрат на незашумленном объекте (ов= 0). Прп дальнейшем увеличении интенсивности помех среднее число экспериментов резко возрастает. Исследуемый алгоритм опробован на функции с оврагом. Анализ проведенного моделирования показал, что система быстро выходит в район оврага и затем начинает длительное время блуждать по оврагу, пока благодаря воздействию помехи не попадает в требуемую окрестность.
Таким образом, ыб данный алгоритм кв овражной ситуации» пракгическп нс работоспособен, как впрочем и другие градиентные методы. На основе проведенного экспериментального изучения свойств статистического поиска с управляемой длиной рабочего шага можно сделать следующие выводы; 1) СущаетауЕт ОнтнМаЛЬНЫй ОбЪЕМ НаКОПЛЕНнй Лцн„, При КО- тором алгоритм имеет в среднем максимальное быстродействие; 2) алгоритм отличается повышенной скоростью сходимостп по сравнению со случайным поиском с накоплением; 3) в данном виде алгоритм практически не работоспособен чв овражной ситуации»; 4) рассмотренный алгоритм целесообразно применять для оптимизации многомерных зашумленных объектов, имеющих унимодальную функцию качества.
ГЛАВА т СОПОСТАВЛЕНИЕ СЛУЧАЙНОГО ПОИСКА И СТОХАСТИЧЕСКОИ АППРОКСИМАЦИИ $ вл. ИОстАНОвкА 3АдАчи В последнее время большой интерес проявляется к методам стохастической аппроксимации, впервые предложенным Г. !роббинсом и С. Монро [1], Д.