Эволюционная мультимодальная оптимизация

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

Мотивация

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

Предыстория

Классические методы оптимизации потребуют нескольких точек перезапуска и нескольких прогонов в надежде, что при каждом прогоне может быть обнаружено другое решение, однако без каких-либо гарантий. Эволюционные алгоритмы (ЭА) благодаря своему популяционному подходу обеспечивают естественное преимущество перед классическими методами оптимизации. Они поддерживают совокупность возможных решений, которые обрабатываются в каждом поколении, и если несколько решений можно сохранить на протяжении всех этих поколений, то при завершении работы алгоритма у нас будет несколько хороших решений, а не только лучшее решение. Обратите внимание, что это противоречит естественной тенденции классических методов оптимизации, которые всегда сходятся к лучшему или неоптимальному решению (в грубой, «плохо ведущей» функции). Поиск и поддержка нескольких решений — вот в чем заключается проблема использования советников для мультимодальной оптимизации. Нишевая деятельность это общий термин, обозначающий метод поиска и сохранения нескольких стабильных ниш или благоприятных частей пространства решений, возможно, вокруг нескольких решений, чтобы предотвратить сходимость к одному решению.

Область эволюционных алгоритмов охватывает генетические алгоритмы (ГА), стратегию эволюции (ES), дифференциальную эволюцию (DE), оптимизацию роя частиц (PSO) и другие методы. Во всех этих областях предпринимались попытки решить мультимодальную оптимизацию, и большинство, если не все методы реализуют нишу в той или иной форме.

генетических алгоритмов/стратегий

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

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

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

В статье предлагается подход, который не использует какой-либо радиус для разделения популяции на субпопуляции (или виды), а вместо этого использует пространственную топологию.

Продолжительность: 1 минута 27 секунд. 1:27

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

Библиография

• Д. Голдберг и Дж. Ричардсон. (1987) « Генетические алгоритмы с разделением для оптимизации мультимодальных функций ». В материалах Второй международной конференции по генетическим алгоритмам о генетических алгоритмах и оглавлении их применения, страницы 41–49. L. Erlbaum Associates Inc. Хиллсдейл, Нью-Джерси, США, 1987 г.
• А. Петровский. (1996) « Процедура очистки как метод ниш для генетических алгоритмов ». В материалах Международной конференции IEEE по эволюционным вычислениям 1996 г., страницы 798–803. Гражданин, 1996.
• Деб, К., (2001) «Многокритериальная оптимизация с использованием эволюционных алгоритмов», Уайли ( Google Книги)
• Ф. Штрайхерт, Г. Штайн, Х. Ульмер и А. Зелл. (2004) « Нишевый советник на основе кластеризации для мультимодальных пространств поиска ». Конспекты лекций по информатике, страницы 293–304, 2004 г.
• Сингх Г., Деб К. (2006) « Сравнение алгоритмов многомодальной оптимизации, основанных на эволюционных алгоритмах ». В материалах 8-й ежегодной конференции по генетическим и эволюционным вычислениям, страницы 8–12. АКМ, 2006.
• Ронкконен Дж. (2009). Непрерывная мультимодальная глобальная оптимизация с использованием методов дифференциальной эволюции
• Вонг, К.К. (2009). Эволюционный алгоритм с видовым взрывом для мультимодальной оптимизации. ГЕККО 2009: 923–930.
• Дж. Баррера и CAC Coello. « Обзор методов оптимизации роя частиц, используемых для мультимодальной оптимизации », страницы 9–37. Шпрингер, Берлин, ноябрь 2009 г.
• Вонг, К.К. (2010). Влияние пространственной локальности на эволюционный алгоритм мультимодальной оптимизации. EvoApplications (1) 2010: 481–490.
• Деб К., Саха А. (2010) Поиск множественных решений задач мультимодальной оптимизации с использованием многоцелевого эволюционного подхода. ГЕККО 2010: 447–454.
• Вонг, К.К. (2010). Прогнозирование структуры белка на решетчатой ​​модели с помощью методов мультимодальной оптимизации. ГЕККО 2010: 155–162.
• Саха А., Деб К. (2010), Двухкритериальный подход к мультимодальной оптимизации: самоадаптивный подход. ПЕЧАТЬ 2010: 95–104.
• Шир О.М., Эммерих М., Бэк Т. (2010), Адаптивные подходы к созданию ниш с использованием радиусов ниш и форм ниш с помощью CMA-ES. Эволюционные вычисления Том. 18, № 1, стр. 97-126.
• К. Стоан, М. Пройсс, Р. Стоэн, Д. Думитреску (2010) Мультимодальная оптимизация с помощью алгоритма сохранения топологических видов . В IEEE Transactions on Evolutionary Computing, Vol. 14, выпуск 6, страницы 842–864, 2010 г.
• С. Дас, С. Майти, Б.И. Цюй, П.Н. Сугантан, « Эволюционная мультимодальная оптимизация с реальными параметрами. Обзор современного состояния », Vol. 1, № 2, стр. 71–88, Swarm and Evolutionary Computation, июнь 2011 г.

Внешние ссылки

• Мультимодальная оптимизация с использованием Particle Swarm Optimization (PSO)
• Нишевые стратегии эволюции (ES)
• Страница мультимодальной оптимизации на кафедре 11 компьютерных наук Технического университета Дортмунда.
• Рабочая группа IEEE CIS по мультимодальной оптимизации