Экстремальная оптимизация

Экстремальная оптимизация (EO) — это оптимизации, эвристика вдохновленная Бака – Снеппена моделью самоорганизованной критичности из области статистической физики. Эта эвристика изначально была разработана для решения задач комбинаторной оптимизации, таких как задача коммивояжера и спиновые очки , хотя было продемонстрировано, что этот метод работает и в областях оптимизации.

Отношение к самоорганизованной критичности

Самоорганизованная критичность (SOC) — это концепция статистической физики, описывающая класс динамических систем, у которых критическая точка является аттрактором. В частности, это неравновесные системы, которые развиваются посредством лавин изменений и диссипаций, достигающих самых высоких масштабов системы. Говорят, что SOC управляет динамикой некоторых природных систем, в которых наблюдаются такие взрывоподобные явления, включая формирование ландшафта, землетрясения, эволюцию и гранулярную динамику риса и песчаных куч. Особый интерес здесь представляет модель SOC Бака-Снеппена , которая способна описывать эволюцию через прерывистое равновесие (события вымирания), моделируя таким образом эволюцию как самоорганизующийся критический процесс.

Связь с вычислительной сложностью

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

Техника

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

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

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

ЭО в первую очередь применялся к комбинаторным задачам, таким как разбиение графа и задача коммивояжера , а также к задачам статистической физики, таким как спиновые стекла .

Вариации на тему и приложения

Обобщенная экстремальная оптимизация (GEO) была разработана для работы с битовыми строками, где качество компонента определяется абсолютной скоростью изменения бита или вкладом битов в целостное качество решения. Эта работа включает в себя применение к стандартным задачам оптимизации функций, а также к областям инженерных задач. Еще одно подобное расширение EO — непрерывная экстремальная оптимизация (CEO).

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

См. также

Ссылки

