Рис. 28. К алгоритму с направляющим гиперквадратом

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

Таким образом на 1-м этапе координаты случайных точек удовлетворяют

неравенствам a1	≤ x ≤ b1	, i =1,...,n , и	x1 = arg min	{	f (x	j	)	– точка с минималь-
i	i i		j=1,m				}

ным значением целевой функции.

В алгоритме с обучением стороны гиперквадрата могут регулироваться в соответствии с изменением параметра α по некоторому правилу. В этом случае координаты вершин гиперквадрата на (k +1) -м этапе будут определяться соот-

ношениями

aik+1 = xik+1 − bik 2−αaik , bik+1 = xik+1 + bik 2−αaik .

Хорошо выбранное правило регулировки стороны гиперквадрата приводит

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

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

6.4. Алгоритмы глобального поиска

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

Алгоритм 1

В допустимой области D случайным образом выбирают точку x1 D .

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

кального минимума x1 D (рис. 29).

Затем выбирается новая случайная точка x2 D и по той же схеме ос у- ществляется спуск в точку локального минимума x2 D и т.д.

48

Рис. 29. Алгоритм 1 глобального поиска

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

Алгоритм 2

Пусть получена некоторая точка локального экстремума x1 D . После этого переходим к ненаправленному случайному поиску до получения точки x2

такой, что f (x2 )< f (x1 ).

Из точки x2 с помощью детерминированного алгоритма или направленного случайного поиска получаем точку локального экстремума x2 , в которой заведомо выполняется неравенство f (x2 )< f (x1 ).

Далее с помощью случайного поиска определяем новую точку x3 , для которой справедливо неравенство f (x3 )< f (x2 ), и снова спуск в точку локального

экстремума x3 и т.д.

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

Алгоритм 3

Пусть x10 – некоторая исходная точка поиска в области D , из которой осуществляется спуск в точку локального экстремума x1 со значением f (x1 ). Далее из точки x1 двигаемся либо в случайном направлении, либо в направлении x1 − x10 до тех пор, пока функция снова н е станет убывать (выходим из «области притяжения» x1 ). Полученная точка x20 принимается за начало следующего спуска. В результате находим новый локальный экстремум x2 и значением функции f (x2 ) (рис. 30).

Если f (x2 )< f (x1 ), точка x1 забывается и ее место занимает точка x2 . Если f (x2 )≥ f (x1 ), то возвращаемся в точку x1 и движемся из нее в новом случайном направлении.

49

Рис. 30. Алгоритм 3 глобального поиска

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

Этот метод позволяет найти глобальный экстремум в случае многосвязных допустимых областей.

Алгоритм 4

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

Рис. 31. Алгоритм 4 глобального поиска

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

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

50