Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Стратегии формирования нового поколения 
Выделяют два типа формирования нового поколения после получения 
множества детей в результате кроссовера и мутации:
1.
дети замещают родителей; 
2.
новое поколение составляется из совокупности и детей, и их 
родителей, например, выбором 
N
лучших.
Также для формирования нового поколения возможно использование 
принципа 
элитизма
: в новое поколение обязательно включается 
заданное количество лучших особей предыдущего поколения (часто 
одна лучшая особь). Использование второй стратегии и элитизма 
оказывается весьма полезным для эффективности ГА, т. к. не допускает 
потерю лучших решений. К примеру, если популяция сошлась в 
локальном максимуме, а мутация вывела одну из строк в область 
глобального, то при первой стратегии весьма вероятно, что эта особь в 
результате скрещивания будет потеряна, и решение задачи не будет 
получено. Если же используется элитизм, то полученное хорошее 
решение будет оставаться в популяции до тех пор, пока не будет 
найдено еще лучшее.
3.4. 
Некоторые модели генетических алгоритмов 

---

А.Е. Кононюк Дискретно-непрерывная математика 
116 
Классический ГА был рассмотрен выше. Напомним, что его создал 
Holland (1975).
Genitor 
Этот алгоритм был создан Уитли (D. Whitley). 
Genitor
-подобные 
алгоритмы отличаются от классического ГА следующими тремя 
свойствами:

На каждом шаге только 
одна
пара случайных родителей создает 
только 
одного
ребенка.

Этот ребенок заменяет не родителя, а одну из худших особей 
популяции (в первоначальном 
Genitor
— самую худшую).

Отбор особи для замены производится по ее ранку (рейтингу), а 
не по приспособленности.
Утверждается (Syswerda, 1991), что в 
Genitor
поиск гиперплоскостей 
происходит лучше, а сходимость быстрее, чем у классического ГА.
CHC 
CHC
расшифровывается как 
Cross generational elitist selection, 
Heterogenous recombination, Cataclysmic mutation
. Этот алгоритм был 
создан Eshelman (1991) и характеризуется следующими параметрами:

Для нового поколения выбираются 
N
лучших 
различных
особей 
среди родителей и детей. Дублирование строк не допускается.

Для скрещивания выбирается случайная пара, но не 
допускается, чтобы между родителями было мало Хэммингово 
расстояние или мало расстояние между крайними 
различающимися битами.

Для скрещивания используется разновидность однородного 
кроссовера 
HUX
(
Half Uniform Crossover
): ребенку переходит 
ровно половина битов каждого родителя.

Размер популяции небольшой, около 50 особей. Этим 
оправдано использование однородного кроссовера.

---

А.Е. Кононюк Дискретно-непрерывная математика 
117 

CHC противопоставляет агрессивный отбор агрессивному 
кроссоверу, однако все равно малый размер популяции быстро 
приводит ее к состоянию, когда создаются только более или 
менее одинаковые строки. В таком случае CHC применяет 
cataclysmic mutation
: все строки, кроме самой приспособленной, 
подвергаются сильной мутации (изменяется около трети битов). 
Таким образом, алгоритм перезапускается и далее продолжает 
работу, применяя только кроссовер.