Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 2
Текст из файла (страница 2)
Таким образом, каждый этап характеризуется исходным состоянием объекта Ха и информацией, полученной в процессе идентификации в точках Х; (1=1,..., гп), которая заключается в соответствующих значениях показателя качества ~',1,=Я(Х;), 1=1,...,т (1.2.!) и ограничений Здесь выбор пробных состояний Х; производится в соответствии с алгоритмом поиска Х,=й(Х; ь ..., Ха/Фа), (1.2.3) связывающим предыдущие и последующие пробы, где Фе— вектор предыстории, характеризующий предыдущие этапы поиска, тт'= (вь..., ге„), (1.2.4) Решающее правило поиска на основе полученной информации определяет на каждом этапе новое состояние объекта Х =Г(Х,, Хь ..,, Х„(В,), (1.2.5) Алгоритм самообучения корректирует вектор предыстории с точки зрения информации (1.2.1) и (1.2.2), полученной на этом этапе: %~=Ф(%м Хо Хь..., Х„).
(1.2.6) Как видно, процесс поиска определяется тремя элементами: 1. Алгоритмом 12 выбора пробных состояний Хь 1=1,..., >и. 2. Решающим правилом Р. 3. Алгоритмом самообучения Ф. Эта общая схема поиска включает в себя достаточно большое множество различных алгоритмов оптимизации. Проиллюстрируем указанное на некоторых известных методах поиска (регулярных и случайных). й ьз.
пвимнпы пвиминвння овщнп схимы А.Метод градиента 1. Алгоритм выбора пробных состояний: Х,=Х,+йЕь (1.3.1) где ш=л, т. е. число проб в этапе равно числу переменных; Е; — единичный вектор вдоль (-й координаты; д — величина пробного шага. 2. Решающее правило: Р =Хе — а пгад Я, (1.3.2) где а — некоторая постоянная рабочего шага, а составляющие вектора градиента оцениваются по результатам замера показателя качества в пробных состояниях (1.3.1): дЯ 1 — — [Я(Х;) -Я(ха)), (1=1,..., и).
(1.3.3) дх; ф 3. Алгоритм самообучения Ф в дашщм случае может быть записан, например, так: тт1=%а — 6 ягаб Я, (1.3.4) где б — параметр скорости самообучения, а Фа — вектор предыстории. Учет предыстории соответственно изменяет решающее правило (1.3.2): Р=хо — а йтад Я вЂ” ЪЧо. (1.3.5) Б. Слепой поиск 1. Алгоритм выбора пробных состояний в данном случае представляет собой заданное пространственное распределение случайных состояний (1.3.6) р(Х). л 1ф(х;), (1.3.7) Это означает, что после каждой пробы принимается решение, переходить ли к следующей случайной пробе или предварительно запомнить результат последнего произведенного эксперимента.
3. В случае введения адаптации в процессе слепого поиска распределение случайных проб (1.3.6) бтановится условным: р(хув), (1.3.8) !О Число проб гп в каждом (гл=1). 2. Решающее правило в процессе поиска: этапе постоянно и равно единице определяет содержимое памяти если (1 (Х;) ~ ф,'; если Я(х,) ~Я,,а. если Я(Х;) )Я; 1а; если Я(Х;) ~Я; Р. где вектор памяти % характеризует, например, математическое ожидание распределения (1.3,8): В=~ р(Х)а) (Х, (1.3.9) Это распределение должно группироваться вокруг наилучшей пробы Хз, хранящейся в памяти. Поэтому алгоритм самообучения можно представить, например, в следующей форме: т!(Г ХО (!.3.10) которая в этом случае гарантирует поиск в районе наилучшей пробы Хз.
В. Случайный поиск с парными пробами 1. Алгоритм выбора пробных шагов для случайного поиска заключается в определении случайного направления Е, вдоль которого на расстоянии ~-д от исходного состояния Х, производятся эксперименты, т. е. Х,=Х +дЕ; где Е= ($ь сь..., ви) — единичный случайный вектор, равномерно распределенный в пространстве оптимизируемых параметрон (в случае без обучения). 2. Решающее правило в этом случае заключается в определении рабочего шага по результатам наблюдений показателя качества в точках Х, и Х,: ЛХг аЕ з1дп Я(Хз) — Я(Х~)].
(1.3.12) 3. В случае поиска с самообучением вектор памяти вычисляется по следующей рекуррентной формуле: %~ — — Й%а+ 6Е [Я(Хз) — 0(Х~)1 (!.3.13) где й — коэффициент забывания 0(А~1; б>0 — параметр интенсивности самообучения. Самообучение определяет выоор случайного направления Еа, например, следующим образом: ЕО=Д!Г(%+Е), (1.3.14) где б!г — знак направления. Как видно, в указанную схему поиска укладываются практически все известные методы поиска экстремума. й к4. двл фронтл решпния провлпмы поисковои оптимизлции Все возможные алгоритмы поиска экстремума можно подразделить на два больших класса: класс детерминированных, регулярных алгоритмов и класс недетерминпрованных, случай- ных алгоритмов поиска. Это Лад разделение производится в зависимости от того, содержит или не содержи г элемент случайности алгоритм определения пробных состояний.
В первом случае асовчеочо поиск можно назвать статистическим. а во втором регулярным. Таким образом, фронт Рис. 1.1. поисковых методов оптимизации разбивается иа два участка: фронт регулярных методов оптимизации и фронт статистических, случайных методов. На рис. Е! условно показано место проблемы оптимизации по отношению к обоим фронтам. Однако нз-за ряда объективных условий между этими фронтамн установились в некоторой степени антагонистические отношения. Это означает, что часть усилий затрачивается не па решение основной проблемы оптимизации, а на <самоутверждение» методов, которое достигается ценой изучения и сопоставления регулярных и статистических алгоритмов поиска в различных условиях и определения зоны их целесообразного применения. Однако задача сопоставления различных методов до настоящего времени сводилась в значительной степени к сопоставлению обоих видов поиска.
Попробуем сделать обратное и установить их общность и преемственность, Для этого необходимо обобщить алгоритмы поиска так, чтобы они содержали параметр стохастичности а. Если а=о, то поиск становится регулярным. При аФО поиск имеет статистический характер, причем с увеличением а влияние элемента случайности возрастае~. Пусть в регулярном алгоритме пробы производятся в строго определенных состояниях Хь..., Х .
Тогда статистическим расширением этого алгоритма будем считать, например, такой случайный поиск, в котором пробы берутся в состояниях Х~+аЕь Хз+аЕь..., Х +аБ, где Е; (1=-1,..., н1) — независимые случайные векторы. При этом решающее правило может сохранять свой вид, а адаптация будет сводиться к такой перестройке плотности распределения случайных векторов Е, которая повышает вероятность успеха на последующем шаге. Построим несколько таких расширенных статистических алгоритмов н проанализируем особенности их поведения.
й ЬЗ. СТАТИСТИЧЕСКИИ ГРАДИЕНТ Уже отмечалось, что метод статистического градиента [1, 2) обобщает обычный метод градиента. Построим алгоритм метода обобщенного статистического градиента, который имел бы параметр стохастнчности и, характеризующий степень случайности алгоритма.
Пусть случайные пробы Хь ..,, Х„, берутся на поверхности сферы, имеющей радиус д, с центром в исходном состоянии Х,. При этом каждая проба Х; находится внутри гиперконуса с углом полураскрытия а, ось которого совпадает с 1-м координатным направлением Е;. Алгоритм определения пробного состояния Х; сводится, таким образом, к следующему: 1. Выбору случайной точки Х на поверхности гиперсферы. 2. Определению попадания этой точки внутрь 1-го гиперконуса: (1.5,!) (Х вЂ” Ха, дЕ;) (д соз а, где (, ) — скалярное произведение.
Если это неравенство удовлетворяется, то Х является точкой 1-го эксперимента: Х;=Х. Если же неравенство (1.5.1) не выполняется, то следует перейти к следующему циклу, т, е. к следующему случайному выбору точки на поверхности гиперсферы. Очевидно, что в результате работы такого алгоритма прп ачь0 за конечное число циклов будут определены все т состояний, где н собирается информация о поведении объекта оптимизации, т. е.
выясняются значения показателя качества: $3 Направление рабочего шага прн этом соответствует направлению вектора Ъ'= —,~ (Х! Хо)[Я(Х!) 11(Х»)) (! 5.3) !са который является оценкой антиграднентиого направления. В случае т =п (при линейной функции качества),а - 0 и прн отсутствии помех получаем йг Ъ'=йг йтад Я, (1.5.4) т. е. в пределе рассматриваемый метод статистического градиента вырождается в обычный регулярный метод градиента. Однако при !п<и метод градиента эффективно «не работает», так как в этом случае пробы производятся не по всем л направлениям пространства параметров, Если вычислять градиент по (н<н пробам, то полученная оценка будет располагаться в подпространстве параметров и„следовательно, будет смещена. Для того чтобы устранить это смешение, необходимо направления покоординатных проб выбирать различными от этапа к этапу, например, случайным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