Бак, Пер; Тан, Чао; Визенфельд, Курт (27 июля 1987 г.). «Самоорганизованная критичность: объяснение 1/fnoise». Письма о физических отзывах . 59 (4). Американское физическое общество (APS): 381–384. Бибкод : 1987PhRvL..59..381B . дои : 10.1103/physrevlett.59.381 . ISSN 0031-9007 . ПМИД 10035754 . S2CID 7674321 .
Бак, Пер; Снеппен, Ким (13 декабря 1993 г.). «Периодическое равновесие и критичность в простой модели эволюции». Письма о физических отзывах . 71 (24). Американское физическое общество (APS): 4083–4086. Бибкод : 1993PhRvL..71.4083B . дои : 10.1103/physrevlett.71.4083 . ISSN 0031-9007 . ПМИД 10055149 .
П. Чизмен, Б. Канефски, В.М. Тейлор, «Где действительно трудные проблемы» ^{[ постоянная мертвая ссылка ]}, Материалы 12-го IJCAI, (1991)
Г. Истрате, « Вычислительная сложность и фазовые переходы », Труды. 15-я ежегодная конференция IEEE по сложности вычислений, 104–115 (2000 г.)
Стефан Бетчер, Аллон Г. Перкус, «Экстремальная оптимизация: методы, полученные на основе совместной эволюции» , Труды конференции по генетическим и эволюционным вычислениям (1999)
Бетчер, Стефан (1 января 1999 г.). «Экстремальная оптимизация разделения графа на пороге перколяции». Журнал физики A: Математический и общий . 32 (28). Издательство ИОП: 5201–5211. arXiv : cond-mat/9901353 . Бибкод : 1999JPhA...32.5201B . дои : 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). «Экстремальная оптимизация: эвристика через коэволюционные лавины». Вычисления в науке и технике . 2 (6). Институт инженеров по электротехнике и электронике (IEEE): 75–82. arXiv : cond-mat/0006374 . Бибкод : 2000CSE.....2f..75B . дои : 10.1109/5992.881710 . ISSN 1521-9615 . S2CID 7259036 .
Бетчер, Стефан; Перкус, Аллон Г. (4 июня 2001 г.). «Оптимизация с экстремальной динамикой». Письма о физических отзывах . 86 (23). Американское физическое общество (APS): 5211–5214. arXiv : cond-mat/0010337 . Бибкод : 2001PhRvL..86.5211B . дои : 10.1103/physrevlett.86.5211 . ISSN 0031-9007 . ПМИД 11384460 . S2CID 3261749 .
Далл, Джеспер; Сибани, Паоло (2001). «Быстрое моделирование Монте-Карло при низких температурах. Метод времени ожидания». Компьютерная физика. Коммуникации . 141 (2): 260–267. arXiv : cond-mat/0107475 . Бибкод : 2001CoPhC.141..260D . дои : 10.1016/s0010-4655(01)00412-x . ISSN 0010-4655 . S2CID 14585624 .
Бетчер, Стефан; Гриньи, Микеланджело (28 января 2002 г.). «Модель заклинивания для эвристики экстремальной оптимизации». Журнал физики A: Математический и общий . 35 (5). Издательство ИОП: 1109–1123. arXiv : cond-mat/0110165 . Бибкод : 2002JPhA...35.1109B . дои : 10.1088/0305-4470/35/5/301 . ISSN 0305-4470 . S2CID 640976 .
Сухам Мешул и Мохамед Батуш, «Надежное соответствие точек для регистрации изображений с использованием оптимизации с экстремальной динамикой» ^{[ постоянная мертвая ссылка ]}, Конспекты лекций по информатике 2449 , 330–337 (2002)
Оноди, Роберто Н.; Де Кастро, Пауло А. (2003). «Самоорганизованная критичность, оптимизация и биоразнообразие». Международный журнал современной физики C . 14 (7). World Scientific Pub Co Pte Lt: 911–916. arXiv : cond-mat/0302260 . Бибкод : 2003IJMPC..14..911O . дои : 10.1142/s0129183103005054 . ISSN 0129-1831 . S2CID 14553130 .
Бетчер, Стефан; Перкус, Аллон Г. (24 июня 2004 г.). «Экстремальная оптимизация при фазовом переходе задачи трёх раскрасок». Физический обзор E . 69 (6). Американское физическое общество (APS): 066703. arXiv : cond-mat/0402282 . Бибкод : 2004PhRvE..69f6703B . дои : 10.1103/physreve.69.066703 . ISSN 1539-3755 . ПМИД 15244779 . S2CID 3070942 .
Миддлтон, А. Алан (14 мая 2004 г.). «Улучшенная экстремальная оптимизация спинового стекла Изинга». Физический обзор E . 69 (5). Американское физическое общество (APS): 055701(R). arXiv : cond-mat/0402295 . Бибкод : 2004PhRvE..69e5701M . дои : 10.1103/physreve.69.055701 . ISSN 1539-3755 . ПМИД 15244875 . S2CID 28439352 .
Хейльманн, Ф; Хоффманн, К.Х; Саламон, П. (2004). «Наилучшее возможное распределение вероятностей по экстремальным рангам оптимизации». Письма по еврофизике (EPL) . 66 (3). Издательство ИОП: 305–310. Бибкод : 2004EL.....66..305H . дои : 10.1209/epl/i2004-10011-3 . ISSN 0295-5075 . S2CID 250810936 .
[1] Понтус Свенсон, «Экстремальная оптимизация предварительной обработки отчетов датчиков», Proc SPIE 5429 , 162–171 (2004).
Чжоу, Тао; Бай, Вэнь-Цзе; Ченг, Лун-Цзю; Ван, Бин-Хонг (6 июля 2005 г.). «Непрерывная экстремальная оптимизация кластеров Леннарда-Джонса». Физический обзор E . 72 (1). Американское физическое общество (APS): 016702. arXiv : cond-mat/0411428 . Бибкод : 2005PhRvE..72a6702Z . дои : 10.1103/physreve.72.016702 . ISSN 1539-3755 . ПМИД 16090129 . S2CID 26578844 .
Дач, Джорди; Аренас, Алекс (24 августа 2005 г.). «Обнаружение сообществ в сложных сетях с использованием экстремальной оптимизации». Физический обзор E . 72 (2). Американское физическое общество (APS): 027104. arXiv : cond-mat/0501368 . Бибкод : 2005PhRvE..72b7104D . дои : 10.1103/physreve.72.027104 . ISSN 1539-3755 . ПМИД 16196754 . S2CID 13898113 .
Ахмед, Э.; Элеттреби, МФ (2006). «О комбинаторной оптимизации по мотивам биологии». Прикладная математика и вычислительная техника . 172 (1). Эльзевир Б.В.: 40–48. дои : 10.1016/j.amc.2005.01.122 . ISSN 0096-3003 .

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

Стефан Бетчер – Физический факультет Университета Эмори
Аллон Перкус – Аспирантура Клермонтского университета
Алгоритмы глобальной оптимизации - Теория и применение - Архивировано 11 сентября 2008 г. в Wayback Machine - Томас Вайзе.