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

 
Находят применение операторы кроссинговера для вещественного 
кодирования 
Предположим, что 
С1
={
c1
1
,..,
c1
n
} и 
С2
={
c2
1
,..,
c2
n
} - две хромосомы к 
которым применяется оператор кроссинговера. Будем обозначать 
потомков как 
H1
и 
H2
. Ниже кратко описаны некоторые операторы 
скрещивания для генетических алгоритмов с вещественным 
кодированием.

Двухточечный 
кроссинговер 
(Two-point 
crossover).
Случайным образом выбираются две точки разрыва 
i
и 
j
из 
диапазона [1, 
n
-1]. Пусть при этом 
i
. Тогда потомки 
определяются 
путем 
обмена 
соответствующих 
частей 
родительских 
хромосом: 
H1 
= 
{c1
1
, 
c1
2
,.., 
c2
i
, 
c2
i+1
,.., 
c2
j
, 
c1
j+1
,.., 
c1
n
}, 
H2 = {c2
1
, c2
2
,.., c1
i
, c1
i+1
,.., c1
j
, c2
j+1
,.., c2
n
}.

Однородный 
кроссинговер 
(Uniform 
crossover).
Работает как однородный кроссинговер для бинарного 

---

А.Е. Кононюк Дискретно-непрерывная математика 
76 
кодирования с той лишь разницей, что участок хромосомы, для 
которого разыгрывается вероятность попасть к первому или ко 
второму потомку не отдельный разряд, а значение параметра 
целиком. Т.е. разыгрывается не бит, а весь ген. Иными словами, 
для каждого гена, если случайная бюинарная переменная 
Rnd
=0, то ген от 1-го родителя попадает к первому потомку, а 
ген второго родителя - ко второму. Если же 
Rnd
=1, то наоборот.
Используются также кроссинговеры: 

Арифметический кроссинговер (Arithmetical crossover).

Геометрический кроссинговер (Geometrical crossover,).

BLX-a кроссинговер (BLX-a crossover). 

Имитированный бинарный кроссинговер (Simulated binary 
crossover).

Нечеткая рекомбинация (Fuzzy recombination).
Стратегии формирования нового поколения
После скрещивания особей необходимо решить проблему о том какие 
из новых особей войдут в следующее поколение, а какие - нет, и что 
делать с их предками. Есть два способа:
1.
Новые особи (потомки) занимают места своих родителей. 
После чего наступает следующий этап, в котором потомки 
оцениваются, отбираются, дают потомство и уступают место 
своим "детям".
2.
Создается промежуточная популяция, которая включает в себя 
как родителей, так и их потомков. Члены этой популяции 
оцениваются, а затем из них выбираются N самых лучших, 
которые и войдут в следующее поколение.
Те кто знаком с эволюционными стратегиями, то с этими способами вы 
уже встречались. Какой из этих двух вариантов лучше – ответить 
однозначно затруднительно. Видимо второй вариант практичнее (т.к. не 
позволяет заменять приспособленных родителей на "неизвестно кого"), 
но тут может быть больше проблем с преждевременной сходимостью, 
чем в первом варианте. К тому же он требует сортировки массива 

---

А.Е. Кононюк Дискретно-непрерывная математика 
77 
размером (как минимум) 2*N.
Вообще говоря, можно комбинировать стратегии отбора и 
формирования следующего поколения как угодно - ограничений нет 
никаких.