Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Свойства [ править ]

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

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

Классификация [ править ]

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

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

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

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

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

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

Одно решение или популяционное [ править ]

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

Гибридизация и меметические алгоритмы [ править ]

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

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

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

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

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

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

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

Метаэвристика, вдохновленная древностью [ править ]

Кажется, мы сталкиваемся с новым источником вдохновения. Это уступит дорогу многим древним алгоритмам. В древнюю эпоху существовало множество ограничений, но различные искусственные сооружения указывают на то, что ограничения и нехватка оборудования привели к некоторой оптимизации. Более пристальный взгляд на эти древние реликвии показывает, что методы, стратегии и технологии, использовавшиеся в древности, намного более продвинуты и оптимизированы, чем мы могли себе представить. Идеология, вдохновленная древностью, наблюдает и размышляет над особенностями и стремится понять способы управления проектом в то время. [12]

Приложения [ править ]

Метаэвристика используется для комбинаторной оптимизации, при которой оптимальное решение ищется в дискретном пространстве поиска. Примером проблемы является задача коммивояжера, в которой пространство поиска возможных решений растет быстрее, чем экспоненциально, по мере увеличения размера задачи, что делает невозможным исчерпывающий поиск оптимального решения. Кроме того, многомерные комбинаторные проблемы, в том числе большинство проблем проектирования в инженерии [13] [14] [15], такие как поиск формы и поведение, страдают от проклятия размерности , что также делает их невозможными для исчерпывающего поиска илианалитические методы . Метаэвристика также широко используется для планирования работы цехов и задач выбора работы. [ Править ] Популярная метаэвристики для комбинаторных задач включают в себя моделирование отжига Киркпатрик и др., [16] генетические алгоритмы Голландия и др., [17] Поиск рассеяния [18] и поиск с запретами [19] с помощью Гловера. Обзор литературы по метаэвристической оптимизации [20] предполагает, что слово «метаэвристика» придумал Фред Гловер. [21]

Рамки метаэвристической оптимизации (MOF) [ править ]

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

Существует множество инструментов-кандидатов для оптимизации, которые можно рассматривать как 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 [22] и OptaPlanner.

Вклады [ править ]

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

  • 1952: Роббинс и Монро работают над методами стохастической оптимизации. [23]
  • 1954: Барричелли проводит первые симуляции процесса эволюции и использует их для решения общих задач оптимизации. [24]
  • 1963: Растригин предлагает случайный поиск . [25]
  • 1965: Матиас предлагает случайную оптимизацию . [26]
  • 1965: Нелдер и Мид предлагают симплекс-эвристику , которая, как показал Пауэлл, сходится к нестационарным точкам в некоторых задачах. [27]
  • 1965: Инго Рехенберг открывает первый алгоритм Evolution Strategies . [28]
  • 1966: Fogel et al. предложить эволюционное программирование . [29]
  • 1970: Гастингс предлагает алгоритм Метрополиса – Гастингса . [30]
  • 1970: Кавиччио предлагает адаптацию параметров управления для оптимизатора. [31]
  • 1970: Керниган и Лин предлагают метод разделения графа, связанный с поиском с переменной глубиной и поиском на основе запретов (запретов) . [32]
  • 1975: Голландия предлагает генетический алгоритм . [17]
  • 1977: Гловер предлагает поиск по методу рассеяния. [18]
  • 1978: Мерсер и Сэмпсон предлагают метаплан для настройки параметров оптимизатора с помощью другого оптимизатора. [33]
  • 1980: Смит описывает генетическое программирование . [34]
  • 1983: Киркпатрик и др. предложить имитацию отжига . [16]
  • 1986: Гловер предлагает запретный поиск , первое упоминание термина « метаэвристический» . [19]
  • 1989: Москато предлагает меметические алгоритмы . [11]
  • 1990: Москато и Фонтанари [35] и Дюк и Шойер [36] независимо предложили детерминированное правило обновления для имитации отжига, которое ускорило поиск. Это привело к принятию порога метаэвристики.
  • 1992: Дориго вводит оптимизацию колоний муравьев в своей докторской диссертации. [10]
  • 1995: Вольперт и Макреди доказывают теоремы об отсутствии бесплатного обеда . [37] [38] [39] [40]

См. Также [ править ]

  • Стохастический поиск
  • Мета-оптимизация
  • Матевристика
  • Гиперэвристика
  • Рой интеллект
  • Генетические алгоритмы
  • Имитация отжига
  • Моделирование рабочей силы

