Меметический алгоритм - Memetic algorithm

Часть серия на
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

В Информатика и исследование операций, а меметический алгоритм (MA) является продолжением традиционного генетический алгоритм. Он использует местный поиск техника для снижения вероятности преждевременного схождения.[1]

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

Вступление

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

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

В общем, использование идей меметики в вычислительной структуре называется «меметические вычисления или меметические вычисления» (MC).[4][5]В MC более уместно уловить черты универсального дарвинизма. С этой точки зрения MA - это более ограниченное понятие MC. Более конкретно, MA охватывает одну область MC, в частности, касается областей эволюционных алгоритмов, которые сочетаются с другими детерминированными методами уточнения для решения задач оптимизации. MC расширяет понятие мемов, чтобы охватить концептуальные сущности процедур или представлений с расширенными знаниями.

Развитие МА

1 поколение

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

Псевдокод
   Процедура Меметический алгоритм Инициализировать: Создайте начальную популяцию; пока Условия остановки не выполнены делать       Оценивать все особи в популяции. Эволюционировать новая популяция с использованием операторов стохастического поиска. Выбирать подмножество людей, , которые должны пройти процедуру индивидуального улучшения. за каждый человек в  делать           Выполнять индивидуальное обучение с использованием мемов с частотой или вероятностью , в течение периода от .           Продолжить с ламаркианским или балдвинским обучением. конец для   конец пока

2-е поколение

Мульти-мем,[6] Гиперэвристический[7][8] и Мета-Ламарка М.А.[9] относятся к МА второго поколения, демонстрируя принципы меметической передачи и выбора в их конструкции. В Multi-meme MA меметический материал кодируется как часть генотип. Впоследствии декодированный мем каждого человека /хромосома затем используется для выполнения локального уточнения. Затем меметический материал передается через простой механизм наследования от родителей к потомкам. С другой стороны, в гиперэвристической и мета-ламаркианской MA пул рассматриваемых мемов-кандидатов будет конкурировать на основе их прошлых заслуг в создании локальных улучшений с помощью механизма вознаграждения, решая, какой мем выбрать, чтобы перейти к будущим локальным уточнениям. . Мемы с более высокой наградой имеют больше шансов быть воспроизведены или скопированы. Для обзора МА второго поколения; то есть магистерская программа, рассматривающая несколько индивидуальных методов обучения в рамках эволюционной системы, к читателю.[10]

3-е поколение

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

Некоторые примечания к дизайну

Частота и интенсивность индивидуального обучения напрямую определяют степень эволюции (исследования) по сравнению с индивидуальным обучением (эксплуатацией) в поиске МА при заданном фиксированном ограниченном вычислительном бюджете. Очевидно, что более интенсивное индивидуальное обучение дает больше шансов на сходимость к локальным оптимумам, но ограничивает объем эволюции, которая может быть затрачена без чрезмерных вычислительных ресурсов. Таким образом, следует соблюдать осторожность при установке этих двух параметров, чтобы сбалансировать доступный вычислительный бюджет для достижения максимальной производительности поиска. Когда только часть населения проходит обучение, необходимо рассмотреть вопрос о том, какое подмножество людей следует улучшить, чтобы максимизировать полезность поиска МА. И последнее, но не менее важное: индивидуальная процедура обучения / мем, используемые также, благоприятствуют другой структуре соседства, поэтому необходимо решить, какой мем или мемы использовать для данной задачи оптимизации.

Как часто следует применять индивидуальное обучение?

Одна из первых проблем, связанных с разработкой меметических алгоритмов, - это рассмотрение того, как часто следует применять индивидуальное обучение; т.е. индивидуальная частота обучения. В одном случае[13] влияние индивидуальной частоты обучения на эффективность поиска МА было рассмотрено, когда были исследованы различные конфигурации индивидуальной частоты обучения на разных этапах поиска МА. Напротив, это было показано в другом месте[14] что, возможно, имеет смысл применять индивидуальное обучение к каждому человеку, если вычислительная сложность индивидуального обучения относительно невысока.

На каких решениях следует использовать индивидуальное обучение?

