Главная » Все файлы » Просмотр файлов из архивов » Файлы формата DJVU » Л.А. Растригин - Теория и применение случайного поиска

Л.А. Растригин - Теория и применение случайного поиска, страница 21

DJVU-файл Л.А. Растригин - Теория и применение случайного поиска, страница 21 Алгоритмы оптимизации основанные на методе проб и ошибок (2692): Книга - 5 семестрЛ.А. Растригин - Теория и применение случайного поиска: Алгоритмы оптимизации основанные на методе проб и ошибок - DJVU, страница 21 (2692) - СтудИзб2019-05-09СтудИзба

Описание файла

DJVU-файл из архива "Л.А. Растригин - Теория и применение случайного поиска", который расположен в категории "". Всё это находится в предмете "алгоритмы оптимизации основанные на методе проб и ошибок" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 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) также сходится, так как оп иажорнруется ряоз дом ~~~ е а.

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4986
Авторов
на СтудИзбе
471
Средний доход
с одного платного файла
Обучение Подробнее