Ссылки [ править ]

  1. ^ Р. Баламуруган; AM Натараджан; К. Премалата (2015). "Оптимизация звездной массы черных дыр для бикластеризации данных экспрессии генов микрочипов". Прикладной искусственный интеллект . 29 (4): 353–381. DOI : 10.1080 / 08839514.2015.1016391 . S2CID 44624424 . 
  2. ^ a b c d e Бьянки, Леонора; Марко Дориго; Лука Мария Гамбарделла; Уолтер Дж. Гутьяр (2009). «Обзор метаэвристики для стохастической комбинаторной оптимизации» (PDF) . Естественные вычисления . 8 (2): 239–287. DOI : 10.1007 / s11047-008-9098-4 . S2CID 9141490 .  
  3. ^ a b c d e f g h i j Blum, C .; Роли, А. (2003). «Метаэвристика в комбинаторной оптимизации: обзор и концептуальное сравнение» . 35 (3). ACM Computing Surveys: 268–308. Цитировать журнал требует |journal=( помощь )
  4. Перейти ↑ Goldberg, DE (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Kluwer Academic Publishers. ISBN 978-0-201-15767-3.
  5. ^ Гловер, Ф .; Кохенбергер, Г.А. (2003). Справочник по метаэвристике . 57 . Спрингер, Международная серия исследований операций и управления. ISBN 978-1-4020-7263-5.
  6. ^ a b c d e Talbi, EG. (2009). Метаэвристика: от дизайна до реализации . Вайли. ISBN 978-0-470-27858-1.
  7. ^ a b Соренсен, Кеннет (2015). «Метаэвристика - разоблаченная метафора» (PDF) . Международные операции в операционных исследованиях . 22 : 3–18. CiteSeerX 10.1.1.470.3422 . DOI : 10.1111 / itor.12001 . Архивировано из оригинального (PDF) 2 ноября 2013 года.  
  8. ^ Классификация метаэвристики
  9. ^ D, Бину (2019). «RideNN: новая нейронная сеть на основе алгоритма оптимизации райдера для диагностики неисправностей в аналоговых схемах» . IEEE Transactions по приборостроению и измерениям . 68 (1): 2–26. DOI : 10.1109 / TIM.2018.2836058 . S2CID 54459927 . 
  10. ^ a b М. Дориго, Оптимизация, обучение и естественные алгоритмы , докторская диссертация, Миланский политехнический университет, Италия, 1992.
  11. ^ a b Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: к меметическим алгоритмам» . Программа параллельных вычислений Калифорнийского технологического института (отчет 826).
  12. ^ "Алгоритм строительства пирамид Гизы (GPC)" . www.mathworks.com . Проверено 28 сентября 2020 .
  13. ^ Томоягэ Б., Чиндриш М., Сампер А., Судрия-Андреу А., Виллафафила-Роблес Р. Оптимальная реконфигурация по Парето систем распределения энергии с использованием генетического алгоритма на основе NSGA-II. Энергии. 2013; 6 (3): 1439–1455.
  14. ^ Ganesan, T .; Elamvazuthi, I .; Ку Шаари, Ку Зилати; Васант, П. (2013-03-01). «Ройовой интеллект и алгоритм гравитационного поиска для многоцелевой оптимизации добычи синтез-газа». Прикладная энергия . 103 : 368–374. DOI : 10.1016 / j.apenergy.2012.09.059 .
  15. ^ Ganesan, T .; Elamvazuthi, I .; Васант, П. (2011-11-01). Эволюционный метод пересечения нормальных границ (ENBI) для многоцелевой оптимизации системы зеленых песчаных форм . 2011 Международная конференция IEEE по системам управления, вычислениям и проектированию (ICCSCE) . С. 86–91. DOI : 10.1109 / ICCSCE.2011.6190501 . ISBN 978-1-4577-1642-3. S2CID  698459 .
  16. ^ a b Киркпатрик, S .; Гелатт младший, компакт-диск; Векки, депутат (1983). «Оптимизация моделированием отжига». Наука . 220 (4598): 671–680. Bibcode : 1983Sci ... 220..671K . CiteSeerX 10.1.1.123.7607 . DOI : 10.1126 / science.220.4598.671 . PMID 17813860 . S2CID 205939 .   
  17. ^ а б Голландия, JH (1975). Адаптация в естественных и искусственных системах . Пресса Мичиганского университета. ISBN 978-0-262-08213-6.
  18. ^ a b Гловер, Фред (1977). «Эвристика для целочисленного программирования с использованием суррогатных ограничений». Решение наук . 8 (1): 156–166. CiteSeerX 10.1.1.302.4071 . DOI : 10.1111 / j.1540-5915.1977.tb01074.x . 
  19. ^ а б Гловер, Ф. (1986). «Пути будущего для целочисленного программирования и связи с искусственным интеллектом». Компьютеры и исследования операций . 13 (5): 533–549. DOI : 10.1016 / 0305-0548 (86) 90048-1 .
  20. ^ XS Ян, Метаэвристическая оптимизация, Scholarpedia, 6 (8): 11472 (2011).
  21. ^ Гловер Ф., (1986). Будущие пути для целочисленного программирования и ссылки на искусственный интеллект , Computers and Operations Research, 13, 533–549 (1986).
  22. ^ a b Москато, П. (2012). «Фреймворки метаэвристической оптимизации: обзор и сравнительный анализ». Мягкие вычисления (2012) 16, 527–561 . 16 (3): 527–561. DOI : 10.1007 / s00500-011-0754-8 . hdl : 11441/24597 . S2CID 1497912 . 
  23. ^ Роббинс, H .; Монро, С. (1951). "Метод стохастической аппроксимации" (PDF) . Анналы математической статистики . 22 (3): 400–407. DOI : 10.1214 / АОМ / 1177729586 .
  24. ^ Barricelli, Н. А. (1954). "Esempi numerici di processi di evoluzione". Methodos : 45-68.
  25. ^ Растригин, Л. (1963). «Сходимость метода случайного поиска в экстремальном управлении многопараметрической системой». Автоматизация и телемеханика . 24 (10): 1337–1342.
  26. ^ Матиас, J. (1965). «Случайная оптимизация» . Автоматизация и телемеханика . 26 (2): 246–253.
  27. ^ Нелдер, JA; Мид, Р. (1965). «Симплексный метод минимизации функции». Компьютерный журнал . 7 (4): 308–313. DOI : 10.1093 / comjnl / 7.4.308 . S2CID 2208295 . 
  28. ^ Rechenberg, Инго (1965). «Путь кибернетического решения экспериментальной задачи». Royal Aircraft Establishment, перевод библиотеки .
  29. ^ Fogel, L .; Оуэнс, AJ; Уолш, MJ (1966). Искусственный интеллект посредством моделирования эволюции . Вайли. ISBN 978-0-471-26516-0.
  30. Перейти ↑ Hastings, WK (1970). "Методы выборки Монте-Карло с использованием цепей Маркова и их приложения". Биометрика . 57 (1): 97–109. Bibcode : 1970Bimka..57 ... 97H . DOI : 10.1093 / Biomet / 57.1.97 . S2CID 21204149 . 
  31. ^ Cavicchio, DJ (1970). «Адаптивный поиск с использованием моделирования эволюции». Технический отчет . Мичиганский университет, факультет компьютерных наук и коммуникаций. ЛВП : 2027,42 / 4042 .
  32. ^ Керниган, BW; Лин, С. (1970). «Эффективная эвристическая процедура разбиения графов». Технический журнал Bell System . 49 (2): 291–307. DOI : 10.1002 / j.1538-7305.1970.tb01770.x .
  33. ^ Мерсер, RE; Сэмпсон, младший (1978). «Адаптивный поиск с использованием репродуктивного метаплана». Кибернетес . 7 (3): 215–228. DOI : 10,1108 / eb005486 .
  34. ^ Смит, SF (1980). Система обучения на основе генетических адаптивных алгоритмов (кандидатская диссертация). Университет Питтсбурга.
  35. ^ Moscato, P .; Фонтанари, Дж. Ф. (1990), «Стохастическое и детерминированное обновление при моделировании отжига», Physics Letters A , 146 (4): 204–208, Bibcode : 1990PhLA..146..204M , doi : 10.1016 / 0375-9601 (90) 90166-L
  36. ^ Dueck, G .; Scheuer, T. (1990), «Принятие порога: алгоритм оптимизации общего назначения, превосходящий моделируемый отжиг», Journal of Computational Physics , 90 (1): 161–175, Bibcode : 1990JCoPh..90..161D , doi : 10.1016 / 0021-9991 (90) 90201-Б , ISSN 0021-9991 
  37. ^ Wolpert, DH; Макреди, WG (1995). «Нет теорем о бесплатном обеде для поиска». Технический отчет SFI-TR-95-02-010 . Институт Санта-Фе. S2CID 12890367 . 
  38. ^ Игель, Кристиан, Туссен, Марк (июнь 2003). «О классах функций, для которых результаты бесплатного обеда отсутствуют». Письма об обработке информации . 86 (6): 317–321. arXiv : cs / 0108011 . DOI : 10.1016 / S0020-0190 (03) 00222-9 . ISSN 0020-0190 . S2CID 147624 .  CS1 maint: несколько имен: список авторов ( ссылка )
  39. ^ Оже, Энн, Teytaud, Оливье (2010). «Непрерывные обеды бесплатные плюс разработка оптимальных алгоритмов оптимизации». Алгоритмика . 57 (1): 121–146. CiteSeerX 10.1.1.186.6007 . DOI : 10.1007 / s00453-008-9244-5 . ISSN 0178-4617 . S2CID 1989533 .   CS1 maint: несколько имен: список авторов ( ссылка )
  40. ^ Стефан Дросте; Томас Янсен; Инго Вегенер (2002). «Оптимизация с помощью эвристики рандомизированного поиска - теорема (A) NFL, реалистичные сценарии и сложные функции». Теоретическая информатика . 287 (1): 131–144. CiteSeerX 10.1.1.35.5850 . DOI : 10.1016 / s0304-3975 (02) 00094-4 . 

Дальнейшее чтение [ править ]

  • Соренсен, Кеннет; Сево, Марк; Гловер, Фред (2017-01-16). «История метаэвристики» (PDF) . В Марти, Рафаэль; Панос, Пардалос; Ресенде, Маурисио (ред.). Справочник по эвристике . Springer. ISBN 978-3-319-07123-7.

Внешние ссылки [ править ]

  • Фред Гловер и Кеннет Соренсен (ред.). «Метаэвристика» . Scholarpedia .
  • Форум ЕС / ME для исследователей в этой области.