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

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

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

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

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

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

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

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

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