Простейшие алгоритмы направленного случайного поиска

Алгоритм парной пробы.В данном алгоритме четко разделены пробный и рабочий шаги.

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

Рабочий шаг делается в направлении наи­меньшего значения целевой функции. Очередное приближение определяется соотношением

.

Рис.

Особенностью данного алгоритма является его повышенная тенденция к “блужданию”. Даже найдя экстремум, алгоритм может увести процесс поиска в сторону.

Алгоритм наилучшей пробы. На -м шаге мы имеем точку . Генерируется случайных единичных векторов . Делаются пробные шаги в на­правлениях и в точках вычисляются значения функции. Выбирается тот шаг, который приводит к наибольшему уменьшению функции: . И в данном направлении де­ла­ется шаг

.

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

С увеличением числа проб выбранное направление приближается к направлению .

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

Рис.

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

.

После этого формируем векторную сумму

.

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

.

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

Рис.

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

Опираясь на эту точку, строим новый гиперквадрат. Точка, в которой достигается минимум функции на -м этапе, берется в качестве центра нового гиперквадрата на -м этапе.

Рис.

Координаты вершин гиперквадрата на -м этапе определяются соотношениями

, ,

где – наилучшая точка в гиперквадрате на -м этапе.

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

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

, .

Хорошо выбранное правило регулирования стороны гиперквадрата приводит к достаточно эффективному алгоритму поиска.

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