Экстремальная оптимизация (ЭО) является оптимизация эвристический вдохновлен моделью Bak-Sneppen из самоорганизованной критичности из области статистической физики. Эта эвристика изначально была разработана для решения задач комбинаторной оптимизации, таких как задача коммивояжера и спиновые очки , хотя было продемонстрировано, что этот метод работает в областях оптимизации.
Отношение к самоорганизованной критичности
Самоорганизованная критичность (SOC) - это концепция статистической физики для описания класса динамических систем, которые имеют критическую точку в качестве аттрактора. В частности, это неравновесные системы, которые развиваются через лавины изменений и диссипации, достигающие самых высоких масштабов системы. Считается, что SOC управляет динамикой некоторых природных систем, в которых наблюдаются подобные всплески явления, включая формирование ландшафта, землетрясения, эволюцию и гранулярную динамику кучи риса и песка. Особый интерес здесь представляет модель Бака-Снеппена SOC, которая способна описывать эволюцию через прерывистое равновесие (события вымирания) - таким образом, моделируя эволюцию как самоорганизованный критический процесс.
Отношение к вычислительной сложности
Еще одна часть головоломки - это работа над вычислительной сложностью, в частности, было показано, что критические точки существуют в NP-полных задачах, где почти оптимальные решения широко разбросаны и разделены барьерами в пространстве поиска, что приводит к зависанию алгоритмов локального поиска или сильно затруднено. Именно эволюционная модель самоорганизованной критичности Бака и Снеппена и наблюдение критических точек в задачах комбинаторной оптимизации привели к разработке Стефаном Ботчером и Аллоном Перкусом экстремальной оптимизации.
Техника
EO был разработан как алгоритм локального поиска для задач комбинаторной оптимизации . В отличие от генетических алгоритмов , которые работают с популяцией возможных решений, EO развивает единое решение и вносит локальные изменения в худшие компоненты. Для этого необходимо выбрать подходящее представление, позволяющее присвоить отдельным компонентам решения показатель качества («соответствие»). Это отличается от холистических подходов, таких как оптимизация муравьиных колоний и эволюционные вычисления, которые приписывают одинаковую пригодность всем компонентам решения на основе их коллективной оценки по отношению к целевой функции. Алгоритм инициализируется начальным решением, которое может быть построено случайным образом или получено из другого процесса поиска.
Эта техника представляет собой мелкозернистый поиск и внешне напоминает технику восхождения на холм (локальный поиск). Более подробное изучение раскрывает некоторые интересные принципы, которые могут иметь применимость и даже некоторое сходство с более широкими популяционными подходами ( эволюционные вычисления и искусственная иммунная система ). Основным принципом этого алгоритма является улучшение путем выборочного удаления некачественных компонентов и их замены случайно выбранным компонентом. Это явно противоречит генетическим алгоритмам , типичному алгоритму эволюционных вычислений, который выбирает хорошие решения в попытке найти лучшие решения.
Результирующая динамика этого простого принципа - это, во-первых, устойчивое поведение поиска с подъемом на холм, а во-вторых, механизм разнообразия, напоминающий поиск с многократным перезапуском. График качества целостного решения с течением времени (итерации алгоритма) показывает периоды улучшения, за которыми следуют ухудшения качества (лавины), очень похоже на то, как это описывается прерывистым равновесием . Именно эти сбои или резкие скачки в пространстве поиска позволяют алгоритму избегать локальных оптимумов и отличать этот подход от других процедур локального поиска. Хотя такое поведение прерывистого равновесия может быть «спроектировано» или «жестко закодировано», следует подчеркнуть, что это возникающий эффект принципа выбора отрицательных компонентов, фундаментального для алгоритма.
ЭО в основном применялся к комбинаторным задачам, таким как разбиение графа и задача коммивояжера , а также к задачам статистической физики, таким как спиновые очки .
Вариации по теме и приложениям
Обобщенная экстремальная оптимизация (GEO) была разработана для работы с битовыми строками, где качество компонентов определяется абсолютной скоростью изменения бита или вкладом битов в целостное качество решения. Эта работа включает применение к стандартным задачам оптимизации функций, а также к областям инженерных задач. Еще одно аналогичное расширение EO - это непрерывная экстремальная оптимизация (CEO).
EO применялся для растеризации изображений, а также использовался в качестве локального поиска после оптимизации муравьиной колонии . EO использовался для идентификации структур в сложных сетях. EO использовался для решения проблемы слежения за несколькими целями. Наконец, была проделана некоторая работа по исследованию распределения вероятностей, используемого для контроля выбора.
Смотрите также
Рекомендации
- Бак, Пер; Тан, Чао; Визенфельд, Курт (1987-07-27). «Самоорганизованная критичность: объяснение шума 1 / f». Письма с физическим обзором . Американское физическое общество (APS). 59 (4): 381–384. Bibcode : 1987PhRvL..59..381B . DOI : 10.1103 / physrevlett.59.381 . ISSN 0031-9007 . PMID 10035754 .
- Бак, Пер; Снеппен, Ким (1993-12-13). «Прерывистое равновесие и критичность в простой модели эволюции». Письма с физическим обзором . Американское физическое общество (APS). 71 (24): 4083–4086. Bibcode : 1993PhRvL..71.4083B . DOI : 10.1103 / physrevlett.71.4083 . ISSN 0031-9007 . PMID 10055149 .
- П. Чизмен, Б. Канефски, В. М. Тейлор, «Где действительно серьезные проблемы» [ постоянная мертвая ссылка ] , Труды 12-го IJCAI, (1991)
- Г. Истрате, " Вычислительная сложность и фазовые переходы ", Труды. 15-я ежегодная конференция IEEE по вычислительной сложности, 104–115 (2000)
- Стефан Ботчер, Аллон Г. Перкус, «Экстремальная оптимизация: методы, полученные в результате совместной эволюции» , Труды конференции по генетическим и эволюционным вычислениям (1999)
- Бетчер, Стефан (1 января 1999 г.). «Экстремальная оптимизация разбиения графа на пороге перколяции». Журнал физики A: математический и общий . IOP Publishing. 32 (28): 5201–5211. arXiv : cond-mat / 9901353 . Bibcode : 1999JPhA ... 32.5201B . DOI : 10.1088 / 0305-4470 / 32/28/302 . ISSN 0305-4470 . S2CID 7925735 .
- Ботчер, Стефан; Перкус, Аллон (2000), «Природный способ оптимизации», Искусственный интеллект , 119 (1-2): 275–286, arXiv : cond-mat / 9901351 , doi : 10.1016 / S0004-3702 (00) 00007-2 , S2CID 7128022
- Бетчер, С. (2000). «Экстремальная оптимизация: эвристика через коэволюционные лавины». Вычислительная техника в науке и технике . Институт инженеров по электротехнике и радиоэлектронике (IEEE). 2 (6): 75–82. arXiv : cond-mat / 0006374 . Bibcode : 2000CSE ..... 2f..75B . DOI : 10.1109 / 5992.881710 . ISSN 1521-9615 . S2CID 7259036 .
- Ботчер, Стефан; Перкус, Аллон Г. (2001-06-04). «Оптимизация с экстремальной динамикой». Письма с физическим обзором . Американское физическое общество (APS). 86 (23): 5211–5214. arXiv : cond-mat / 0010337 . Bibcode : 2001PhRvL..86.5211B . DOI : 10.1103 / physrevlett.86.5211 . ISSN 0031-9007 . PMID 11384460 . S2CID 3261749 .
- Далл, Джеспер; Сибани, Паоло (2001). «Более быстрое моделирование Монте-Карло при низких температурах. Метод времени ожидания». Компьютерная физика . 141 (2): 260–267. arXiv : cond-mat / 0107475 . Bibcode : 2001CoPhC.141..260D . DOI : 10.1016 / s0010-4655 (01) 00412-X . ISSN 0010-4655 . S2CID 14585624 .
- Ботчер, Стефан; Гриньи, Микеланджело (28 января 2002). «Модель глушения для эвристики экстремальной оптимизации». Журнал физики A: математический и общий . IOP Publishing. 35 (5): 1109–1123. arXiv : cond-mat / 0110165 . Bibcode : 2002JPhA ... 35.1109B . DOI : 10.1088 / 0305-4470 / 35/5/301 . ISSN 0305-4470 . S2CID 640976 .
- Сухам Мешул и Мохамед Батуш, «Соответствие устойчивых точек для регистрации изображений с использованием оптимизации с экстремальной динамикой» [ постоянная мертвая ссылка ] , Lecture Notes in Computer Science 2449 , 330–337 (2002)
- Оноди, Роберто Н .; Де Кастро, Пауло А. (2003). «Самоорганизованная критичность, оптимизация и биоразнообразие». Международный журнал современной физики С . World Scientific Pub Co Pte Lt. 14 (7): 911-916. arXiv : cond-mat / 0302260 . Bibcode : 2003IJMPC..14..911O . DOI : 10.1142 / s0129183103005054 . ISSN 0129-1831 . S2CID 14553130 .
- Ботчер, Стефан; Перкус, Аллон Г. (2004-06-24). «Экстремальная оптимизация при фазовом переходе задачи трех раскраски». Physical Review E . Американское физическое общество (APS). 69 (6): 066703. arXiv : cond-mat / 0402282 . Bibcode : 2004PhRvE..69f6703B . DOI : 10.1103 / physreve.69.066703 . ISSN 1539-3755 . PMID 15244779 . S2CID 3070942 .
- Миддлтон, А. Алан (2004-05-14). «Улучшенная экстремальная оптимизация для спинового стекла Изинга». Physical Review E . Американское физическое общество (APS). 69 (5): 055701 (R). arXiv : cond-mat / 0402295 . Bibcode : 2004PhRvE..69e5701M . DOI : 10.1103 / physreve.69.055701 . ISSN 1539-3755 . PMID 15244875 . S2CID 28439352 .
- Heilmann, F; Hoffmann, K. H; Саламон, П. (2004). «Наилучшее возможное распределение вероятностей по рангам экстремальной оптимизации». Письма Europhysics (EPL) . IOP Publishing. 66 (3): 305–310. Bibcode : 2004EL ..... 66..305H . DOI : 10,1209 / EPL / i2004-10011-3 . ISSN 0295-5075 .
- [1] Понтус Свенсон, «Экстремальная оптимизация для предварительной обработки отчетов с датчиков», Proc SPIE 5429 , 162–171 (2004).
- Чжоу, Дао; Бай, Вэнь-Цзе; Ченг, Лун-Джиу; Ван, Бинг-Хун (2005-07-06). «Непрерывная экстремальная оптимизация для леннард-джонсовских кластеров». Physical Review E . Американское физическое общество (APS). 72 (1): 016702. arXiv : cond-mat / 0411428 . Bibcode : 2005PhRvE..72a6702Z . DOI : 10.1103 / physreve.72.016702 . ISSN 1539-3755 . PMID 16090129 . S2CID 26578844 .
- Duch, Jordi; Аренас, Алекс (24 августа 2005). «Обнаружение сообществ в сложных сетях с использованием экстремальной оптимизации». Physical Review E . Американское физическое общество (APS). 72 (2): 027104. arXiv : cond-mat / 0501368 . Bibcode : 2005PhRvE..72b7104D . DOI : 10.1103 / physreve.72.027104 . ISSN 1539-3755 . PMID 16196754 . S2CID 13898113 .
- Ahmed, E .; Элеттреби, MF (2006). «О комбинаторной оптимизации по мотивам биологии». Прикладная математика и вычисления . Elsevier BV. 172 (1): 40–48. DOI : 10.1016 / j.amc.2005.01.122 . ISSN 0096-3003 .
Внешние ссылки
- Стефан Ботчер - Физический факультет, Университет Эмори
- Аллон Перкус - Калифорнийский университет, Лос-Анджелес
- Алгоритмы глобальной оптимизации - Теория и применение - Томас Вайз