Метаэвристический - Metaheuristic

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

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

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

Характеристики

Это свойства, которые характеризуют большинство метаэвристик:

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

Классификация

Диаграмма Эйлера различных классификаций метаэвристики.

Существует множество метаэвристик и ряд свойств, по которым их можно классифицировать.

Локальный поиск против глобального поиска

Один из подходов - охарактеризовать тип поисковой стратегии. Один из типов стратегии поиска - это усовершенствование простых алгоритмов локального поиска. Хорошо известным алгоритмом локального поиска является метод восхождения на холм, который используется для поиска локальных оптимумов. Однако восхождение на холмы не гарантирует нахождения оптимальных решений в глобальном масштабе.

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

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

Единое решение против популяционного

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

Гибридизация и меметические алгоритмы

Гибридная метаэвристика объединяет метаэвристику с другими подходами к оптимизации, такими как алгоритмы математического программирования , программирование с ограничениями и машинное обучение . Оба компонента гибридной метаэвристики могут работать одновременно и обмениваться информацией, чтобы направлять поиск.

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

Параллельная метаэвристика

Параллельно метаэвристический является тот , который использует методы параллельного программирования для запуска несколько метаэвристического поиска параллельно; они могут варьироваться от простых распределенных схем до параллельных поисковых запусков, которые взаимодействуют для улучшения общего решения.

Метаэвристика, вдохновленная природой и основанная на метафорах

Основные статьи: Интеллект роя и список метаэвристик, основанных на метафорах

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

Приложения

Метаэвристика используется для комбинаторной оптимизации, при которой оптимальное решение ищется в дискретном пространстве поиска. Примером проблемы является задача коммивояжера, в которой пространство поиска возможных решений растет быстрее, чем экспоненциально, по мере увеличения размера задачи, что делает невозможным исчерпывающий поиск оптимального решения. Кроме того, многомерные комбинаторные проблемы, включая большинство проблем проектирования в инженерии, такие как поиск формы и поведение, страдают от проклятия размерности , что также делает их невозможными для исчерпывающего поиска или аналитических методов . Метаэвристика также широко используется для планирования работы цехов и задач выбора работы. Популярные метаэвристики для комбинаторных задач включают моделирование отжига Киркпатрика и др., Генетические алгоритмы Холланда и др., Поиск по разбросу и поиск запретов Гловера. Обзор литературы по метаэвристической оптимизации предполагает, что слово «метаэвристика» придумал Фред Гловер.

Фреймворки метаэвристической оптимизации (MOF)

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

Существует множество инструментов-кандидатов для оптимизации, которые можно рассматривать как MOF с различной функциональностью: Comet, EvA2, evolvica, Evolutionary :: Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO / EO. , Pisa, Watchmaker, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, UOF и OptaPlanner.

Взносы

Существует множество различных метаэвристик, и постоянно предлагаются новые варианты. Некоторые из наиболее значительных вкладов в эту область:

Смотрите также

использованная литература

дальнейшее чтение

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