Введение
Метод оптимизации
В информатике и математической оптимизации метаэвристика — это процедура или эвристика более высокого уровня, предназначенная для поиска, генерации, настройки или выбора эвристики (частичного алгоритма поиска), которая может предоставить достаточно хорошее решение задачи оптимизации или задачи машинного обучения, особенно при неполной или несовершенной информации или ограниченных вычислительных ресурсах. Предполагается, что термин "метаэвристика" был введен Фредом Гловером. Большая часть литературы по метаэвристикам носит экспериментальный характер, описывая эмпирические результаты, полученные в ходе компьютерных экспериментов с алгоритмами. Однако существуют и некоторые формальные теоретические результаты, часто касающиеся сходимости и возможности нахождения глобального оптимума.
In computer science and mathematical optimization, a metaheuristic is a higher level procedure or heuristic designed to find, generate, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. suggested that it was Fred Glover who coined the word metaheuristics. Most literature on metaheuristics is experimental in nature, describing empirical results based on computer experiments with the algorithms. But some formal theoretical results are also available, often on convergence and the possibility of finding the global optimum.
Единое решение против населения
Еще одно измерение классификации — поиск одного решения против поиска на основе популяции. оптимизация роем частиц,
Приложения
Метаэвристики используются для решения всех типов задач оптимизации, от непрерывных и смешанных задач целочисленного программирования до задач комбинаторной оптимизации или их комбинаций. В задачах комбинаторной оптимизации оптимальное решение ищется в дискретном пространстве поиска. Классическим примером является задача коммивояжера, где пространство поиска возможных решений растет быстрее экспоненциально с увеличением размера задачи, что делает полный перебор для нахождения оптимального решения невозможным. Кроме того, многомерные комбинаторные задачи, включая большинство задач проектирования в инженерии, таких как определение формы и поведения, подвержены "проклятию размерности", что также делает невозможным их решение полным перебором или аналитическими методами. Метаэвристики также часто применяются к задачам планирования. Типичным примером этого класса комбинаторных задач является задача планирования работы цеха, которая заключается в назначении операций рабочих заданий на обрабатывающие станции таким образом, чтобы все задания были выполнены вовремя и в целом за минимальное время. На практике часто необходимо учитывать ограничения, например, ограничивать допустимую последовательность операций задания с помощью предопределенных технологических процессов и/или в отношении использования ресурсов, например, путем сглаживания энергопотребления. К популярным метаэвристикам для решения комбинаторных задач относятся генетические алгоритмы, разработанные Холландом и др., и их применение в различных инженерных задачах. Примером сочетания комбинаторной и непрерывной оптимизации является планирование оптимальных траекторий движения для промышленных роботов.
Метаевристические системы оптимизации
MOF можно определить как «набор программных инструментов, обеспечивающих корректную и повторно используемую реализацию набора метаэвристик, а также базовые механизмы для ускорения реализации сопутствующих подчиненных эвристик (включая, возможно, кодирование решений и специфические для техники операторы), необходимые для решения конкретного экземпляра задачи с использованием предоставляемых методов». Dueck и Scheuer независимо друг от друга предложили детерминированное правило обновления для имитации отжига, что ускорило поиск. Это привело к появлению метаэвристики «принятие по порогу». 1992 год: Дориго представил оптимизацию муравьиных колоний в своей докторской диссертации.