Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 21
Текст из файла (страница 21)
Сходимость алгоритмов проверялась на квадратичной форме Работа обоих алгоритмов рассматривалась прн одинаковых начальных условиях, н поиск останавливался при попадании в е — окрестность экстремума функции 9(Х), причем а~в= '-, К;.=н (1=1,2,...); о=1; а=0,1; МЧ;' д=0,5; ххэ — — х„,о=! (й, т=1,2,..., л).
1 При у>; — пн один пз алгоритмов не обеспечивал попаданий 2 в е — окрестность со значением функции Я(Х) =0,05. Это хорошо согласуется с условиями (5.3.3) и (5.3.6). На рис. 5.2 показан график е=МЯ'(Х) в функции числа 1 измерений Ж для и=-К;=3, у — --. 4' Кривая ! соответствует среднему поведению алгоритма случайного поиска, кривая 2 — среднему поведению алгоритма стохастической аппроксимации. Осреднение Я(Х) производилось на базе !00 экспериментов. На рис. 5.2 показаны также гистограммы при оптимизации алгорнтмамн (5.3.2) и (5.3.8) различных е — окрестностей Я(Х). Аналогичные картины наблюдаются для всех л.-э2, Наглядно видно, что при увеличении числа итераций возрастает вероятность того, что случайный поиск окажется лучше, чем стохастическая аппроксимация.
В пределе она будет равна единице. Экспериментально показано, что последнее свойство выражено особенно заметно при увеличении и. Таким образом, сходпмость случайного поиска прн и - 2 в среднем превышает сходимость стохастнческой аппроксимации при выборе а; н д; такими, что Я(Х) представнма в виде линейной формы на промежутках АХ~=а;~угад Я(Х,) (.
Так как из выражения (5.3.11) следует, что зашумленность объекта пропорциональна числу итераций в степени у, то по мере продвижения к экстремуму объект как бы попадает в зону больших помех даже при сравнительно малой начальной зашумленности а; (5.3.12). Из этого следует, что случайный поиск имеет явное преимущество перед стохастической аппроксимацией. В связи с тем что сходнмость обоих алгоритмов ухудшается при увеличении оь необходимо коэффициент у выбирать малым. !36 $ бзк КУСОЧНО-ЛИНЕЙНАЯ АППРОКСИМАЦИЯ ФУНКЦИИ, ОПТИМИЗИРУЕМОЙ В ОБСТАНОВКЕ ПОМЕХ Обозначим через 8(Х) матрицу вторых производных функции (;1(Х), удовлетворяющей условиям (5.3.4), (5.3.5).
Лемма 1. Если 1) выполнены условия (5.3.4), (5.3.б); 2) итерационный процесс нахождения экстремума строится по формуле Х; =Х; — ЛХь где ЛХ,г ав Етае( Я(ХС), ав= —.; с ' (5.4.!) 3) а выбрано так, что на первой итерации 9(Х) можно считать линейной формой с некоторой погрешностью О(!Лхв)')х, т. е. Я(Х~) — с)(хо) =с',Лхо, дгад 1;!(Хв))+0(1ЛХо)з), (5.4.2) то всегда найдется такой номер 1, что для 1~7 величина (1; пе превысит (4о. О(/Лхс))а 0()ЛХо)) (ЛХь игам Я(Х,)7 с',Лх„Втащи Я(Ха)) г причем последовательность )3; такова, что (!с< —,, где с О.
! Доказательство. Разложим Я(Хгы) в ряд Тэйлора: 1!(хсчч) — 1!(х;) =(лхь ягас(Я(х;))+ +-,-1-<В(Х,— (ЛХ;)ЛХь ЛХ;>, !37 где 0"=.1- .!. В целях упрощения доказательства ограничимся функцией двух аргументов Я(х) =Я(х. у). Пусть Ох,=х; — (Лх;; т)а,=- Ус (ЛУс (сх (хс У1) и Яхх (хо У~) — соответственно первая ' Таков выбор а ие противоречит сходимости алгоритмов стохвстичсскоа вппрокспмапии и вторая производные функции Я(Х) по х в точках хь д, н аналогично по другим аргументам.
Используя (5.3.5), оценим р;; а ! 9,'(хзьу;)Я.. (О..ь Од;) 2! ~ Я„з(хьу )+ф,з(хьу;) 2Я~(хь уг) Яз(хй У1) (~ (Ох1 Ода) + Да~(х1 уг) Оуг (Ох~. Оа!) 9„.з(хь у;) + ф7(хь у,) аЕ ' Я„.~(хь у;) + 29„(хь у ) Яг(хь у;) + 9з'(х, д,) ~ 2! ~ [ягаг! Сг(хьу ))" а!. .аЕ :-=. ((+2) соз ~р,гсоз рх, !)~~ — ~ ро (5. Я,.(хь у,) соз р„. ) ОгадЯ(хь У,) ! Яг(хь уг) 'р-" ~ йтад г;! (хь д,) ~ ' Для и-мерного случая легко получить ахи р1» ~~ ро. (5.4.5) Лемма 1 доказана. Следствие.
Если последовательность а; принимает значения аь аь .,аь..., удовлетворяющие условиям (5,3.3), причеч аьы~аг для всех ! (в частности, последовательность может быть оптимальной в смысле скорости сходнмости алгорптмоа к Хз), то всегда найдется такой номер 7, при котором для г==.! имеет место кусочно-линейное представление 9(Х). Лемма 2.
Пусть справедливо (5,4.!), (5.3.4)„(5.3.5), тогда !)гп(~афтаб Я(Х;) )(1-т) =со, (5.4.6) ! где 0<у< —. 2' Доказательство. Определим скорость убывания (Огаг! Я(Х;) ) в процедуре (5.4.!), учитывая ее сходимость к точке Хе при 138 (5.4В) угад Я(Х!) =0(1Х;) П [Š— а +!0(1Х +!)] Х„, О~+ ! ]ягад(!(Х!) ] ="~1 ~ ~ ! ~1 П (( — а„,э!!(...в ), э-! ~хат ж-!-! /и 1= у'~(!1!„эхм,)'. в=! ! Оценим Ц (1 — а,!!1вах) В окрестности Хэ имеем Рлз ! И аиАпьах = !1!!!а? ~ О. е ю !и а (5.4.9) !зз Разложим Я(Х) в ряд Тэйлора в окрестности Х"! с1(Х) =а(Х')+<й б а(Х'), Х>+ -)- — (В(Х" -(-1Х) Х ХУ вЂ” ХтВ(1Х) Х (5 4.7) где 0~1 =); В(1Х) — матрица вторых производных в точке 1Х, Т вЂ” операция транспонирования. Предполозким, что в окрестности Х* функция О(Х) выпукла, тогда из (5.3.4) и (5.3.5) следует, что квадратичная форма (5.4.7) положительно определена.
От матрицы В(1Х) легко перейти к диагональной мат- рице 0(1Х ! прн помощи ортогонального преобразования 17т(Х)0(1Х)Я(Х), где Я(Х) — ортогональная матрица. Обозна- чим через др,д й-й диагональный элемент матрицы 0(1Х), шах 0(1Х) =0, где В" — окрестность точки Х", в которой спра- !.
х~в" ведливо (5.4.7); Ищ наибольший элемент матрицы О. Предположим, что окрестность Х* достигается после и! ите- раций поиска. Найдем закон изменения ]й!гад О(Х) ] для квадт ратичной формы Я(Х) = — Хт0(1Х) Х: 2 цгада(Х ) =0(1Х ); Х„.,+,—— Х„,-а„, ягад Я(Х„,) =(1 — и 0(1Х„,)]Х „; игам О(Х, !) —.-0(1Х в!.!)(1 — а,„0(1Х )] Х 1 ПОлОжим иж~йщд~= тогда 2* / ' ш.1.21 282~ гп! 28 П (1- - ( .) = П 2 . =,;,, ,--'= —.,;; (5410) „,. ~ 2(1+т) 2м!!1! 2ьчу!!! Применяя формулу Стирлпнга для 11, получим 1 Т ! (1 — а +; ( ..) ~ =,.
хи+! )!Я (5.4.! 1) Таким образом, !пп (~угад Я(Х<) 1р-т] 1!!ш ~= р-т =со, /! ! ОЭ )~п! (5.4.12) 1 так как 0<у< —. 2' 1 Очевидно, что (5.4.12) справедливо при а,п'„„< †: Лемма 2 доказана. Теорема 1. Если коэффициент а выбран так, что справедливо (5.4.1) и (5.4.2), то, начиная с некоторого номера йфункцию Я(Х), оптизимируемую по алгоритму (5.3.8) и удовлетворяющую условиям (5.3.4), (5.3.5), с вероятностью ! можно аппроксимировать линейной формой с относительной погрешностью, не превышающей ро (5.4.3). Доказательство. В кусочно-линейном поле процедура (5.3.8) запишется в виде Х;„., =Х; — !ЛХ;~Е; з!пп(Еь вагаб Я(Х;))+ (5.4.13) 240 а где 1оХ;~ =а;)йтад Я(Х;) ~; е;=еп — ееь ыо Среднее смещение к цели вдоль антпградиентного направления при работе алгоритма (5.3.8) ! М;1= ~ ЬХ;! Мт1ь (5.4,14) Очевидно, что !ЬУ;~ < !ЛХ;~.
С увеличением числа параметров и [9! !ЛТ;! уменьшается. рв= — !)(»о, Юо) (; (5.4.!5) а (», у)о„.(Е„О,)+2а(х, р) а„(х,у) ага(Е,, О„)+ д ) +Е(., )а„(6.,6,) 9'(х р) + Я '(х р) Найдем а»"'. Подставляя в (5.4.4) а»* вместо а»», получим л» !!(»» й'») 2 (5.4.! 6) Приравнивая (5.4.15) к (5.4.!6), найдем !(х» у») ! Рассуждая так же, как при выводе (5.4.4), получим Дх», и;) ~2Е. лв) Для и-мерного случая ~(х„у») =лЕ. Таким образом, а4» ~ — ' = й (5,4.17) Введем »1»а = ) б~'1-15У'! (5.4.!8) Р»»с дЗ, Е!айдем вероятность р(х») попадания случайной величины †»в е» (5.4.13) на участок, заштрихованный иа рнс.
5.3, кото2д» рый соответствует вероятности выхода функции ()(К) за пределы !4! Из (5.4.5) — (5.4.14) видно, что по алгоритму (5.3.8) Я(Х) в среднем не выйдет за пределы области, в которой имеет место кусочно-линейная аппроксимация. Положим ) ЛХ») = а»*) игам Я(Х»), где коэффициенты а выбраны так, чтобы для процедуры (5.4.1) и всех» имело место 6 =р ч=ро, где: кусочно-линейной аппроксимации проекции случайного вектора а;в — е,З; на градиентное направление 2д~ Р(х;) =Р . е;айги~= — -Ф(сбгар-т), (54.19) 25'Р т ' га! 2 )2й с= —, Ф(х)==)е 'Ж, оп з Увеличим р(х;), произведя замену Ь;а на (5.4.20) Из (5.3.6), (5.4.!3) и (5.4.17) следует, что Л;=а ! — —,~ ) пгад Я(Х;) ).
1! (5.4.21) Заменяя в (5.4.!9) Л;а на Л» из (54.2!) и учитывая (54.!2), получим Р (х;) = — — Ф (г(з) . 1 2 (5.4.22) где (5.4.23) 1 1 Р(х) = — — Ф(х) — — е х г'2п (5.4.25) !42 Так как б>0, то Р(х;) =О. 1' Ъ Теорема будет доказана„если событие х; произойдет конечное число раз в бесконечной последовательности итераций, т. е. необходимо доказать, что ,~„ Р(х;) <оо (5.4.24), как это ! следует из леммы Бореля--Кантелн (см. (13)).
Учитывая (5.4.23) и применяя асимптотяческую формулу для Р(х) при х — оо (13), получим Из формул (5.4.22) — (5.4.25) следует, что »ч:ь 1 и 2 Р(х») = 2)»пг; » (5.4.26) а; 2- Х»созф ->Ль 2я'» (5.4.27) где / п "Й(ф» ~ "lм а'= ~7,» (ець-е»а") а. а *» Чтобы найти вероятность такого события, необходимо оценить интеграл типа (5.4.19), в котором функция Лапласа 6»(х) !43 Пусть о — некоторое целое положительное число, большее 1 единицы, такое, что 26~ —. Рассмотрим наихудший для сходио 1 мости ряда (5.4.26) случай, т.
е. когда 26= —. Докажем сходно мость ряда ~ е я, применив к нему интегральный признак ~" 1 » Маклорена — Коши, т. е. заменим ряд ~ е а интегралом » р / е Яс(у. Произведя замену х= —, полУчим интегРал ! о/е-' хе-'~(х, сходимость которого следует из сходимости гам» ма-функции Г(о) = 7 е-'хе-Чх. о Ряд (5.4.26) также сходится, так как оп иажорнруется ряоз дом ~~~ е а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
