Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 20
Текст из файла (страница 20)
Пусть частные производные по координатным осям оцениваются по двум замерам следующим образом: дЯ'(Х) ! — — Я (х;+а, х) — Я (х„— д; ))— дхги 2йа дЯ(Х) 1 ". + — — (ен -еа"), дхь; 2д. (5.3,1) где штрих выражает наличие помехи е(о): Я'(Х) =!1(Х)+е(о). функция качества оптимизируемой си- стемы; вектор оптимизируемых параметров; случайные помехи с распределением М(0, о), накладывающиеся на функ- цию качества вдоль й-й координатной осн на 1-й итерации (дисперсин по- мехи о' не зависит от й и !); единичный вектор в направлении й-й координаты; д(х) Х=(хь хм...,х ) е"о, ех,т 120 для алгоритма (5.2,3).
Из условий (1' — 2'), (!" — 2") можно найти класс функций, для которых сходимость к Х* происходит при А~=сонь!. Например, для положительно определенной квадратичной формы зто следует немедленно. хси — значение параметра х~, после Ьй итерации; Я~ — величина пробного шага вдоль й-Й координатной оси на 1-й итерации. Тогда итерационный процесс нахождения экстремума функции Я(Х) в соответствии с методом стохастической аппроксимации записывается в виде следующей рекуррентной формулы: Х;~,=Х; — а; пгад Я(Х;) =Х;— — а; йтад Я(Х;) + ' Хь 2а; ™ (5.3,2) где 2; — вектор шума; Х;= (ео' — а12', еиз-е,р~,..., ео" — емя). ОР СО Х а,=оо;,~~ а~у;~со; ~, — 'г ~со.
(5.3.3) -~ йР Функция Я(Х) предполагается непрерывной и для нее существу1от первая и вторая производные. Кроме того, длн любого Ь>0 существует такое й(Ь) >О, что из 11Х1) ~Ь следует Я(Х) ~й(Ь) и / угад Я(Х) ~ ~й(Ь). (53 4) ЬзЯ(Х) Далее, вторые частные производные -- предполагаЬхьдхт ются ограниченными для всех й, т=1,...,л, т. е. д д(Х) дхьдх (5,3.5) Без ограничения общности предполагаем Х*=О, Я(О) =О, (,1(Х) ~О для всех Х. 127 Рассмотрим класс функций Я(Х), для которого последовательность Х; сходится с вероятностью 1 к точке Х~, в которой эта функция достигает экстремума при соблюдении следующих условий Блюма (3): о д' а;= —.
и д;= —. Е ' И (5.3.6) ! где 0<у< —. 2" В качестве метода, конкурирующего с методом стохастической аппроксимации, выберем метод случайного поиска с «парными пробамиа, для которого Хмы = Х; — '= [Я'(Х;+ и, В;) — Я'(Х; — и, = ВИ В . (5 3 7) 8~а Итерационныи процесс для алгоритма случайного поиска может быть записан аналогичным образом (5.3,2): Х,„=Х,— "в--((~(Х,-+д,аВ,) -1~(х,-д, )) В,+ а;в + (еп — еа) 2и1ю (5.3.8) Задача заключается в сопоставлении быстродействия обоих методов поиска па одинаковых объектах.
1-1адо будет показать, что при прочих равных условиях всегда можно так выбрать зависимость параметров случайного поисиа а,я и д;в от ю', что его сходпмость будет вьппе, чем сходимость метода стохастической аппроксимации (даже оптимального в данной ситуации). В $5.4 доказано, что в алгоритмах (5.3.2) и (5.3.8), начиная с достаточно большого номера итерации с вероятностью 1, пгад Я(Х) =сопз1. Итак, пусть функция качества на каждой итерации алгоритмов (5.3.2) и (5.3.8) линейка, т. е. угад)Я(Х) ( =сопз1. Начнем со случайного поиска, для которого в этом случае Хг ы — — Х,+а,а (угад Я(Х;) ~ соыр;Е, + '= е;()2о) Яь (539) '' 2~;а где г;()~2п) =з; -- случайная нормально распределенная помеха с дисперсией 2о' и пулевым математическим ожиданием; 128 В. Дуная (10) показал, что для данного класса функций вы- Я и ражение —.— является оптимальным из класса а;= —,„, где 0<о=-!, поэтому в дальнейшем будут использоваться чн — угол между вектором градиента н случайно выбран- ным направлением; (Еь афган Я(Х;)) /йтао Я(Х;) ( созгрь если О~гр;(, и Зл О, если — ~ср,( — .
2 ' 2 пь а;а- ---, где н;= Мч;' Целесообразно уменьшать коэффициенты а,в н д;в при работе алгоритма (5.3.9) по мере достижения им поверхностей уровня Я(Х), соответствующих поверхностям уровня Я(Х), достигнутых при работе алгоритмом (5.3.2). Число шагов (подытераций) случайного поиска К; между каждой (-й н 1+1-й итерацией алгоритма стохастической аппроксимации вычисляется по формуле (и К,= — „', (5.3.10) где 0'; и У"; — соответственно среднее смешение к цели по методу стохастической аппроксимации за 2п измерений функ- ции Я(Х) и по методу случайного поиска — за два измере- ния. 12Э (Х, т)=~ ххух — скалярное произведение Х и У. е ! Так как каждый рабочий шаг стохастнческой аппроксимации совершается после 2п измерений функции качества с соответствующим уменьшением коэффициентов а, н дь а для случайного поиска рабочий шаг производится лишь посче двух измерений функции качества, то при аналогичном уменьшении коэффициентов а; и д;в случайный поиск оказывается явно в невыгодном положении, особенно при больших п.
Корректность постановки задачи о сравнении обоих методов в кусочно-линейном поле должна заключаться в том [11), чтобы соблюдалось равенство коэффициентов д, и д;а, длин рабочих шагов а; дгадЯ(Х,) и а;в (Хгад Я(Х,) (сов ~;; соответственно для алгорнтлюв (5.32) и (5.3.9), т. е. а; — —; кю=к в. /соз йч/ ' Для црактическнх целей можно принять Этим оба метода будут поставлены в равные условия. Введем параметр зашумлепностн поиска, который для каждой пробы равен отношению помехи к полезному сигналу, т, е. — .— -!7 е, ( г'2о) 25) дгьаб д(й;) ) (5.3.1 1) среднеквадратичное отклонение которого о ==:-- — -- — — Р=т;Р, 12а!йгаб а (Х1) 1 (5.3.12) где )!А)игам Ц(Х~) ! ' -гр, рлм Огт,у Н Рис эд. У;=-а, М(созъ~,), ам=а;) цгаб 9(Х;) ~. где Аналогично тому, как это сделано в работе (12], можно по- лучить Г '", з!п"-з<р; соз" — т<р4~; и,=, В,,2.— ~ ]"— "1'1:Ф з(п' ф; '"" а!и" йн соз"-з ~;сыч 'р ')'! — 1с; з(п' ~р; (5.3.13) 130 Средний путь, проходимый в процессе поиска прн оптимизации методом стохастической аппроксимации вдоль антнградпентного направления за один шаг (2л определений функции качества) (рис.
5.1): где, как и в работе (12), и; 2,; ~ 2 Ь = -- - '; г; = о; г'2 .;+1' = г;+1' =,.( и !2 Для нечетных и подстановка г'=з!ох в (5.3.13) дает й. 3 ,'! -2(1 (з) 2 (! 120 ) У', = 2"-'гозВ„) — — — — = —.=- о (5.3.14) з!Кп Л Фа =з!Кп (й! ! в+ с), ЛФа — — 2й; ~ргали Я(Х;) )соз Чз. (5.3,15) где Вероятность правильного решения при этом р!1(~созйч 2 2 (, хР (5.3.16) где о н = — — — — --- — —; й~йгаб Я(Х;) ~ ' с Ф(1) = — -„~ е-"Н. г'н" Осредняя (5.3.16) по всем возможным реализациям угла р в л-мерном пространстве аналогично (12), получим среднее смещение к цели на 1-м шаге лв У,-2~,В,/ Ф( ') д, Ь"-'юФ~,.
(5317) о нт 131 Последний интеграл берется в конечном виде, Для четных п получаются эллиптические интегралы. Как и следовало ожидать, прп 1- оз и конечной длине шага а;„- О; У'.,— О, так как !с; — О, о- О, у>О, т. е. среднее смещение к цели с ростом числа итераций стремится к нулю. Из (5.3.9) следует, что рй шаг будет сделан в правильном направлении, если Вычислим пнтегРал т'= ~ Ф ~ — —.- ~ соз «Р; з!и"-'сй,йуь (соз ~р;! ~ и! После замены у=-з)п«р; имеем ! (У1 — ~з! ~ Ф ..... р««-2Др о « ~,п «ДФ и†! ! «« 2 . 2 — (1 — !зиз) е-"~й. (и 1)Уя о (5.3.18) Для нечетных и последний интеграл берется в конечном виде. Так, для п=3 получаем и"„=В,оез 1 — — — !! —,„+ — 'е Обозначая р=к!т=У2оо имеем 0"з =пыВ, 1 — !' Ф вЂ” + ! з Р, (5.3.19) При п=б У"м=аы — — — + 8 р' Ф вЂ” + =- —, е Р . (5.3.20) Так как в окрестности экстремума р — «-сю прн 1-«оо, то интеграл вероятностей Ф(!) можно разложить в степенной ряд и огра- ничиться линейным приближением соз «р;'! 2 соз «р; р / у и (5.3.21) 132, Применив интегрирование по частям, а затем подстановку У1-~~' 1=- — — ---, получим Х Подставляя это выражение в (5.3.!7), после некоторых преобразований получим 2а~з, на'у'л (5.3.22) ~ — 3 2" з) — ==-==-..
' Ж г ф~' ~(1 — г2) з (1 — (байи) о ~1 — ЙРР К~= !,к л — ! (а — 1) уп / (1 — 12нз) е е-"~й о (5.3.23) т е. К, является функцией а, й у и х н не зависит от длины шага а;д. На первых шагах поиска прп незначительной начальной ,ашумленности еч (5.3.12) можно получить следующее выражение 111) для К;: (5.3.24) При больших а для алгоритма (5.3.2) имеем У'~=2а0 =~. о1)'а (5.3.25) где 1 У„= — — — †. (12). 12о;а)~а 1ЗЗ Теперь сопоставим сходимость обоих методов.
В качестве меры сопоставления выберем число подытераций К; (5.3.10). Пусть 1 — число итераций, за которое алгоритм (5.3.2) достигнет любой наперед заданной е — окрестности экстремума ! функции Я(Х); тогда, если окажется, что ~ К,<а), метод слу! ! чайного поиска будет лучше метода стохастической аппроксимации, в противном случае — наоборот. Из (5.3.14), (5.3.17) и (5.3.18) получим В районе экстремума Х*, т. е. при р — со, для систем высокой сложности, т. е. для п>>1, величину К, нетрудно вычислить из (5.3.22) и (5.3.25): К( ==)'а. ~л (5.3.26) 2)'2 Рассмотрим предел отношения ' — '~ который показывает, К я- со во сколько раз по отношению к методу стохастической аппроксимации возрастает эффективность метода случайного поиска с изменением номера итерации 1 от О до ос.
Воспользовавшись асимптотпческпм представлением при и сю получим К; 1!т — =4, и 0 К~ (5.3.27) !~(Х) ~, Ахьз, где п=З, 4,...,12. !34 т. е. относительное быстродействие метода случайного поиска при а-~оо н 1- оо возрастает в 4 раза. В работе (12) получены выражения типа (5.3.22) — (5.3.27) при различных и и и для частного случая у=О, Рассуждая и аналогично [!2), получим, что отношение а=и >1 для а~2 1 возрастает с увеличением каждого из параметров а, й у и х. Эксперименты, проведенные на ЭЦВМ «БЭСМ-2э, подтверждают указанные соображения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
