Вопрос 34: Меметический алгоритм

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

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

Компоненты алгоритма:

• Локальный поиск. Для осуществления локального поиска можно использовать алгоритм имитации отжига и алгоритмы подъема.
• Кооперация. Для обмена информацией между особямиможет служить процедура, аналогичная применению оператора двухточечного скрещивания в генетических алгоритмах. Технически, при этом выбирается некоторый диапазон в пределах длины решения, и соответствующие сегменты двух решений меняются местами. В резульатте получаются две новые особи, к которым впоследствии применяется процедура локальной оптимизации.
• Соревнование. Процедура селекции в целм аналогична таковой в генетических алгоритмах и обычно заключается в отборе наиболее приспособленных особей в популяции и исключении из нее менее приспособленных
• Критерий окончания поиска. Наряду с подсчетом числа итераций и оценкой улучшения резульатта определние целесообразности окончания поиска в меметических алгоритмах может включать оценку разнообразия особей. Обычно в случае вырожения популяции бессмысленно продолжать поиск.

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

• Обучение особей. Проблему баланса между популяционным и локальным поиском можно рассматривать как общую проблему соблюдения баланса межу экстенсивным и интенсивными исследованиями простраснтва поиска. Разные исследователи по-разному оценивали важность локального поиска и объем времени, который нужно ему уделять.
• Использование информации об области поиска. В отличии от большиснства эволюционных методов меметические алгоритмы обычно проблемно-специфичны. Они широко используют всю имеющуюся информацию о решаемой задаче. Это несколько усложняет их проектирование, однако значительно улучшает показываемые ими результаты.