stringtranslate.com

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

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

По сравнению с алгоритмами оптимизации и итеративными методами , метаэвристики не гарантируют, что глобально оптимальное решение может быть найдено для некоторого класса задач. [3] Многие метаэвристики реализуют некоторую форму стохастической оптимизации , так что найденное решение зависит от набора сгенерированных случайных величин . [2] В комбинаторной оптимизации существует много задач, которые относятся к классу NP-полных задач и, таким образом, больше не могут быть решены точно за приемлемое время из относительно низкой степени сложности. [7] [8] Затем метаэвристики часто предоставляют хорошие решения с меньшими вычислительными усилиями, чем методы аппроксимации, итеративные методы или простые эвристики. [3] [4] Это также применимо в области непрерывной или смешанно-целочисленной оптимизации. [4] [9] [10] Таким образом, метаэвристики являются полезными подходами для задач оптимизации. [2] По этой теме было опубликовано несколько книг и обзорных статей. [2] [3] [4] [11] [12] Обзор литературы по метаэвристической оптимизации [13] предполагает, что именно Фред Гловер придумал слово «метаэвристика». [14]

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

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

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

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

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

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

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

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

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

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

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

Единичное решение против решения на основе популяции

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

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

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

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

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

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

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

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

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

Большое количество более поздних метаэвристик, вдохновленных метафорами, начали подвергаться критике в исследовательском сообществе за то, что они скрывают свою нехватку новизны за сложной метафорой. [16] [17] [25] В результате ряд известных ученых в этой области предложили исследовательскую программу по стандартизации метаэвристик, чтобы сделать их более сопоставимыми, среди прочего. [34] Другим следствием является то, что правила публикации ряда научных журналов были соответствующим образом адаптированы. [35] [36] [37]

Приложения

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

Метаэвристики используются для всех типов задач оптимизации, от непрерывных до смешанных целочисленных задач и комбинаторной оптимизации или их комбинаций. [9] [38] [39] В комбинаторной оптимизации оптимальное решение ищется в дискретном пространстве поиска. Примером проблемы является задача коммивояжера , где пространство поиска возможных решений растет быстрее, чем экспоненциально , по мере увеличения размера задачи, что делает исчерпывающий поиск оптимального решения невозможным. [40] [41] Кроме того, многомерные комбинаторные задачи, включая большинство задач проектирования в инженерии [6] [42] [43] [44], таких как поиск формы и поиск поведения, страдают от проклятия размерности , что также делает их непригодными для исчерпывающего поиска или аналитических методов .

Метаэвристики также часто применяются к задачам планирования. Типичным представителем этого класса комбинаторных задач является планирование рабочих процессов, которое включает в себя назначение рабочих этапов заданий на обрабатывающие станции таким образом, чтобы все задания были выполнены вовремя и в совокупности в кратчайшие сроки. [5] [45] На практике часто приходится соблюдать ограничения, например, ограничивая допустимую последовательность рабочих этапов задания с помощью предопределенных рабочих процессов [46] и/или в отношении использования ресурсов, например, в форме сглаживания потребности в энергии. [47] [48] Популярные метаэвристики для комбинаторных задач включают генетические алгоритмы Холланда и др., [49] поиск рассеяния [50] и поиск с запретами [51] Гловера.

Другая большая область применения — задачи оптимизации в непрерывных или смешанно-целочисленных пространствах поиска. Сюда входят, например, оптимизация дизайна [6] [52] [53] или различные инженерные задачи. [54] [55] [56] Примером смеси комбинаторной и непрерывной оптимизации является планирование благоприятных траекторий движения для промышленных роботов. [57] [58]

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

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

Существует множество инструментов оптимизации, которые можно рассматривать как MOF с различными функциями. Следующий список из 33 MOF сравнивается и оценивается подробно в: [59] 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. Было несколько публикаций о поддержке параллельных реализаций, которая отсутствовала в этом сравнительном исследовании, особенно с конца 10-х годов. [32] [33] [60] [61] [62]

