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