Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

являются параметрами алгоритма. Вектор рп называют статисти­ ческим градиентом. Если U = E m, s — m и векторы ^ я вл я ю тся не­ случайными и совпадают с соответствующими единичными вектора­ ми в {= ( 0 , . . , 0, 1, 0 , . . , 0), £ =1 , 2 , . . , /п, то описанный алгоритм,

как нетрудно видеть, превращается в разностный аналог градиент­ ного метода.

2. В описанных вариантах а), б), в) метода случайного пои ка предполагается, что закон распределения случайного вектора £ не зависит от номера итераций. Такой поиск называют случайным поиском без обучения. Алгоритмы случайного поиска без обучения не обладают «способностью» анализировать результаты предыду­ щих итераций и выделять, направления, более перспективные в смысле убывания минимизируемой функции, и сходятся, вообще го­ воря, медленно.

Между тем ясно, что от метода случайного поиска можно ожи­ дать большей эффективности, если на каждой итерации учитывать накопленный опыт поиска минимума на предыдущих итерациях и перестраивать вероятностные свойства поиска так, чтобы направле­ ния £, более перспективные в смысле убывания функции, станови­ лись более вероятными. Иначе говоря, желательно иметь алгорит­ мы случайного поиска, которые обладают способностью к самообу­ чению и самоусовершенствованию в процессе поиска минимума' в зависимости от конкретных особенностей минимизируемой функ­ ции. Такой поиск называют случайным поиском с обучением [204].

Обучение алгоритма осуществляют посредством целенаправленного изменения закона распределения случайного вектора £ в зависимо­ сти от номера итерации и результатов предыдущих итераций таким образом, чтобы «хорошие» направления, по которым функция убы­ вает, стали более вероятными, а другие направления — менее ве­ роятными. Таким образом, на различных этапах метода случайного поиска с обучением приходится иметь дело с реализациями случай­ ных векторов | с различными законами распределения. Имея в ви­

минимизируемой функции. Если такая информация отсутствует, то поиск обычно начинают от случайного вектора = (|о, ••■, £сГ),

компоненты |о,£= 1, 2 , . . . , пг, которого представляют собой незави­ симые случайные величины, распределенные равномерно на отрез­

§ 12] О методе случайного поиска и некоторые других методах 151

ке [— 1, 1]. Для обучения алгоритма в процессе поиска часто берут

точке « „ _ 1 привел к уменьшению значения функции, то вероятность выбора направления ип- Х— и„_2 на следующем шаге увеличивается. И наоборот, если при переходе от ип- 2 к i значение функции увеличится, то вероятность выбора направления ип- 1— ип- 2 на сле­ дующем шаге уменьшается. Таким образом, формулы (4) осуще­ ствляют обучение алгоритма. Величина 6 ^ 0 в (4) регулирует ско­ рость обучения: чем больше 6 > 0 , тем быстрее обучается алгоритм; при 6 = 0, как видно, обучения нет. Величина в формулах (4) регулирует влияние предыдущих значений параметров на обуче­ ние алгоритма; при |3 = 0 алгоритм «забывает» предыдущие значе­

152 МИНИМИЗАЦИЯ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ [Гл. 2

ния шл_|. Для устранения возможного чрезмерного детерминиро­ вания алгоритма и сохранения способности алгоритма к достаточно'

ci являются параметрами алгоритма.

Вместо формул (4), посредством которых производится обу­

Описанный алгоритм покоординатного обучения имеет тот не­ достаток, что поиск и обучение происходят лишь по одному из 2т направлений £ = (|‘, . . . , £т ), где либо £’ = 1 , либо £* = — 1. Отсутст­ вие «промежуточных» направлений делает покоординатное обуче­ ние немобильным в областях с медленно изменяющимися направ­ лениями спуска. От этого недостатка свободен следующий алго­ ритм.

б) Алгоритм непрерывного самообучения [204]. Пусть имее

чайный вектор, координаты rf которого представляют собой неза­ висимые случайные величины, распределенные равномерно на отрезке [ - U ] . Поиск начинается с рассмотрения случайных векторов £о = £(0), £i = £(0), реализации которых используются при определении приближений u0, ut по формулам (2). Обучение алгоритма при 2 призводится так же, как в алгоритме поко­ ординатного обучения, с помощью формул (4) или (5). При боль­

близким к направлению шп. Во избежание излишней детермини­

Более подробные рассмотрения различных вариантов метода случайного поиска, их сравнительные характеристики, вычисли­ тельные аспекты метода случайного поиска см. в работах [79],. [204].

3. Приведенные алгоритмы случайного поиска с обучение показывают, что процесс обучения в ходе поиска сопровождается уменьшением фактора случайности и увеличением степени детер­ минированности алгоритма поиска минимума, направляя поиск.

возможность алгоритму «переучиваться», если свойства функции в районе поиска изменились или предыдущее обучение было не­ точным. Случайный поиск с обучением в некотором смысле зани­ мает промежуточное положение между случайным поиском без обучения и детерминированными методами поиска минимума из предыдущих параграфов. Разумеется, и в методах предыдущих параграфов можно обнаружить в том или ином виде элементы самообучения алгоритма, однако наличие случайного фактора в алгоритме делает метод случайного поиска более гибким и поэто­ му более приспособленным к поиску минимума многоэкстремаль­ ных функций, т. е. функций со многими глобальными и локальны­ ми минимумами в рассматриваемой области.

Следует сказать, что задача отыскания глобального миниму­ ма многоэкстремальных функций существенно более трудна, и ме­ тоды решения таких задач в настоящее время разработаны недо­ статочно. Для изучения поведения многоэкстремальных функций и

здесь можно предложить метод, обобщающий метод ломаных из главы 1, однако его реализация с возрастанием размерности про­ странства весьма усложняется [85]. Другие методы минимизации многоэкстремальных функций изложены в работах [103, 174, 214].

4.Весьма усложняет решение задачи минимизации функц

многих переменных наличие помех, когда на значения функции J (и) в каждой точке и накладываются случайные ошибки. В этих случаях можно использовать метод стохастической аппроксимации

([45, 79, 230] и др.). Одним из вариантов этого метода является процедура Кифера — Вольфовица, краткое описание которой бы­ ло дано в § 1.12 применительно к задачам минимизации функций одной переменной. Для функций m переменных эта процедура приводит к построению последовательности {«„} по закону

Z О/, + С„е,) — Z (и„ — с„е,)

Un-\-1 —

Сп

i = 1, 2, . . . , m; п = 0, 1, . . . ,

где = ( 0 , . . . , 0, 1, 0 , . . . , 0), z(u) — наблюдаемые в эксперимен­ те значения функции J (и) в точке и, последовательности {а„}, {с„} удовлетворяют условиям (1.12.2). Различные варианты мето­ да стохастической аппроксимации, строгое обоснование этого ме­ тода и различные приложения можно найти в работе [45]. Для минимизации функции при наличии помех могут быть использо­ ваны также метод случайного поиска [204] и некоторые другие методы [ПО, 214].