Глобальный случайный поиск с гиперсферой и направляющим гиперконусом

Этот алгоритм реализует идею Л. А. Растригина «Глобальный поиск как поиск с самообучением» [2].

Зададимся некоторым произвольным начальным вектором X^х е V. Из точки Х‘ сделаем т независимых случайных проб (здесь и в дальнейшем верхний индекс при X — номер точки допустимой области пространства К, а не компоненты вектора):

где а — постоянная величина (шаг поиска); «случайный, равномерно распределенный на отрезке [-1, +1] вектор, нормированный так, чтобы.

Оптимальным значением т считается величина размерности вскто;

_*.

pa X, т. е. т = п. Из этой совокупности проб выберем точку X¹ + а •^, _*.

где? — направление наилучшей пробы, удовлетворяющей условию.

—*.

Две точки X^х и X^х + а • ?, определят вектор W_j9 который назовем вектором памяти. На этом векторе, как на оси, построим гиперконус с углом раскрытия 2|/ и вершиной в точке X^х. Из вершины конуса проведем гиперсферу радиуса а. Гиперконус отсечет от гиперсферы часть поверхности, на которой вновь сделаем т независимых случайных проб. Из этих проб выбирается точка, удовлетворяющая условию (1.13). Каждый раз вершина конуса переносится в выбранную точку, а вектор W- меняет свое направление. Процесс поиска продолжается циклически (рис. 1.16).

На каждом шаге поиска проверяется условие.

при выполнении которого точка A^r,_1 отмечается как «подозрительная» на минимум. Движение продолжается на подъем, но угол раскрытия направляющего конуса уменьшается вдвое, чтобы придать поиску большую инерционность и предотвратить «сползание» в уже обнаруженный минимум. После перехода через «перевал»:

угол раскрытия конуса восстанавливается.

Если в процессе поиска произойдет выход к-й компоненты вектора IV. за пределы допустимой области, то направление вектора будет выбираться из условия.

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

Рис. 1.16. Движение поиска в пространстве управлений при оптимизации алгоритмом с направляющим конусом (т = п = 2)

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