Вклады

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

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

Ссылки

  1. ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). «Оптимизация черной дыры звездной массы для бикластеризации данных экспрессии генов микрочипов». Прикладной искусственный интеллект . 29 (4): 353–381. doi : 10.1080/08839514.2015.1016391 . S2CID  44624424.
  2. ^ abcde Бьянки, Леонора; Марко Дориго; Лука Мария Гамбарделла; Уолтер Дж. Гутъяр (2009). «Обзор метаэвристик для стохастической комбинаторной оптимизации» (PDF) . Natural Computing . 8 (2): 239–287. doi :10.1007/s11047-008-9098-4. S2CID  9141490.
  3. ^ abcdefghij Блум, Кристиан; Роли, Андреа (2003). «Метаэвристика в комбинаторной оптимизации: обзор и концептуальное сравнение». ACM Computing Surveys . 35 (3). ACM: 268–308. doi :10.1145/937503.937505.
  4. ^ abcde Гловер, Ф.; Кохенбергер, ГА (2003). Справочник по метаэвристике . Том 57. Springer, Международная серия по исследованию операций и науке управления. ISBN 978-1-4020-7263-5.
  5. ^ ab Jarboui, Bassem; Siarry, Patrick; Teghem, Jacques, ред. (2013). Метаэвристика для планирования производства. Серия «Автоматизация — управление и промышленная инженерия». Лондон: ISTE. ISBN 978-1-84821-497-2.
  6. ^ abc Gupta, Shubham; Abderazek, Hammoudi; Yıldız, Betül Sultan; Yildiz, Ali Riza; Mirjalili, Seyedali; Sait, Sadiq M. (2021). "Сравнение алгоритмов метаэвристической оптимизации для решения задач оптимизации ограниченного механического проектирования". Expert Systems with Applications . 183 : 115351. doi :10.1016/j.eswa.2021.115351.
  7. ^ Брукер, Питер; Кнуст, Сигрид (2012). Комплексное планирование. Берлин, Гейдельберг: Springer. дои : 10.1007/978-3-642-23929-8. ISBN 978-3-642-23928-1.
  8. ^ Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Комбинаторная оптимизация: алгоритмы и сложность . Mineola, NY: Dover Publ., исправленное, несокращенное новое издание работы, опубликованной Prentice-Hall в 1982 году. ISBN 978-0-486-40258-1.
  9. ^ ab Gad, Ahmed G. (2022). «Алгоритм оптимизации роя частиц и его применение: систематический обзор». Архив вычислительных методов в инженерии . 29 (5): 2531–2561. doi : 10.1007/s11831-021-09694-4 . ISSN  1134-3060.
  10. ^ Ли, Чжэньхуа; Линь, Си; Чжан, Цинфу; Лю, Хайлинь (2020). «Стратегии эволюции для непрерывной оптимизации: обзор современного состояния». Swarm и эволюционные вычисления . 56 : 100694. doi : 10.1016/j.swevo.2020.100694.
  11. ^ Голдберг, Д. Э. (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Kluwer Academic Publishers. ISBN 978-0-201-15767-3.
  12. ^ abcde Talbi, EG. (2009). Метаэвристика: от проектирования до реализации . Wiley. ISBN 978-0-470-27858-1.
  13. ^ XS Yang, Метаэвристическая оптимизация, Scholarpedia, 6(8):11472 (2011).
  14. ^ Гловер, Фред (январь 1986 г.). «Будущие пути целочисленного программирования и связи с искусственным интеллектом» (PDF) . Компьютеры и исследования операций . 13 (5): 533–549. doi :10.1016/0305-0548(86)90048-1. ISSN  0305-0548.
  15. ^ Рудольф, Гюнтер (2001). «Самоадаптивные мутации могут привести к преждевременной конвергенции». Труды IEEE по эволюционным вычислениям . 5 (4): 410–414. doi :10.1109/4235.942534. hdl : 2003/5378 .
  16. ^ ab Sörensen, Kenneth (2015). «Метаэвристика — раскрытая метафора». International Transactions in Operational Research . 22 (1): 3–18. CiteSeerX 10.1.1.470.3422 . doi :10.1111/itor.12001. S2CID  14042315. {{cite journal}}: CS1 maint: url-status ( ссылка )
  17. ^ ab Браунли, Александр; Вудворд, Джон Р. «Почему мы разлюбили алгоритмы, вдохновленные природой». The Conversation (веб-сайт) . Получено 30 августа 2024 г.
  18. ^ Швефель, Ганс-Пауль (1995). Эволюция и поиск оптимума . Серия «Технологии компьютеров шестого поколения». Нью-Йорк: Wiley. ISBN 978-0-471-57148-3.
  19. ^ Эберхарт, Р.; Кеннеди, Дж. (1995), "Новый оптимизатор, использующий теорию роя частиц", Conf. Proc. MHS'95 , IEEE, стр. 39–43, doi :10.1109/MHS.1995.494215, ISBN 978-0-7803-2676-7
  20. ^ Colorni, Alberto; Dorigo, Marco; Maniezzo, Vittorio (1991), Varela, F.; Bourgine, P. (ред.), "Распределенная оптимизация с помощью муравьиных колоний", Conf. Proc. of ECAL91 - Европейская конференция по искусственной жизни , Амстердам: Elsevier Publ., стр. 134–142, ISBN 9780262720199
  21. ^ Соха, Кшиштоф; Дориго, Марко (2008). «Оптимизация колонии муравьев для непрерывных доменов». Европейский журнал операционных исследований . 185 (3): 1155–1173. doi :10.1016/j.ejor.2006.06.046.
  22. ^ Ниссен, Волкер; Краузе, Маттиас (1994), Ройш, Бернд (редактор), «Ограниченная комбинаторная оптимизация со стратегией эволюции», Fuzzy Logik , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 33–40, номер документа : 10.1007/978-3- 642-79386-8_5, ISBN 978-3-540-58649-4, получено 2024-08-24
  23. ^ Классификация метаэвристик
  24. ^ Raidl, Günther R. (2006), Almeida, Francisco; Blesa Aguilera, María J.; Blum, Christian; Moreno Vega, José Marcos (ред.), "A Unified View on Hybrid Metaheuristics", Hybrid Metaheuristics , Lecture Notes in Computer Science, т. 4030, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 1–12, doi :10.1007/11890584_1, ISBN 978-3-540-46384-9, получено 2024-08-24
  25. ^ ab Гловер, Фред; Сёренсен, Кеннет (2015). «Метаэвристика». Scholarpedia . 10 (4): 6532. doi : 10.4249/scholarpedia.6532 . ISSN  1941-6016.
  26. ^ Бираттари, Мауро; Пакете, Луис; Штютцле, Томас; Варрентрапп, Клаус (2001). «Классификация метаэвристик и планирование экспериментов для анализа компонентов». S2CID  18347906.
  27. ^ D, Binu (2019). «RideNN: Новая нейронная сеть на основе алгоритма оптимизации Rider для диагностики неисправностей в аналоговых схемах». Труды IEEE по приборостроению и измерениям . 68 (1): 2–26. Bibcode : 2019ITIM...68....2B. doi : 10.1109/TIM.2018.2836058. S2CID  54459927.
  28. ^ ab Pang, Shinsiong; Chen, Mu-Chen (2023-06-01). «Оптимизация планирования работы железнодорожной бригады с помощью модифицированного алгоритма поиска пищи бактериями». Компьютеры и промышленная инженерия . 180 : 109218. doi : 10.1016/j.cie.2023.109218. ISSN  0360-8352. S2CID  257990456.
  29. ^ М. Дориго, Оптимизация, обучение и естественные алгоритмы , докторская диссертация, Миланский технический университет, Италия, 1992.
  30. ^ ab Moscato, P. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: на пути к меметическим алгоритмам». Программа параллельных вычислений Caltech (отчет 826).
  31. ^ Канту-Пас, Эрик (2001). Эффективные и точные параллельные генетические алгоритмы. Генетические алгоритмы и эволюционные вычисления. Том 1. Бостон, Массачусетс: Springer US. doi : 10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6.
  32. ^ ab Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (ред.), «Параллельные эволюционные алгоритмы», Springer Handbook of Computational Intelligence , Берлин, Гейдельберг: Springer, стр. 929–959, doi :10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, получено 2024-09-04
  33. ^ ab Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02), "Универсальная гибкая и масштабируемая структура для иерархической распараллеливания метаэвристик на основе населения", Proc. 12th Int. Conf. on Management of Digital EcoSystems (MEDES'20) , ACM, стр. 124–131, doi : 10.1145/3415958.3433041, ISBN 978-1-4503-8115-4
  34. ^ Свон, Джерри; Адриансен, Стивен; Бишр, Мохамед; Берк, Эдмунд К.; Кларк, Джон А.; Де Каусмаке, Патрик; Дурилло, Хуан Хосе; Хаммонд, Кевин; Харт, Эмма; Джонсон, Колин Г.; Кочиш, Золтан А.; Ковиц, Бен; Кравец, Кшиштоф; Мартин, Саймон; Мерело, Хуан Дж.; Минку, Леандро Л.; Озкан, Эндер; Паппа, Жизель Лобо; Пеш, Эрвин; Гарсиа-Санчес, Пабло; Шерф, Андреа; Сим, Кевин; Смит, Джим; Штютцле, Томас; Вагнер, Стефан (2015). «План исследований метаэвристической стандартизации». Семантический учёный . Получено 30 августа 2024 г.
  35. ^ "Journal of Heuristic Policies on Heuristic Search Research" (PDF) . Journal of Heuristics - Руководство по подаче заявок . Архивировано из оригинала 2017-07-09 . Получено 2024-09-01 .
  36. ^ "Цели и масштаб". 4OR . Получено 2024-09-01 .
  37. ^ "Цели и область применения". Меметические вычисления . Получено 2024-09-01 .
  38. ^ Алмейда, Франциско; Блеса Агилера, Мария Х.; Блюм, Кристиан; Морено Вега, Хосе Маркос; Перес Перес, Мелькиадес; Роли, Андреа; Сампелс, Майкл, ред. (2006). Гибридная метаэвристика. Конспекты лекций по информатике. Том. 4030. Берлин, Гейдельберг: Springer. дои : 10.1007/11890584. ISBN 978-3-540-46384-9.
  39. ^ Нери, Ферранте; Котта, Карлос; Москато, Пабло, ред. (2012). Справочник по меметическим алгоритмам. Исследования по вычислительному интеллекту. Т. 379. Берлин, Гейдельберг: Springer Berlin Heidelberg. doi :10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6.
  40. ^ Дориго, М.; Гамбарделла, Л. М. (апрель 1997 г.). «Система колонии муравьев: подход к решению проблемы коммивояжера с использованием кооперативного обучения». Труды IEEE по эволюционным вычислениям . 1 (1): 53–66. doi :10.1109/4235.585892.
  41. ^ Мерц, Питер; Фрейслебен, Бернд (2002). «Меметические алгоритмы для задачи коммивояжера». Сложные системы . 13 (4).
  42. ^ Томояга Б., Чиндрис М., Сумпер А., Судрия-Андреу А., Виллафафила-Роблес Р. Оптимальная по Парето реконфигурация систем распределения электроэнергии с использованием генетического алгоритма на основе NSGA-II. Энергии. 2013; 6(3):1439–1455.
  43. ^ Ганесан, Т.; Эламвазути, И.; Ку Шаари, Ку Зилати; Васант, П. (2013-03-01). «Алгоритм роевого интеллекта и гравитационного поиска для многоцелевой оптимизации производства синтез-газа». Applied Energy . 103 : 368–374. Bibcode : 2013ApEn..103..368G. doi : 10.1016/j.apenergy.2012.09.059.
  44. ^ Ганесан, Т.; Эламвазути, И.; Васант, П. (2011-11-01). "Метод эволюционного пересечения нормалей и границ (ENBI) для многокритериальной оптимизации системы формовочной смеси". Международная конференция IEEE по системам управления, вычислениям и инжинирингу 2011 г. . стр. 86–91. doi :10.1109/ICCSCE.2011.6190501. ISBN 978-1-4577-1642-3. S2CID  698459.
  45. ^ Xhafa, Fatos; Abraham, Ajith, ред. (2008). Метаэвристика для планирования в промышленных и производственных приложениях. Исследования по вычислительному интеллекту. Т. 128. Берлин, Гейдельберг: Springer Berlin Heidelberg. doi :10.1007/978-3-540-78985-7. ISBN 978-3-540-78984-0. S2CID  42238720.
  46. ^ Якоб, Вильфрид; Штрак, Сильвия; Квинте, Александр; Бенгель, Гюнтер; Штуки, Карл-Уве; Зюсс, Вольфганг (2013-04-22). «Быстрое перепланирование нескольких рабочих процессов для ограниченных гетерогенных ресурсов с использованием многокритериальных меметических вычислений». Алгоритмы . 6 (2): 245–277. doi : 10.3390/a6020245 . ISSN  1999-4893.
  47. ^ Кизилай, Дамла; Тасгетирен, М. Фатих; Пан, Куан-Ке; Сюэр, Гюрсель (2019). «Ансамбль мета-эвристик для проблемы планирования энергоэффективного блокирующего потокового цеха». Procedia Manufacturing . 39 : 1177–1184. doi : 10.1016/j.promfg.2020.01.352 . S2CID  213710393.
  48. ^ Грош, Бенедикт; Вайцель, Тимм; Пантен, Никлас; Абеле, Эберхард (2019). «Метаэвристика для адаптивного планирования производства энергии с несколькими энергоносителями и ее реализация в реальной производственной системе». Procedia CIRP . 80 : 203–208. doi : 10.1016/j.procir.2019.01.043 . S2CID  164850023.
  49. ^ ab Holland, JH (1975). Адаптация в естественных и искусственных системах . Издательство Мичиганского университета. ISBN 978-0-262-08213-6.
  50. ^ ab Гловер, Фред (1977). «Эвристика для целочисленного программирования с использованием суррогатных ограничений». Decision Sciences . 8 (1): 156–166. CiteSeerX 10.1.1.302.4071 . doi :10.1111/j.1540-5915.1977.tb01074.x. 
  51. ^ ab Glover, F. (1986). «Будущие пути целочисленного программирования и связи с искусственным интеллектом». Computers and Operations Research . 13 (5): 533–549. doi :10.1016/0305-0548(86)90048-1.
  52. ^ Квинт, Александр; Якоб, Вильфрид; Шерер, Клаус-Питер; Эггерт, Хорст (2002), Лаудон, Мэтью (ред.), «Оптимизация пластины микроактюатора с использованием эволюционных алгоритмов и моделирования на основе методов дискретных элементов», Международная конференция по моделированию и имитации микросистем: MSM 2002 , Кембридж, Массачусетс: Computational Publications, стр. 192–197, ISBN 978-0-9708275-7-9
  53. ^ Parmee, IC (1997), Dasgupta, Dipankar; Michalewicz, Zbigniew (ред.), "Стратегии интеграции эволюционного/адаптивного поиска с процессом инженерного проектирования", Evolutionary Algorithms in Engineering Applications , Berlin, Heidelberg: Springer, стр. 453–477, doi :10.1007/978-3-662-03423-1_25, ISBN 978-3-642-08282-5, получено 2023-07-17
  54. ^ Валади, Джаяраман; Сиарри, Патрик, ред. (2014). Применение метаэвристики в проектировании процессов. Cham: Springer International Publishing. doi : 10.1007/978-3-319-06508-3. ISBN 978-3-319-06507-6. S2CID  40197553.
  55. ^ Санчес, Эрнесто; Скильеро, Джованни; Тонда, Альберто (2012). Промышленные приложения эволюционных алгоритмов. Справочная библиотека интеллектуальных систем. Том 34. Берлин, Гейдельберг: Springer. doi :10.1007/978-3-642-27467-1. ISBN 978-3-642-27466-4.
  56. ^ Акан, Таймаз; Антер, Ахмед М.; Этанер-Уяр, А. Шима; Олива, Диего, ред. (2023). Инженерные приложения современных метаэвристик. Исследования по вычислительному интеллекту. Т. 1069. Cham: Springer International Publishing. doi : 10.1007/978-3-031-16832-1. ISBN 978-3-031-16831-4. S2CID  254222401.
  57. ^ Blume, Christian (2000), Cagnoni, Stefano (ред.), "Оптимизированная генерация операторов перемещения робота без столкновений с помощью эволюционного программного обеспечения GLEAM", Реальные приложения эволюционных вычислений , Lecture Notes in Computer Science, т. 1803, Берлин, Гейдельберг: Springer, стр. 330–341, doi :10.1007/3-540-45561-2_32, ISBN 978-3-540-67353-8, получено 2023-07-17
  58. ^ Фолди, Нантиват; Бурерат, Суджин (2018-12-14), «Многоцелевое планирование траектории 6D-робота на основе многоцелевого метаэвристического поиска», Международная конференция по сетям, коммуникациям и вычислениям (ICNCC 2018) , ACM, стр. 352–356, doi :10.1145/3301326.3301356, ISBN 978-1-4503-6553-6, S2CID  77394395
  59. ^ Аб Парехо, Хосе Антонио; Руис-Кортес, Антонио; Лосано, Себастьян; Фернандес, Пабло (март 2012 г.). «Метаэвристические системы оптимизации: исследование и сравнительный анализ». Мягкие вычисления . 16 (3): 527–561. дои : 10.1007/s00500-011-0754-8. ISSN  1432-7643.
  60. ^ Гарсия-Вальдес, Марио; Мерело, Дж. Дж. (2017-07-15), «evospace-js: асинхронное выполнение разнородных метаэвристик на основе пула», GECCO '17: Труды конференции по генетическим и эволюционным вычислениям, Companion , Нью-Йорк: ACM, стр. 1202–1208, doi : 10.1145/3067695.3082473, ISBN 978-1-4503-4939-0
  61. ^ Лим, Дуди; Онг, Ю-Сун; Джин, Яочу; Сендхофф, Бернхард; Ли, Бу-Сун (май 2007 г.). «Эффективные иерархические параллельные генетические алгоритмы с использованием сетевых вычислений». Future Generation Computer Systems . 23 (4): 658–670. doi :10.1016/j.future.2006.10.008.
  62. ^ Небро, Антонио Дж.; Барба-Гонсалес, Кристобаль; Ньето, Хосе Гарсия; Кордеро, Хосе А.; Монтес, Хосе Ф. Алдана (15 июля 2017 г.), «Проектирование и архитектура структуры jMetaISP», GECCO '17: Материалы конференции по генетическим и эволюционным вычислениям, Companion , Нью-Йорк: ACM, стр. 1239–1246, дои : 10.1145/3067695.3082466, ISBN 978-1-4503-4939-0
  63. ^ Роббинс, Х.; Монро, С. (1951). "Метод стохастической аппроксимации" (PDF) . Annals of Mathematical Statistics . 22 (3): 400–407. doi : 10.1214/aoms/1177729586 .
  64. ^ Барричелли, Н.А. (1954). «Числовые примеры процесса эволюции». Методы : 45–68.
  65. ^ Растригина, Л.А. (1963). «Сходимость метода случайного поиска при экстремальном управлении многопараметрической системой». Автоматика и телемеханика . 24 (10): 1337–1342.
  66. ^ Матьяс, Дж. (1965). «Случайная оптимизация». Автоматизация и телеуправление . 26 (2): 246–253.
  67. ^ Nelder, JA; Mead, R. (1965). «Симплексный метод минимизации функций». Computer Journal . 7 (4): 308–313. doi :10.1093/comjnl/7.4.308. S2CID  2208295.
  68. ^ Рехенберг, Инго (1965). «Кибернетический путь решения экспериментальной проблемы». Королевское авиационное учреждение, Библиотечный перевод .
  69. ^ Фогель, Л.; Оуэнс, А.Дж.; Уолш, М.Дж. (1966). Искусственный интеллект через имитацию эволюции . Wiley. ISBN 978-0-471-26516-0.
  70. ^ Hastings, WK (1970). «Методы выборки Монте-Карло с использованием цепей Маркова и их применение». Biometrika . 57 (1): 97–109. Bibcode : 1970Bimka..57...97H. doi : 10.1093/biomet/57.1.97. S2CID  21204149.
  71. ^ Cavicchio, DJ (1970). «Адаптивный поиск с использованием симулированной эволюции». Технический отчет . Мичиганский университет, Кафедра компьютерных и коммуникационных наук. hdl :2027.42/4042.
  72. ^ Керниган, Б. В.; Лин, С. (1970). «Эффективная эвристическая процедура для разбиения графов». Bell System Technical Journal . 49 (2): 291–307. doi :10.1002/j.1538-7305.1970.tb01770.x.
  73. ^ Мерсер, Р. Э.; Сэмпсон, Дж. Р. (1978). «Адаптивный поиск с использованием репродуктивного метаплана». Kybernetes . 7 (3): 215–228. doi :10.1108/eb005486.
  74. ^ Смит, С. Ф. (1980). Система обучения на основе генетических адаптивных алгоритмов (кандидатская диссертация). Университет Питтсбурга.
  75. ^ Киркпатрик, С.; Гелатт-младший, CD; Векки, MP (1983). «Оптимизация с помощью имитации отжига». Science . 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. 
  76. ^ Москато, П.; Фонтанари, Дж. Ф. (1990), «Стохастическое и детерминированное обновление в моделируемом отжиге», Physics Letters A , 146 (4): 204–208, Bibcode : 1990PhLA..146..204M, doi : 10.1016/0375-9601(90)90166-L
  77. ^ Дьюк, Г.; Шойер, Т. (1990), «Принятие порога: универсальный алгоритм оптимизации, превосходящий имитацию отжига», Журнал вычислительной физики , 90 (1): 161–175, Bibcode : 1990JCoPh..90..161D, doi : 10.1016/0021-9991(90)90201-B, ISSN  0021-9991
  78. ^ Вулперт, Д. Х.; Макреди, В. Г. (1995). «Нет теорем о бесплатном обеде для поиска». Технический отчет SFI-TR-95-02-010 . Институт Санта-Фе. S2CID  12890367.
  79. ^ Igel, Christian, Toussaint, Marc (июнь 2003 г.). «О классах функций, для которых результаты No Free Lunch справедливы». Information Processing Letters . 86 (6): 317–321. arXiv : cs/0108011 . doi :10.1016/S0020-0190(03)00222-9. ISSN  0020-0190. S2CID  147624.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  80. ^ Оже, Энн , Тейто, Оливье (2010). «Непрерывные обеды бесплатны плюс разработка оптимальных алгоритмов оптимизации». Algorithmica . 57 (1): 121–146. CiteSeerX 10.1.1.186.6007 . doi :10.1007/s00453-008-9244-5. ISSN  0178-4617. S2CID  1989533. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  81. ^ Стефан Дросте; Томас Янсен; Инго Вегенер (2002). «Оптимизация с помощью эвристики рандомизированного поиска – теорема (A)NFL, реалистичные сценарии и сложные функции». Теоретическая информатика . 287 (1): 131–144. CiteSeerX 10.1.1.35.5850 . doi :10.1016/s0304-3975(02)00094-4. 

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

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