§ 3.6. Глобальный поиск

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

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

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

годом становится все острее. Число возникающих многоэкстремальных задач неуклонно растет, особенно в области оптимального проектирования [21, 156, 209].

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

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