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

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

Рассмотрим некоторые подходы к поиску глобального экстремума.

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

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

Рис.

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

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

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

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

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

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

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

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

Рис.

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

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

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

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

Рис.

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

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