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

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

(

), определенного в

-мерном евклидовом пространстве

(1)

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

. Пусть

- вектор координат центра гиперсферы,

- радиус гиперсферы,

- вектор с началом в точке

и концом в искомой точке на поверхности гиперсферы,

- углы между вектором

и ортами координатных осей

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

, может быть представлена в следующем виде:

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

Упрощенная схема метода случайного поиска с постоянным радиусом поиска и случайными направлениями.

Задаем начальную точку , начальный радиус гиперсферы , и полагаем счетчик числа итераций =0.
Генерируем случайные точки , [1, ] равномерно распределенные по поверхности гиперсферы радиуса с центром в точке . Здесь – количество точек – свободный параметр метода.
Вычисляем значения минимизируемой функции () в полученных точках и находим точку, в которой достигается минимальное значение функции ():

Каким-либо из рассмотренных в главе 4 одномерных методов оптимизации (например, методом Паулла) находим минимум функции () в направлении :
Проверяем условие окончания итераций (см. ниже). Если условие окончания выполнено, то полагаем и завершаем итерации. Иначе - принимаем =+1 и переходим к п.2

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

где

- константа, определяющая требуемую точность решения по

;

где

- константа, определяющая требуемую точность решения по

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

В процессе поиска радиус гиперсферы может меняться, увеличиваясь при удачных шагах (вдали от точки

) и уменьшаясь при неудачных шагах (вблизи от точки

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

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

Рис. 1. Траектория поиска минимума функции Химмельблау методом случайного поиска с постоянным радиусом поиска и случайными направлениями (n=2).

На рисунке точки, лежащие на окружности с центром в точке

, соответствуют случайным точкам

[1,

Примечание 1

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

(см. параграф 6.4).

Рис. 2. Один шаг поиска в направлении антиградиента минимизируемой функции (∇Φ(X^r)) приводит на линию уровня (1.5). В то же время одна итерация по методу случайного поиска с постоянным радиусом поиска и случайными направлениями – на линию уровня ~0.2. Точки на окружности с центром в точке X^r соответствуют случайным точкам. Любое направление поиска в секторе β лучше, чем направление антиградиента.