3.6.2. «Блуждающие» алгоритмы

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

3.6.2.1. Метод «зашумления» градиента

Если на оценку градиента в градиентном поиске наложить вектор то получаем случайный поиск вида

где — некоторая постоянная. Запишем этот процесс в непрерывной форме:

где — случайный векторный процесс типа белого шума с единичными дисперсиями. При поиск является

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

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

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

Как видно, этот алгоритм гарантирует отыскание глобального экстремума лишь при очень медленном уменьшении параметра о (строго говоря, для этого нужна нулевая скорость убывания о). Риск не найти глобальный экстремум тем выше, чем больше скорость уменьшения о.

3.6.2.2. Метод сглаживания

Если минимизируемая функция имеет вид, показанный на рис. 3.6.1, а, т. е. образована путем наложения на «хорошую» унимодальную функцию (см. пунктир на рисунке) мелких случайных отклонений, то для отыскания глобального экстремума можно воспользоваться идеей сглаживания [103, 152, 238]. Делается это следующим образом.

В районе точки осредним функцию с неотрицательным весом поведение которого показано на рис. 3.6.1, б. Получаем

Эта функция уже ближе к «хорошей», так как здесь несколько сглажена колебательная составляющая. Однако определить этот -кратный интеграл очень трудно. Указанную трудность можно преодолеть, если для его вычисления воспользоваться методом Монте-Карло, рассмотренным в § 3.1. Действительно, весовую

Рис. 3.6.1. Сглаживание многоэкстремальной функции а — многоэкстремальная функция, образованная наложением случайных колебаний на унимодальную функцию (пунктирная линия); б - весовая функция.

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

Тогда, генерируя в соответствии с этой плотностью случайные векторы можно оценить значение интересующего нас интеграла следующим образом:

Выражение (3.6.11) есть монте-карловская оценка, совпадающая с (3.6.10) при и отличающаяся от (3.6.10) при конечном на случайную величину с нулевым средним и дисперсией порядка Отсюда вытекает возможность подбирать объем случайной выборки таким образом, чтобы свойства оценки (3.6.11) были приемлемыми.

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

где значение определяется путем оценивания по (3.6.11), что, как видно, эквивалентно оптимизации в обстановке случайных помех.

Воспользуемся градиентным методом и для простой оценки градиента получим аналитический вид распределения

Для этого преобразуем интеграл (3.6.10) с помощью подстановки к виду

(3.6.13) Градиент функции можно определить следующим образом:

где операция вычисления градиента осуществляется аналитически. Оценивать (3.6.14) следует также методом Монте-Карло:

где — случайные реализации вектора распределенного в соответствии с заданной плотностью для

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

3.6.2.3. Метод направляющего конуса

Очень часто глобальный экстремум находится на «дне» оврага минимизируемой функции Под оврагом принято понимать ситуацию, отличающуюся следующей особенностью: почти вдоль всех направлений функция сильно увеличивается (это «склоны» оврага), и только в сравнительно узком конусе направлений эта функция слабо уменьшается (это направление «дна» оврага). Если глобальный экстремум лежит на дне такого оврага, то следует воспользоваться методом случайного поиска, называемым поиском с направляющим конусом. Суть его состоит в следующем.

На специфическом дне конуса с вершиной в и осью делаются к случайных проб (рис. 3.6.2). Следующее состояние определяется по наилучшей пробе:

Рис. 3.6.2. К образованию рабочего шага алгоритмом случайного поиска с направляющим конусом.

а ось следующего конуса —

т. е. вдоль сделанного рабочего шага. Легко видеть, что эта процедура позволяет отслеживать направление оврага независимо от того, вверх или вниз идет овраг.

Угол между следующими друг за другом шагами не превышает половины угла раскрытия направляющего конуса. Поэтому траектория поиска при малом имеет очень плавный характер. При получаем поиск по наилучшей пробе, рассмотренный в подразделе 3.3.2.3. Варьируя величину угла можно получить адаптивные процедуры овражного глобального поиска [94].

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