Меметический алгоритм (МА) — это развитие эволюционного алгоритма (ЭА), целью которого является ускорение поиска оптимального решения. Эволюционный алгоритм — это метаалгоритм, который имитирует основные принципы биологической эволюции в виде компьютерной программы для решения сложных задач оптимизации или планирования, хотя бы приближённо. Меметический алгоритм использует одну или несколько подходящих эвристик или техник локального поиска для улучшения качества решений, полученных эволюционным алгоритмом, и для ускорения поиска. Влияние на надёжность нахождения глобального оптимума зависит как от конкретного применения, так и от структуры самого МА.
Меметические алгоритмы представляют одну из активно развивающихся областей исследований в эволюционных вычислениях. Термин меметический алгоритм сейчас широко используется как синергия эволюционных или любых популяционных подходов с отдельными процедурами индивидуального обучения или локального улучшения для поиска решений задач. Нередко в литературе меметические алгоритмы также называют эволюционными алгоритмами Болдуина, ламарковскими эволюционными алгоритмами, культурными алгоритмами или генетическим локальным поиском.
Введение Вдохновлённый дарвиновскими принципами естественной эволюции и концепцией мема Докинза, Пабло Москато предложил термин меметический алгоритм в техническом отчете 1989 года, где он рассматривал меметический алгоритм как разновидность гибридного генетического алгоритма, основанного на популяциях, который дополнен процедурой индивидуального обучения, способной выполнять локальные улучшения. Метафорические параллели, с одной стороны с дарвиновской эволюцией, а с другой — между мемами и эвристиками, специфичными для конкретной области (локальный поиск), захвачены меметическими алгоритмами, что позволяет создать методологию, которая хорошо сбалансирована между общностью и спецификой проблемы. Такая двухэтапная природа делает их особым случаем .
В области сложных оптимизационных задач было предложено множество различных реализаций меметических алгоритмов для широкого спектра областей применения. В целом, они сходятся к высококачественным решениям более эффективно, чем их традиционные эволюционные аналоги.
Применение принципов меметики в рамках вычислительных систем известно как или меметические расчёты. Такой подход лучше отражает универсальные принципы дарвинизма. В этом контексте меметические алгоритмы представляют собой более узкое понятие, охватывающее лишь часть меметических вычислений, а именно те области эволюционных алгоритмов, которые сочетаются с другими детерминированными методами уточнения для решения задач оптимизации. Меметические вычисления расширяют понятие мемов, включая в него концептуальные сущности, основанные на обогащенных знаниями процедурах или представлениях.
Теоретические основы Теорема «Бесплатного обеда не бывает» для оптимизации и поиска утверждает, что все стратегии оптимизации одинаково эффективны для всего множества задач оптимизации. Иными словами, чем эффективнее алгоритм решает конкретную задачу или класс задач, тем менее он универсален и тем больше опирается на специфические знания о проблеме. Это понимание прямо указывает на необходимость дополнять общеприменимые метаэвристики методами или эвристиками, специфичными для конкретного приложения, что хорошо согласуется с концепцией гибридных алгоритмов.
Развитие меметических алгоритмов
Первое поколение Пабло Москато описал меметический алгоритм следующим образом: «Меметические алгоритмы являются сочетанием глобального поиск на основе популяции и эвристического локального поиска, выполняемого каждым отдельным элементом. ... Механизмы локального поиска могут быть направлены на достижение локального оптимума или на улучшение до заданного уровня относительно целевой функции стоимости». Он подчёркивает: «Я не ограничиваю меметический алгоритм генетическим представлением». Хотя это первоначальное определение меметического алгоритма включает в себя элементы культурной эволюции (в виде локального уточнения) в цикле поиска, оно не вполне соответствует критериям истинной эволюционирующей системы согласно , поскольку в нём отсутствуют все основные принципы наследования/меметической передачи, вариации и отбора. Это объясняет, почему термин «меметический алгоритм» вызвал критику и споры среди исследователей при его первом появлении. Следующий псевдокод соответствует этому общему определению меметического алгоритма:
Псевдокод Procedure Меметический алгоритм Initialize: Генерируем начальную популяцию, оцениваем особей и присваиваем им значение качества; while Условие останова не выполнятся do Выделить новую популяцию с помощью поиска. Пересчитать все индивиды в популяции и присвоить им значение качества.. , которые должны пройти процедуру индивидуального улучшения.
Осуществить индивидуальное обучение с помощью meme(s) , Осуществить обучение по Ламарку или Болдуину. end for end while
Мета-обучения Ламарка в данном контексте означает обновление хромосомы в соответствии с улучшенным решением, найденным на этапе индивидуального обучения, тогда как обучение Болдуина оставляет хромосому неизменной и использует только улучшенную приспособленность приспособленность. Этот псевдокод не уточняет, какие шаги основаны на приспособленности особей, а какие нет. Вопросы возникают относительно эволюции новой популяции и выбора .
Поскольку большинство реализаций МА основаны на ЭА, здесь также приводится псевдокод соответствующего представителя первого поколения, согласно Красногору:
псевдокод Procedure Меметический алгоритм на основе EA Initialization: ; // Инициализация счётчика поколений Случайным образом генерируем начальную популяцию ; Вычисляем приспособленность ; while Условие останова не выполнятся do
if обучение Ламарка then
fi Новое поколение: ; // Увеличиваем счётчик поколений end while Return лучшую особь как результат;
Существуют альтернативные варианты данной схемы МА. Например: Все или некоторые из исходных особей могут быть улучшены с помощью meme(s). Родители могут быть улучшены локально вместо потомства. Вместо всего потомства только случайно выбранная или зависящая от приспособленности часть может подвергнуться локальному улучшению. Последнее требует оценки потомства в до шага Обучение.
Второе поколение Многомемные, гиперэвристические и металамарковские МА алгоритмы относятся ко второму поколению. В их основе лежат принципы меметической передачи и отбора. В многомемных МА меметический материал кодируется как часть генотипа. Затем декодированный мем каждого отдельного индивида/хромосомы используется для локального улучшения. Меметический материал передаётся от родителя к потомку(ам) посредством простого механизма наследования. С другой стороны, в гиперэвристических и металамарковских МА пул рассматриваемых кандидатов на мемы будет конкурировать, основываясь на их прошлых заслугах в достижении локальных улучшений через механизм вознаграждения, определяя, какой мем будет выбран для дальнейших локальных улучшений. Мемы с более высоким вознаграждением имеют больше шансов на дальнейшее использование. Обзор алгоритмов второго поколения, учитывающих несколько индивидуальных методов обучения в эволюционной системе, представлен в статье Онга и коллег.
Третье поколение Коэволюция и самогенерирующиеся меметические алгоритмы могут рассматриваться как третье поколение меметических алгоритмов, в которых учтены все три принципа, соответствующие определению базовой эволюционирующей системы. В отличие от второго поколения меметических алгоритмов, предполагающих априорное знание используемых мемов, третье поколение использует локальный поиск на основе правил для дополнения кандидатных решений в рамках эволюционной системы, тем самым улавливая регулярно повторяющиеся особенности или закономерности в пространстве задачи.
Некоторые замечания по дизайну Используемый метод обучения/мем, значительно влияет на результаты улучшения, поэтому важно тщательно выбирать, какой метод или методы применять для конкретной задачи оптимизации. Частота и интенсивность индивидуального обучения напрямую определяют степень эволюции по сравнению с индивидуальным обучением в поиске при заданном ограниченном вычислительном бюджете. Очевидно, что более интенсивное индивидуальное обучение увеличивает вероятность сходимости к локальным оптимумам, но ограничивает объем эволюции, который может быть использован без чрезмерных вычислительных затрат. Поэтому следует внимательно подходить к настройке этих двух параметров, чтобы сбалансировать доступный вычислительный бюджет и достичь максимальной производительности поиска. Если обучение проходит только часть популяции, необходимо решить, какую подгруппу особей улучшать, чтобы максимизировать полезность поиска МА. И последнее, но не менее важное, нужно решить, следует ли изменять соответствующую особь в результате успешного обучения (обучение по Ламарку) или нет (обучение по Болдуину). Таким образом, необходимо ответить на пять проектных вопросов, первый из которых рассматривается всеми вышеупомянутыми представителями второго поколения во время выполнения MA, в то время как расширенная форма мета-ламарковского обучения распространяет это на первые четыре проектных решения.
Выбор индивидуального метода обучения или мема, которые будут использоваться для конкретной задачи или индивида В контексте непрерывной оптимизации индивидуальное обучение проявляется в виде локальных эвристик или традиционных точных перечислительных методов. Примерами стратегий индивидуального обучения являются метод восхождения к вершине, симплекс-метод, метод Ньютона и квазиньютоновские метды, методы внутренней точки, метод сопряжённых градиентов, одномерный поиск и другие локальные эвристики. Большинство распространенных методов индивидуального обучения являются детерминированными.
В комбинаторной оптимизации, с другой стороны, методы индивидуального обучения обычно существуют в виде эвристик (которые могут быть детерминированными или стохастическими), адаптированных к конкретной интересующей задаче. Типичные эвристические процедуры и схемы включают обмен генами, обмен рёбрами, поиск первого улучшения и многие другие.
Определение индивидуальной частоты обучения Один из первых вопросов, касающихся разработки меметических алгоритмов, заключается в определении частоты применения индивидуального обучения. В одном исследовании рассматривался эффект частоты индивидуального обучения на производительность поиска, где изучались различные конфигурации частоты индивидуального обучения на разных этапах поиска МА. В другом месте было показано, что может быть целесообразно применять индивидуальное обучение к каждому индивиду, если вычислительная сложность индивидуального обучения относительно низка.
Отбор индивидов, к которым применяется индивидуальное обучение При выборе подходящих особей в популяции эволюционного алгоритма для индивидуального обучения были изучены стратегии, основанные на приспособленности и распределении, для адаптации вероятности применения индивидуального обучения к популяции хромосом в задачах непрерывного параметрического поиска. Лэнд распространил эту работу на задачи комбинаторной оптимизации. Бамба и соавторы предложили технику имитации нагрева для систематической интеграции параметризованного индивидуального обучения в эволюционные алгоритмы с целью достижения максимального качества решений.
Спецификация интенсивности индивидуального обучения Интенсивность индивидуального обучения — это объём вычислительных ресурсов, выделяемых на одну итерацию индивидуального обучения. Иными словами, это максимальный вычислительный бюджет, который может быть потрачен на улучшение одного решения в рамках индивидуального обучения.
Выбор обучения по Ламарку или по Болдуину