По вопросу выбора подходящих людей среди популяции EA, которые должны пройти индивидуальное обучение, были изучены стратегии, основанные на фитнесе и распределении, для адаптации вероятности применения индивидуального обучения к популяции хромосом в задачах непрерывного параметрического поиска с помощью Land[15] расширение работы на комбинаторная оптимизация проблемы. Bambha et al. представила технику моделирования нагрева для систематической интеграции параметризованного индивидуального обучения в эволюционные алгоритмы для достижения максимального качества решения.[16]

Как долго нужно проводить индивидуальное обучение?

Индивидуальная интенсивность обучения, , - объем вычислительного бюджета, выделенный на итерацию индивидуального обучения; т. е. максимальный вычислительный бюджет, который можно потратить на индивидуальное обучение на улучшение единственного решения.

Какой индивидуальный метод обучения или мем следует использовать для конкретной проблемы или человека?

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

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

Приложения

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

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

Более свежие приложения включают (но не ограничиваются) бизнес-аналитика и наука о данных,[3]обучение искусственные нейронные сети,[18] распознавание образов,[19] робот планирование движения,[20] луч ориентация,[21] схемотехника,[22] восстановление электроснабжения,[23] медицинский экспертные системы,[24] планирование на одной машине,[25] автоматическое расписание (в частности, расписание НХЛ ),[26] планирование рабочей силы,[27] Оптимизация списка медсестер,[28] распределение процессора,[29] график технического обслуживания (например, распределительной электрической сети),[30] многомерная задача о ранце,[31] СБИС дизайн,[32] кластеризация из профили экспрессии генов,[33] выбор признака / гена,[34][35] и мульти-класс, многоцелевой выбор функции.[36][37]

Последние действия в меметических алгоритмах

