Высокоэффективные алгоритмы глобальной оптимизации

В ННГУ им. Н.И. Лобачевского разработан (в рамках единого подхода) ряд эффективных алгоритмов глобальной оптимизации; все они вошли в программную систему Globalizer.

Основными особенностями разработанных методов являются:

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

Лежащий в основе разработанной программной системы Globalizer информационно-статистический алгоритм глобального поиска (АГП) превосходит многие известные методы аналогичного назначения. Для иллюстрации на рис. 1 изображены линии уровня двумерной многоэкстремальной функции и отмечены точки поисковых испытаний, выполненных АГП (рис. 1(а), 130 испытаний) и методом DIRECT (рис. 1(б), 269 испытаний) до достижения заданной точности.

Рис. 1(а) Рис. 1(б)

Результаты сравнения АГП с некоторыми другими алгоритмами (метод ломаных, метод Кушнера, одношаговый байесовский метод) приведены на рис. 2. Сравнение алгоритмов проводилось при решении серии случайно генерируемых задач многоэкстремальных задач. Результат представлен операционной характеристикой P(k), характеризующей долю задач серии, для которых в ходе k шагов поиска имели место попадания точек поисковых испытаний в заданную окрестность решения.

 

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