Вопрос 11: Гибридные эволюционные алгоритмы. Меметический алгоритм. Подход Ламарка и Болдуина.

Гибритизация ГА

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

Другой распространенной формой гибридизации является внедрение адаптации параметров ГА.

Комбинирование ГА и эвристик локального поиска исследовалось многими авторами и предложено множество методов гибридизации, но наиболее распространенными является два:

1. Эволюция Ламарка (стремление к совершенству). Жирафам приходится постоянно вытягивать шею, чтобы дотянуться до листьев, растущих у них над головой. Поэтому их шеи становятся длиннее, вытягиваются.
2. Эффект Болдуина - Если ненаследственное изменение (например, изменение поведения в результате обучения) оказывается полезным, то больше потомства будут оставлять особи с лучшей наследственной предрасположенностью к такому изменению (способные быстрее и лучше научиться такому поведению).

Оба подхода используют то, что особь обучается в течение времени своего существования.

Архитектуры гибридных алгоритмов

• Несколько ЭА в одном (генетическое программирование, выводящее генетические алгоритмы)
• Нейросеть + ЭА
• Нечеткая логика + ЭА
• ЭА + алгоритм оптимизации другого класса

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

• Р. Докинз, «Эгоистичный ген», 1976
• Мемы – единицы культурной информации; идеи в умах людей, которые проявляются в поведении
• Мемы – репликаторы (объекты, которые размножаются путем копирования самих себя)
• Мемы подвержены естественному отбору

Первоначально меметические алгоритмы были предложены как один из способов повышения эффективности генетических алгоритмов.

Псевдокод меметического алгоритма:

begin
 Pop = Initialize()
 do
  Pop1 = Crossover(Pop)
  Pop2 = Improve(Pop1)
  Pop = Select(Pop2)
 while NOT TerminationCriterion
 return best(Pop)
end

Термин меметических алгоритмов был предложен для обозначения класса стохастических методов глобального поиска, которые объединяют в себе сильные стороны методов локального поиска, «заточенных» под конкретные практические задачи, и популяционных методов глобального поиска. На сегодняшний день методы данного класса успешно используются для решения задач комбинаторной, непрерывной, динамической и многокритериальной оптимизации.

Подход Ламарка и Болдуина

Подход Ламарка:

• Улучшения в фенотипе приводят к модификации генотипа
• Локальная оптимизация особи приводит к изменению ее генотипа

Подход Болдуина:

• При отборе используется значение функции приспособленности особи после локальной оптимизации
• Локальная оптимизация «не наследуется»

Сравнение:

• Ламаркианский подход дает более быструю сходимость
• Подход Балдуина требует больше итераций, но может давать более точное решение