Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 10
Текст из файла (страница 10)
Для предельного среднего приращения функции качества М(АЯ) =:.-с Ф В (а,» а,) +о> .% („,,), (3,3,35) о А(>> 2)2 2о ' 2о откуда при о О получаем формулу (3.3.22). Во втором случае предельное распределение вектора % Ф, (,~о>+ р ло>) р =Ф (рР>+рз<о>) )=2 3 (3,3.36) Предельное среднее приращение функции качества М(АЯ) ==~Ф ~ — „) (рг >+ро( >) (и>+аз) + )>2~ йа ) +Ф~ — ! (Р>Оо>+Рз>о>) (а> — аз) о (2о ! (3.3.37) Аналогично при о. О получаем выра>кение (3.3.26). Для обоих рассмотренных случаев получены формулы для определения пошаговых характеристик обучения и пошаговых средних приращений функции качества.
с В работе 157) исследован случай, когда б=-, где й — целое й' число. Матрица переходных вероятностей для вектора памяти % имеет следующий вид: о,.....,... о, Рм, О, Рзз, О,......., О ,,' — (3 3 33) ~~ О,, О, Рзи,зз — ь О, Рзз,зз+~ и '''1~ ,' О,...., О, Рзз+изы Рз виза+1 где Π— нулевые блоки; Є— матрицы Якоби. Здесь цепь Маркова является эргодической для любых значений с. Получены формулы для вычисления предельного распределения вектора % и предельного среднего приращения функции качества.
Так, например, для 1=1 и с — я! имеем следующее предельное распределение вектора %: Ф вЂ” — Фз— Р|= — Рз Рз = Рз' Фз Фз Фз —, — ФзР» — Рз, 'Рз = — Рз' Фг Ф~ ~3.3.39) Рз !+ — + + — + ) Ф~ Фз Фз Фд ', Фз Фз Фз Ф!1 рз = р,= р,= Р,-О. вигза) 61 Предельное среднее приращение функции качества Ф(Ф4 ~ Ф(Ф4 Ф>Ф> ->- — 3 — -3 [1 > — "— + 3 --3- 'тЯ (3.3.40) Ф>Ф3 ~ Ф(Ф4 Ф«Ф3 11а рис. 3.7 показано изменение у2М(Л(;>), вычисление>е пофармулам (3340) и (3335),при а(=1, аз=0, с:=1 для 6=-с и б~2с.
Видно, что при б=с предельное среднее приращение функции качества примерно на >/3 больше, чем прп б~2с. Следовательно, при оптимизации в обстановке помех «медленноеэ обучение приводит к увеличению скорости оптимизации системы. Это объясняется тем, что прн медленном обучении происходит более полная фильтрация помех. В этой >ке работе рассмотрена динамика покоордпнатного обучения прн оптимизации в обстановке помех в многомерном пространстве. Пусть б= 2с и направляющие конусы градиентного направления удовлетворяют условиям: а>)и«)...
»а ~0; а>)аз+...+а«. (3.341) Тогда предельное распределение вектора ЪЧ Р; = 2' — "Ф( (('= 1, 2,..., 2"), (3.3.42) а пределыие среднее приращение функции качества М(ЛЯ) ==2'-"с Ф ' +...+Ф вЂ” ~ — - а>+ *['["') "[ — "')- (-' — ")- [ — "')" ...— Ф[- '---)] „,4[Ф[ — ')— — Ф[ — ').(-Ф[ — ') —...-Ф[: '--)]~). (3343> При о — 3-0 получаем формулу (3.3.33). Г>2 ЬХ =аг (Е, %), (3.3.44) где а — длина шага; Š— единичный случайный вектор, равномерно распределенный во всех направлениях пространства параметров Х; г — некоторая непрерывная единичная векторная функция двух переменных векторов Е и %. Функция )с(Е, %) должна удовлетворять следующим условиям: !.
(3.3.45) где 0=-(О, О,..., 0). 2. М(г"(Е,%))=- — — -", 1%) ' (3,3.46) где М вЂ” знак математического ожидания; )%) — - модуль вектора %. 3. (3.3.47) где Р— знак дисперсии; 0=сопи(; а=сопи(. При выполнении зтих условий функция г" реализует пространственное распределение случайного шага, которое может целесообразно изменяться по мере накопления опыта работы системой. Различные функции г(Е,%) предложены в работе (Ц.
63 Проведенные исследования позволяют сделать вывод о том, что главным недостатком алгоритма покоординатного обучения является их немобнльность при перестройке вероятностных характеристик. Это положение справедливо для общего случая оптимизации многомерной системы как прн отсутствии, так и прп наличии помех. Другой класс образуют предложенные Л. А. Растригпным алгоритмы непрерывного обучения (Ц. Пусть и-мерный вектор %=(шь...,ш„) характеризует обученность систем, т. е.
определяет вероятностные свойства поиска, причем при %=- =-(О, О,..., 0) поиск должен быть равновероятным. Направление случайного шага представляется в виде некоторой векторной функции Подробно алгоритмы непрерывного обучения исследованы в работах (3, 53, 58) прн следующих функциях Р(Е, %): Р~(Е,%) = Е+% (3.3.48) В (0,5%+ Е) 1В(0,5%+Е) ~ ' (3,3.49) где  — матрица ;'!1,0,...,0,0 (, В 1'Ь!' (3,3.50) (3.3.52) % „.
=й%. — б(Лдн+ Ц) ДХн, где й — - коэффициент забывания (0<й=1)", б — - параметр скорости обучения (б>0); ЬЯн — приращение функции качества на М-м шаге; — коэффициент «скептицизма»; ЛХм -- вектор Л'-го шага системы в пространстве параметров. Чтобы избежать чпередетерминирования» системы поиска, модуль вектора % ограничивается: )%~ (с (с)0).
(3.3.53) В работах [3, 53) описывается и экспериментально анализируется непрерывный алгоритм самообучения с функцией Р(Е, %), определяемой формулой (3.3.49), при оптимизации многопараметрических систем. Показано, что он имеет рял преимуществ по сравнению с покоордннатным алгоритмом обучения. Алгоритм самообучения можно представить в виде векторного рекурреитного соотношения, связывающего два следующих друг за другом значения вектора %: Геометрическая интерпретация алгоритма (3.3.49) следую- щая.
На векторе памяти % строится эллипсоид вращения с фо- кусами Р, в начале и Еэ в конце вектора % и с полуосями, определенными формулами (3.3.51). Длина вектора % опреде- ляет эксцентрпситет эллипсопдз, а его поверхность . и-мерный заь кон распределения вероятностей Р(ЛХ). При ~%! =О для вектора е д ) ЛХ имеет место равновероятиый закон распределения, соответствующий поиску без обучения.
При увеличении длины вектора % эллипсоид вытягивается и поиск !ал.г становится более целенаправленным. При )%~ =-2 поиск детерми- 1ич-о п ма нируется по иаправленшо вектора %. Построение эллипсоида и ди- Рыс. 8.8. намика обучения показаны па рис. 3.8. Экспериментально исследовалась работа алгоритма в двумерном пространстве параметров прц стационарном и иеста- ционарном режимах па объекте с линейной функцией качества Яэ Хь (3.3.54) В стационарном режиме в начале поиска соР>=с, вы~=О, т.
е. начальное направление вектора % совпадало с направле- нием, соответствующим градиентному. В этом случае быстро- действие поиска незначительно зависит от параметра скорости обучения б, но сильно зависит от величины с. Чеы больше эта величина, тем выше быстродействие поиска. Эксперименты по- казали, что в стационарном режиме оыстродействие непрерыв- ного алгоритма обучения ье зависит от воздействия помех. Та- кое обучение играет роль фильтра, пропускающего только систе- матические изменения в обстановке и не реагирующего на случайные флуктуации (помехи). Таким образом, самообучение алгоритмов случайного поиска служит хорошей защитой против помех.
Для описания динамических свойств обучения в иестационар- ном режиме вводится количественный показатель а эффектив- ности обучения, равный косинусу угла между вектором памяти и направлением, обратным градиентному. Моделирование на ЦВМ процесса обучения в двумерном пространстве параметров показало следующее: !) средняя эф- аз фективность обучения а,а и среднее число шагов настройки М,г возрастают при увеличении модуля вектора памяти ~ % ~; 2) с уменьшением б а,р также увеличивается, но прп этом возрастает среднее число шагов, неооходимых для настройки; ап ~ 3) увеличение уровня помех заза грудняет определение правильного .1~ направления и приводит к сниже- нию эффективности обучения. ш г Проведено сравнение непрерывзэ ного обучения с покоординатным д обучением и с регулярными метог з ~ а г г г ~ дами поиска.
В основу сравнения было положено количество вычисРис д9, лений функции качества, необходимых для достижения экстремума с заданной точностью. На рис. 3.9 показаны результаты сравнения непрерывного ооучення с по- координатным обучением при оптимизации многопараметрических объектов с центральной фувкцией качества. Видно значительное превосходство алгоритма непрерывного обучения уже при размерности пространства п>3. Сравнение непрерывного алгоритма ооучения с методом градиента и методом наискорейшего спуска проводилось иа центральной функции качества в двумерном пространстве параметров в обстановке помех. Моделирование на ЦВМ показало значительное превосходство по скорости сходимостн и дисперсности результатов алгоритма непрерывного обучения над методами градиента и наискорейшего спуска.