Меметический алгоритм (МА) в информатике и исследовании операций является расширением традиционного генетического алгоритма . Это может обеспечить достаточно хорошее решение проблемы оптимизации . Он использует метод локального поиска , чтобы уменьшить вероятность преждевременной конвергенции . [1]
Меметические алгоритмы представляют собой одну из недавно развивающихся областей исследований в области эволюционных вычислений . Термин МА в настоящее время широко используется как синергия эволюционного или любого популяционного подхода с отдельными процедурами индивидуального обучения или локального улучшения для поиска проблем. Довольно часто МА также упоминаются в литературе как эволюционные алгоритмы Болдуина (ЭА), ламарковские АП, культурные алгоритмы или генетический локальный поиск.
Вдохновленный как дарвиновскими принципами естественной эволюции, так и понятием мема Докинза , термин меметический алгоритм (МА) был введен Пабло Москато в его техническом отчете [2] в 1989 году, где он рассматривал МА как близкую к форме популяции. на основе гибридного генетического алгоритма (ГА) в сочетании с индивидуальной процедурой обучения, способной выполнять локальные уточнения. Метафорические параллели, с одной стороны, с дарвиновской эволюцией, а с другой стороны, между мемами и эвристикой предметной области (локальный поиск)фиксируются в рамках меметических алгоритмов, таким образом создавая методологию, которая хорошо балансирует между общностью и специфичностью проблемы. Эта двухступенчатая природа делает их особым случаем двухфазной эволюции .
В более разнообразном контексте меметические алгоритмы теперь используются под разными названиями, включая гибридные эволюционные алгоритмы, эволюционные алгоритмы Болдуина, эволюционные алгоритмы Ламарка, культурные алгоритмы или генетический локальный поиск. В контексте комплексной оптимизации сообщалось о многих различных экземплярах меметических алгоритмов в широком диапазоне областей применения , которые, как правило, сходятся к высококачественным решениям более эффективно, чем их обычные эволюционные аналоги. [3]
В общем, использование идей меметики в вычислительной структуре называется меметическими вычислениями или меметическими вычислениями (MC). [4] [5] С MC черты универсального дарвинизма улавливаются более уместно. С этой точки зрения MA является более ограниченным понятием MC. Более конкретно, MA охватывает одну область MC, в частности, связанные с областями эволюционных алгоритмов, которые сочетаются с другими детерминированными методами уточнения для решения задач оптимизации. MC расширяет понятие мемов, чтобы охватить концептуальные объекты расширенных знаний процедур или представлений.
Первое поколение MA относится к гибридным алгоритмам , союзу глобального поиска на основе населения (часто в форме эволюционного алгоритма) в сочетании с этапом культурной эволюции. Это первое поколение МА, хотя и включает в себя характеристики культурной эволюции (в форме локального уточнения) в цикле поиска, согласно универсальному дарвинизму , оно не может квалифицироваться как истинно эволюционирующая система , поскольку все основные принципы наследственности/мемической передачи, изменчивости , и выбор отсутствует. Это говорит о том, почему термин МА вызвал критику и споры среди исследователей, когда впервые был введен. [2]