Генетические алгоритмы

Модели ГА

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

Написать письмо

Ниже приведено небольшое описание некоторых моделей генетического алгоритма. При реализации вашего собственного алгоритма придерживаться этих моделей не обязательно, т.к. очень многое зависит от решаемой задачи, однако, описываемые принципы (например, параллелизм) могут оказаться полезными.

1. Canonical GA (J. Holland)

Данная модель алгоритма является классической. Она была предложена Джоном Холландом в его знаменитой работе "Адаптация в природных и исусственных средах" (1975). Часто можно встретить описание простого ГА (Simple GA, D. Goldberg), он отличается от канонического тем, что использует либо рулеточный, либо турнирный отбор. Модель канонического ГА имеет следующие характеристики:

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Пропорциональный отбор.
• Особи для скрещивания выбираются случайным образом.

• Одноточечный кроссовер и одноточечная мутация.

• Следующее поколение формируется из потомков текущего поколения без "элитизма". Потомки занимают места своих родителей.

2. Genitor (D. Whitley)

В данной модели используется специфичная стратегия отбора. Вначале, как и полагается, популяция инициализируется и её особи оцениваются. Затем выбираются случайным образом две особи, скрещиваются, причем получается только один потомок, который оценивается и занимает место наименее приспособленной особи. После этого снова случайным образом выбираются 2 особи, и их потомок занимает место особи с самой низкой приспособленностью. Таким образом на каждом шаге в популяции обновляется только одна особь. Подводя итоги можно выделить следующие характерные особенности:

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Особи для скрещивания выбираются случайным образом.

• Ограничений на тип кроссовера и мутации нет.

• В результате скрещивания особей получается один потомок, который занимает место наименее приспособленной особи.

3. Hybrid algorithm (L. "Dave" Davis)

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

• Фиксированный размер популяции.
• Фиксированная разрядность генов.

• Любые комбинации стратегий отбора и формирования следующего поколения

• Ограничений на тип кроссовера и мутации нет.

• ГА применяется на начальном этапе, а затем в работу включается классический метод оптимизации.

4. Island Model GA

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

• Наличие нескольких популяций, как правило одинакового фиксированного размера.

• Фиксированная разрядность генов.

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

• Ограничений на тип кроссовера и мутации нет.

• Случайный обмен особями между "островами". Если миграция будет слишком активной, то особенности островной модели будут сглажены и она будет не очень сильно отличаться от моделей ГА без параллелизма.

5. CHC (Eshelman)

CHC расшифровывается как Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В силу этого после нахождения некоторого решения алгоритм перезапускается, причемлучшая особь копируется в новую популяцию, а оставшиеся особи являются сильной мутацией (мутирует примерно треть битов в хромосоме) существующих и поиск повторяется. Ещу одной специфичной чертой является стратегия скрещивания: все особи разбиваются на пары, причем скрещиваются только те пары, в которых хромосомы особей существенно различны (хэммингово расстояние больше некоторого порогового плюс возможны ограничения на минимальное расстояние между крайними различающимися битами). При скрещивании используется так называемый HUX-оператор (Half Uniform Crossover) - это разновидность однородного кроссовера, но в нем к каждому потомку попадает ровно половина битов хромосомы от каждого родителя. Таким образом, модель обладает следующими свойствами:

• Фиксированный размер популяции.
• Фиксированная разрядность генов.
• Перезапуск алгоритма после нахождения решения.
• Небольшая популяция.

• Особи для скрещивания разбиваются на пары и скрещиваются при условии существенных отличий.

• Отбор в следующее поколение проводится между родительскими особями и потомками.

• Используется половинный однородный кроссовер (HUX).
• Макромутация при перезапуске.

Источники:

1. Soraya Rana "Examining the Role of Local Optima and Schema Processing in Genetic Search", 1999.

2. Darrel Whitley "A Genetic Algorithm Tutorial", 1993.