Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии о
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

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

Мотивация [ править ]

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

Фон [ править ]

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

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

Мультимодальная оптимизация с использованием генетических алгоритмов / стратегий эволюции [ править ]

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

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

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

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

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

Ссылки [ править ]

  1. ^ Вонг, KC (2015), Эволюционная мультимодальная оптимизация: краткий обзор arXiv препринт arXiv: 1508.00457
  2. ^ Шир, OM (2012), Niching в эволюционных алгоритмах Архивированных 2016-03-04 в Wayback Machine
  3. ^ Прейсс, Майк (2015), Мультимодальная оптимизация с помощью эволюционных алгоритмов
  4. ^ Wong, KC et al. (2012), Эволюционная мультимодальная оптимизация с использованием принципа локальности Информационные науки
  5. ^ Махфуд, SW (1995), " Методы Ничинга для генетических алгоритмов "
  6. ^ Шир, О.М. (2008), " Ничинг в дерандомизированных стратегиях эволюции и их приложениях в квантовом управлении "
  7. ^ Деб, К., Саха, А. (2010) « Нахождение множественных решений для задач мультимодальной оптимизации с использованием многоцелевого эволюционного подхода » (GECCO 2010, в печати)
  8. ^ Саха, А., Деб, К. (2010) «Двухкритериальный подход к мультимодальной оптимизации: самоадаптивный подход» (конспекты лекций по информатике, 2010 г., том 6457/2010, 95–104)
  9. ^ C. Стоуан, М. Прейсс, Р. Стоуан, Д. Думитреску (2010) Мультимодальная оптимизация с помощью алгоритма сохранения топологических видов . В IEEE Transactions on Evolutionary Computing, Vol. 14, выпуск 6, страницы 842–864, 2010 г.

Библиография [ править ]

  • Д. Голдберг и Дж. Ричардсон. (1987) " Генетические алгоритмы с совместным использованием для оптимизации мультимодальных функций ". В материалах Второй международной конференции по генетическим алгоритмам, посвященным генетическим алгоритмам и их применению, оглавление, страницы 41–49. Л. Эрлбаум Ассошиэйтс Инк. Хиллсдейл, Нью-Джерси, США, 1987.
  • А. Петровский. (1996) " Процедура очистки как метод определения генетических алгоритмов ". В материалах Международной конференции IEEE 1996 г. по эволюционным вычислениям, страницы 798–803. Citeseer, 1996.
  • Деб, К., (2001) «Многоцелевая оптимизация с использованием эволюционных алгоритмов», Wiley ( Google Книги)
  • Ф. Штрайхерт, Г. Штейн, Х. Ульмер и А. Целл. (2004) " Niching EA на основе кластеризации для многомодальных пространств поиска ". Конспект лекций по информатике, страницы 293–304, 2004 г.
  • Сингх, Г., Деб, К., (2006) " Сравнение мультимодальных алгоритмов оптимизации, основанных на эволюционных алгоритмах ". В материалах 8-й ежегодной конференции по генетическим и эволюционным вычислениям, страницы 8–12. ACM, 2006.
  • Ронкконен, Дж. (2009). Непрерывная мультимодальная глобальная оптимизация с помощью методов, основанных на дифференциальной эволюции
  • Вонг, KC, (2009). Эволюционный алгоритм с видоспецифическим взрывом для мультимодальной оптимизации. GECCO 2009: 923–930
  • Дж. Баррера и САС Коэльо. « Обзор методов оптимизации роя частиц, используемых для мультимодальной оптимизации », страницы 9–37. Спрингер, Берлин, ноябрь 2009 г.
  • Вонг, KC, (2010). Влияние пространственной локальности на эволюционный алгоритм мультимодальной оптимизации. EvoApplications (1) 2010: 481–490.
  • Деб К., Саха А. (2010) Нахождение множественных решений для задач мультимодальной оптимизации с использованием многоцелевого эволюционного подхода. GECCO 2010: 447–454
  • Вонг, KC, (2010). Прогнозирование структуры белка на решетчатой ​​модели с помощью методов мультимодальной оптимизации. GECCO 2010: 155–162
  • Саха А., Деб К. (2010), Двухкритериальный подход к мультимодальной оптимизации: самоадаптивный подход. SEAL 2010: 95–104
  • Шир, О.М., Эммерих, М., Бэк, Т. (2010), Подходы к адаптивным радиусам и формам ниши для нишинга с помощью CMA-ES. Эволюционные вычисления Vol. 18, No. 1, pp. 97-126.
  • К. Стоуан, М. Прейсс, Р. Стоуан, Д. Думитреску (2010) Мультимодальная оптимизация с помощью алгоритма сохранения топологических видов . В IEEE Transactions on Evolutionary Computing, Vol. 14, выпуск 6, страницы 842–864, 2010 г.
  • S. Das, S. Maity, BY Qu, PN Suganthan, " Эволюционная мультимодальная оптимизация с действительными параметрами - Обзор современного состояния ", Vol. 1, № 2, стр. 71–88, Swarm and Evolutionary Computing, июнь 2011 г.

Внешние ссылки [ править ]

  • Мультимодальная оптимизация с использованием оптимизации роя частиц (PSO)
  • Ничинг в Evolution Strategies (ES)
  • Страница мультимодальной оптимизации на кафедре 11, компьютерные науки, Технический университет Дортмунда
  • Целевая группа IEEE CIS по мультимодальной оптимизации