Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 3
Текст из файла (страница 3)
Но в этом случае метод градиента превращается в метод случайного поиска с ортогональными пробами. Алгоритм этого поиска может быть записан в следующей форме: (1.5.5) АХ=а йг У, 14 где У вычисляется по (1.5.3), а пробы Х; берутся вдоль координатных осей, причем номера координат 1~!==--и не совпадают и на каждом этапе выбираются по жребию.
Расширением этого метода может служить алгоритм с ортогональнымн пробами, берущимися в произвольных направлениях (3). Это означает, что пробные состояния Х; случайны и удовлетворяют следующим ортогональным ограничениям: (Х,-Х„Х,— Х,) =О (1.5.5) при 1 -!чьу~н!, где скобками обозначено Скалярное произведение векторов.
Из сказанного видно, что два последних алгоритма случайного поиска ие укладываются в схему алгоритма статистического градиента, описанную в начале этого параграфа, хотя и являются, безусловно, алгоритмами этого класса. Для того чтобы и этн алгоритмы уложить в указанную схему, достаточно потребовать выполнения определенных ограничений, накладываемых на случайный выбор пробного состояния внутри гиперконуса. Тогда. например, последний алгоритм будет соответствовать случаю а.=п с ограничением (!.5.6). Как видно, рассмотренная схема алгоритма статистического градиента достаточно обща.
Изменяя ограничения и варьируя параметры а, лг, можно получить различные алгоритмы (статистические и регулярные), удовлетворяющие широкому классу треоований. Расширяя далее эту схему, можно поставить задачу об адаптационном алгоритме статистического градиента, смысл которого заключается в том, чтобы последующие пробы располагались в зависимости от предыдущих.
Пусть имеется ш-! проба Хь...,Х„, ь Требуется определить положение т-й пробы Х, например, так, чтобы при этом оценка градиента была бы наилучшей, т. е. чтобы л ) пгаг! Я вЂ” пгад,.„, О~ =пп(п, ((,5.7) где йтад Я вЂ” оценка градиента функции качества на базе лг проб. Решение этой задачи следует искать в форме условной плотности распределения пробного состояния р(Х„!Хь..., Х„,,).
(!.5.8) Прн определенных структурах функции качества в районе поиска это распределение может вырождаться в дельта-функцию, т. е. оптимальный алгоритм адаптационного поиска может быть в некоторых случаях регулярным. Однако в общем случае, когда сведения о структуре функции качества ограничены (именно этот случай чаще всего и встречается на практике— иначе не нужен был бы поиск), следует ожидать, что оптимальным алгоритмом будет случайный поиск. й Кв.
АЛГОРИТМЫ СПУСКА Алгоритмы спуска представляют собой очень компактную группу алгоритмов, в которой близость регулярных и случайных методов поиска проявляется наиболее рельефно. Рассмотрим некоторые из них. !3 Алгоритм Гаусса — Зайделя, как известно, заключается ворганизацни спуска последовательно вдоль направлений всех координатных осей. Этот алгоритм легко обобщается стохастическим. Для этого достаточно направления спуска определять случайным ооразом, например, так же, как в статистическом градиенте (см. В 1.5). При а=О такой алгоритм вырождается в метод Гаусса — Зайделя, а при и- оо — в случайный спуск: /Л)(; при цЯ.=О; (аЕ при ЛЯ= О.
(! .6.1) (1.6.2) Ю,„=б( (В,— бЛХ,Л0,). Как видно, этот алгоритм является одним из алгоритмов самообучения, который позволяет коррекэировать каждый шаг спуска и тем самым добиваться улучшения процесса поиска. Очевидно, что при а=О этот поиск вырождается в градиентный спуск. Естественно определить оптимальное значение а,„„оптимизирующее поиск по заданному критерию. Если это значение щ Если в качестве пробного направления спуска выбирать какую-либо статистическую оценку градиентного направления методом статистического градиента или методом наилучшей пробы, то получим алгоритмы спуска, аналогичные методу наискорейшего (градиентного) спуска. Разница будет лишьвтом, что в последнем случае спуск (без помех) производится точно в направлении антиградиепта, а при статистическом спуске— в направлении его статистической оценки.
Выигрыш статистического метода по сравнению с градиентным заключается в том, что он дает возможность начать спуск раньше, хотя и не в наилучшем направлении. Суммарный эффект зависит от особенностей объекта. Статистическое расширение алгоритмов можетпроизводиться за счет введения случайного отклонения в сам процесс спуска. Для этого достаточно рассмотреть спуск с направляющим конусом (41.
Из исходного состояния с осью в направлении вектора памяти % строится гиперконус с углом полураскрытия а. Внутри этого конуса на расстоянии а от исходной точки произ. вольно выбирается состояние, в котором определяется значение функции качества. Приращение качества ЛЯ по сравнению с исходной точкой определяет успешность движения в этом направлении.
Поэтому, имея эту информацию, можно произвести коррекцию вектора памяти, например, следующим образом: не будет равным нулю, то это означает, что в данной ситуации указанный случайиын поиск является оптимальным среди всех алгоритмов этого класса. Проведенные в этом направлении исследования показали (4), что для объектов определенного класса а ФО. й Кт.
ОБОБЩЕННЫЕ АЛГОРИТМЫ В заключение отметим, что изложенные соображения могут лечь в основу синтеза обобщенных алгоритмов, объединяющих целые классы регулярных и случайных алгоритмов. Эти обобщенные алгоритмы должны иметь статистический характер. В качестве примера построим обобщенный алгоритм, объединяющий регулярные методы Гаусса — -Зайделя и градиентного спуска. Он имеет вид: /ЛХи — ь если ЛЯ =О; '1а У, если ЛЯ) О, (1.7.1) где т' — направление спуска, которое определяется по формуле (1.7.2) Здесь а~ — число проб; В7 — направление /-й пробы; Л٠— приращение функции качества на 1-й пробе.
Пробные шаги определяются следующим образом: В; = п1Г ( Ей+7+ п2В), (1.7.3) где Š— по-прежнему единичный случайный вектор, равномерно распределенный по всем направлениям пространства параметров; аз — параметр меры стохастичности алгоритма; Еа+;— единичный вектор вдоль координатной оси с номером той (А+1); где й=ааь а г — число предыдущих определений направления спуска. Варьируя параметры а~ и ам можно получить различные алгоритмы — они сведены в табл.
1, где полужирными цифрами отмечены следующие известные методы поиска: !. Алгоритм Гаусса — Зайделя. 2, Алгоритм градиентного (наискорейшего) спуска. 3. Алгоритм спуска при оценке градиента не по всем координатным осям (усеченный градиентный спуск). 4. Алгоритм случайного спуска. 5. Алгоритм спуска по статистической оценке градиента. 6.
Алгоритм переорганизованного градиентного спуска (т. е. число проб в данном случае превышает необходимое). Очевидно, что эффективность алТз блика ! горитма по выбранному критерию зависит от параметров а! и ам Вобщ щем случае эта зависимость имеет следующпи внд О ! ед>0 К!=К!(а!, аь... „а„), (!.7.4) ! 1 4 где К! — Рй! критерий оценки эффективности обобщенного алго- 2 ритма; а!, аь..., ар -- параметры этого алгоритма. Тогда задача синтеза оптимального алгоритма для заданной ситуации будет заключаться в поиске а — 1 ! в пространстве обобщенных параметров (а!,..., ар) точки, оптимизирующей выбранный критерий (1.7.4) при выполнении ограниче! ° ний, наложенных па другие критерии.
Регулярные алгоритмы понскз а в этом пространстве представляются в виде точек, линий или гиперповерхностей. Резюмируя сказанное, можем утверждать, что статистические методы обобщают регулярные и расширяют возможности поиска вообще. Общую теорию поиска, по-видимому, следует строить, опираясь на статистический подход, который, как показано выше, позволяет объединить регулярный н статистический методы поисковой оптимизации сложных многопараметрических систем.
ГЛАВА Н НЕРЕШЕННЫЕ ПРОБЛЕМЫ СЛУЧАИНОГО ПОИСКА й 2.1. ВВЕДЕНИЕ В начале шестидесятых годов начинает очень сильно развиваться теория автоматического управления, особенно теория оптимального управления. Это относится к детерминистическим методам, применяемым к известной математической модели управляемого объекта, пе подверженного воздействию помех. Почти параллельно начинают развиваться случайные — вероятностные — методы оптимального управления, Эти методы— как показали дальнейшие исследования — имеют свои преимущества при учете воздействия помех на многопараметрический объект «1, 21. В последней работе приводятся основные, решенные главным образом в СССР, проблемы: а) непрерывные алгоритмы случайного поиска; б) дискретный случайный поиск — без помехи; в) дискретный случайный поиск — с помехой; г) обучение в процессе случайного поиска; д) идентификация систем методом случайного поиска; е) применение теории адаптивного случайного поиска.
$22. МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ЗАДАЧИ СЛУЧАЙНОГО ПОИСКА Метод случайного поиска состоит в определении поведения системы в будущем на основе ее состояния в настоящий момент или ее состояний в предыдущие моменты времени, которые выражены вероятностными характеристиками. Идея. на которой базируется этот метод, принадлежит У.
Р. Эшби, разработавшему теорию гомсостата (устройство, обеспечивающее устойчивое состояние при любых помехах). Фиксированное состояние гомеостата обеспечивается прямо или косвенно нз основе вытекающего из предыдущей деятельности опыта. Рис. 2Л. !!риведем математическую формулировку случайного поиска в терминах теории оптимальногоуправления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