Рекомендации

  1. ^ Пунам Гарг (апрель 2009 г.). «Сравнение меметического алгоритма и генетического алгоритма для криптоанализа упрощенного стандартного алгоритма шифрования данных». Международный журнал сетевой безопасности и ее приложений (IJNSA). 1 (1). arXiv:1004.0574. Bibcode:2010arXiv1004.0574G.
  2. ^ а б Москато, П. (1989). «Об эволюции, поиске, оптимизации, генетических алгоритмах и боевых искусствах: к меметическим алгоритмам». Программа параллельных вычислений Caltech (отчет 826).
  3. ^ а б Moscato, P .; Мэтисон, Л. (2019). «Меметические алгоритмы для бизнес-аналитики и науки о данных: краткий обзор». Бизнес и потребительская аналитика: новые идеи. Springer. С. 545–608. Дои:10.1007/978-3-030-06222-4_13. ISBN  978-3-030-06221-7.
  4. ^ Chen, X. S .; Онг, Ю. С .; Lim, M. H .; Тан, К. С. (2011). «Многогранный обзор меметических вычислений». IEEE Transactions по эволюционным вычислениям. 15 (5): 591–607. Дои:10.1109 / tevc.2011.2132725.
  5. ^ Chen, X. S .; Онг, Ю. С .; Лим, М. Х. (2010). «Границы исследований: меметические вычисления - прошлое, настоящее и будущее». Журнал IEEE Computational Intelligence Magazine. 5 (2): 24–36. Дои:10.1109 / mci.2010.936309.
  6. ^ Красногор Н. (1999). «Коэволюция генов и мемов в меметических алгоритмах». Мастерская аспирантов: 371.
  7. ^ Кендалл Г., Субейга Э. и Коулинг П. Функция выбора и случайная гиперэвристика (PDF). 4-я Азиатско-Тихоокеанская конференция по моделированию эволюции и обучения. SEAL 2002. С. 667–671.
  8. ^ Burke E.K .; Gendreau M .; Hyde M .; Kendall G .; Ochoa G .; Оумл; zcan E .; Цюй Р. (2013). «Гиперэвристика: обзор современного состояния». Журнал Общества оперативных исследований. 64 (12): 1695–1724. CiteSeerX  10.1.1.384.9743. Дои:10.1057 / jors.2013.71.
  9. ^ Онг Ю. С. и Кин А. Дж. (2004). «Мета-ламарковское обучение в меметических алгоритмах» (PDF). IEEE Transactions по эволюционным вычислениям. 8 (2): 99–110. Дои:10.1109 / TEVC.2003.819944.
  10. ^ Онг Ю. С. и Лим М. Х., Чжу Н. и Вонг К. В. (2006). «Классификация адаптивных меметических алгоритмов: сравнительное исследование» (PDF). Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 36 (1): 141–152. Дои:10.1109 / TSMCB.2005.856143. PMID  16468573.
  11. ^ Смит Дж. Э. (2007). «Коэволюция меметических алгоритмов: обзор и отчет о проделанной работе» (PDF). Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 37 (1): 6–17. Дои:10.1109 / TSMCB.2006.883273. PMID  17278554.
  12. ^ Красногор Н. и Густафсон С. (2002). «К истинно« меметическим »меметическим алгоритмам: обсуждение и доказательство концепций». Достижения в естественных вычислениях: семинары PPSN VII. PEDAL (Лаборатория параллельных возникающих и распределенных архитектур). Университет Ридинга.
  13. ^ Харт В. Э. (1994). «Адаптивная глобальная оптимизация с локальным поиском». Калифорнийский университет. CiteSeerX  10.1.1.473.1370. Цитировать журнал требует | журнал = (помощь)
  14. ^ Ку К. В. К., Мак М. В. и Сиу В. К. (2000). «Исследование ламарковской эволюции рекуррентных нейронных сетей». IEEE Transactions по эволюционным вычислениям. 4 (1): 31–42. Дои:10.1109/4235.843493. HDL:10397/289.
  15. ^ Лэнд М. В. С. (1998). «Эволюционные алгоритмы с локальным поиском комбинаторной оптимизации». КАЛИФОРНИЙСКИЙ УНИВЕРСИТЕТ. CiteSeerX  10.1.1.55.8986. Цитировать журнал требует | журнал = (помощь)
  16. ^ Бамбха Н. К. и Бхаттачарья С. С., Тейч Дж. И Зицлер Э. (2004). «Систематическая интеграция параметризованного локального поиска в эволюционные алгоритмы». IEEE Transactions по эволюционным вычислениям. 8 (2): 137–155. Дои:10.1109 / TEVC.2004.823471.
  17. ^ Швефель Х. П. (1995). Эволюция и поиск оптимума. Wiley New York.
  18. ^ Ichimura, T .; Курияма, Ю. (1998). Изучение нейронных сетей с параллельным гибридным ГА с использованием функции королевской дороги. Международная совместная конференция IEEE по нейронным сетям. 2. Нью-Йорк, штат Нью-Йорк. С. 1131–1136. Дои:10.1109 / IJCNN.1998.685931.
  19. ^ Aguilar, J .; Кольменарес, А. (1998). «Решение проблем распознавания образов с использованием гибридного генетического / случайного алгоритма обучения нейронной сети». Анализ шаблонов и приложения. 1 (1): 52–61. Дои:10.1007 / BF01238026.
  20. ^ Ridao, M .; Riquelme, J .; Камачо, Э .; Торо, М. (1998). Алгоритм эволюционного и локального поиска для планирования движения двух манипуляторов. Конспект лекций по информатике. 1416. Springer-Verlag. С. 105–114. CiteSeerX  10.1.1.324.2668. Дои:10.1007/3-540-64574-8_396. ISBN  978-3-540-64574-0.
  21. ^ Haas, O .; Burnham, K .; Миллс, Дж. (1998). «Оптимизация ориентации луча в лучевой терапии с использованием плоской геометрии». Физика в медицине и биологии. 43 (8): 2179–2193. Bibcode:1998ПМБ .... 43.2179Н. Дои:10.1088/0031-9155/43/8/013. PMID  9725597.
  22. ^ Harris, S .; Ифичор, Э. (1998). «Автоматическое построение частотных выборочных фильтров методами гибридного генетического алгоритма». Транзакции IEEE при обработке сигналов. 46 (12): 3304–3314. Bibcode:1998ITSP ... 46.3304H. Дои:10.1109/78.735305.
  23. ^ Augugliaro, A .; Dusonchet, L .; Рива-Сансеверино, Э. (1998). «Восстановление услуг в компенсированных распределительных сетях с использованием гибридного генетического алгоритма». Исследование электроэнергетических систем. 46 (1): 59–66. Дои:10.1016 / S0378-7796 (98) 00025-X.
  24. ^ Wehrens, R .; Лукасий, C .; Buydens, L .; Катеман, Г. (1993). «HIPS, гибридная самонастраивающаяся экспертная система для интерпретации спектра ядерного магнитного резонанса с использованием генетических алгоритмов». Analytica Chimica Acta. 277 (2): 313–324. Дои:10.1016 / 0003-2670 (93) 80444-П. HDL:2066/112321.
  25. ^ França, P .; Mendes, A .; Москато, П. (1999). Меметические алгоритмы для минимизации опозданий на одной машине с зависимым от последовательности временем настройки (PDF). Труды 5-й Международной конференции института Decision Sciences. Афины, Греция. С. 1708–1710.
  26. ^ Коста, Д. (1995). «Эволюционный алгоритм поиска табу и проблема планирования НХЛ». Инфор 33: 161–178.
  27. ^ Айкелин, У. (1998). Список медсестер с генетическими алгоритмами. Труды молодой конференции по операционным исследованиям 1998 г. Гилфорд, Великобритания. arXiv:1004.2870.
  28. ^ Озджан, Э. (2007). «Мемы, самогенерация и состав медсестер». Практика и теория автоматического составления расписания VI. Конспект лекций по информатике. 3867. Springer-Verlag. С. 85–104. Дои:10.1007/978-3-540-77345-0_6. ISBN  978-3-540-77344-3.
  29. ^ Ozcan, E .; Онбасиоглу, Э. (2007). «Меметические алгоритмы для оптимизации параллельного кода». Международный журнал параллельного программирования. 35 (1): 33–61. Дои:10.1007 / s10766-006-0026-х.
  30. ^ Burke, E .; Смит, А. (1999). «Меметический алгоритм для планирования планового технического обслуживания национальной сети». Журнал экспериментальной алгоритмики. 4 (4): 1–13. Дои:10.1145/347792.347801.
  31. ^ Ozcan, E .; Басаран, К. (2009). «Пример меметических алгоритмов для оптимизации ограничений». Мягкие вычисления: сочетание основ, методологий и приложений. 13 (8–9): 871–882. CiteSeerX  10.1.1.368.7327. Дои:10.1007 / s00500-008-0354-4.
  32. ^ Арейби, С., Янг, З. (2004). «Эффективные меметические алгоритмы для автоматизации проектирования СБИС = генетические алгоритмы + локальный поиск + многоуровневая кластеризация». Эволюционные вычисления. 12 (3): 327–353. Дои:10.1162/1063656041774947. PMID  15355604.CS1 maint: несколько имен: список авторов (связь)
  33. ^ Merz, P .; Зелл, А. (2002). «Кластеризация профилей экспрессии генов с меметическими алгоритмами». Параллельное решение проблем с натуры - PPSN VII. Конспект лекций по информатике. 2439. Springer. С. 811–820. Дои:10.1007/3-540-45712-7_78. ISBN  978-3-540-44139-7.
  34. ^ Цзэсюань Чжу, Ю. С. Онг и М. Даш (2007). "Марковский бланкет-встроенный генетический алгоритм для отбора генов". Распознавание образов. 49 (11): 3236–3248. Дои:10.1016 / j.patcog.2007.02.007.
  35. ^ Цзэсюань Чжу, Ю. С. Онг и М. Даш (2007). «Алгоритм выбора функции Wrapper-Filter с использованием меметической структуры». Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 37 (1): 70–76. Дои:10.1109 / TSMCB.2006.883267. HDL:10338.dmlcz / 141593. PMID  17278560.
  36. ^ Цзэсюань Чжу, Ю.С. Онг и М. Зурада (2008). «Одновременная идентификация генов полного и частичного класса». IEEE / ACM Transactions по вычислительной биологии и биоинформатике.
  37. ^ Г. Каркавицас и Г. Цихринцис (2011). Автоматическая классификация музыкальных жанров с использованием гибридных генетических алгоритмов. Интеллектуальные интерактивные мультимедийные системы и услуги. Умные инновации, системы и технологии. 11. Springer. С. 323–335. Дои:10.1007/978-3-642-22158-3_32. ISBN  978-3-642-22157-6.