Обзор современных эвристических методов оптимизации

Предисловие

Доброго времени суток, дорогие Хабаровчане.

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

• большие размерности,
• нелинейность,
• мультимодальность.

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

Гармонический поиск

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

Искусственные иммунные системы

Как ясно из названия, методы будут имитировать принципы иммунологических теорий. На данный момент к этому классу алгоритмов относят следующие:

• алгоритмы клональной селекции,
• алгоритм негативного отбора,
• иммунные сети,
• алгоритмы дендрических клеток.

Гравитационный поиск

Предложенный Рашеди с соавторами в 2009 году алгоритм гравитационного поиска (GS) инспирирован поведением тяжелых тел при их гравитационном взаимодействии. Данный алгоритм является развитием алгоритма оптимизации центральной силой (CFO). Главное отличие GS — его стохастическая природа (в отличие от детерминированности CFO).

Scatter Search

В основе метода разбросанного поиска (scatter search) лежит обработка множества элементарных исходов, состоящих из найденных хороших точек. Фактически обработка заключается в комбинации, улучшении и обновлении множества элементарных исходов. В основе данного метода лежат пять операций:

• метод генерации разнообразных решений,
• метод улучшения решений,
• метод обновления множества элементарных исходов,
• метод генерации подмножеств,
• метод комбинации решений.

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

Метод перекрестной энтропии

Впервые данный метод был предложен Рубенштейном в 1997 году. Изначально он был разработан для решения задач комбинаторной оптимизации, хотя позже был применен и для оптимизации непрерывных функций. Основная особенность метода заключается в апробировании точек исследуемого на оптимум пространства и аппроксимации распределения хороших точек (обычно нормальным законом). На каждом шаге алгоритма в соответствии с текущим распределением генерируются случайные точки, которые впоследствии участвуют в корректировке распределения. По ходу выполнения алгоритма, распределение становится все более «чистым» и устоявшимся, что впоследствии позволяет выбрать приближенное решение задачи оптимизации.

Послесловие

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