Рекомбинация (воспроизведение)

Оператор рекомбинации применяют сразу же после оператора отбора родителей для получения новых особей-потомков. Смысл рекомбинации заключается в том, что созданные потомки должны наследовать генную информацию от обоих родителей. Различают дискретную рекомбинацию и кроссинговер.

Дискретная рекомбинация (Discrete recombination) в основном применяется к хромосомам с вещественными генами. Основными способами дискретной рекомбинации являются собственно дискретная рекомбинация, промежуточная и линейная рекомбинации.

Дискретная рекомбинация соответствует обмену генами между особями. Для иллюстрации данного оператора сравним две особи с тремя генами:

Для создания двух потомков с равной вероятностью случайно выберем номер особи для каждого гена:

Согласно схеме создадим потомков:

Дискретная рекомбинация применима для любого типа генов (двоичные, вещественные и символьные).

Промежуточная рекомбинация (Intermediate recombination) применима только к вещественным переменным, но не к бинарным. В данном методе предварительно определяется числовой интервал значений генов потомков, который должен содержать значения генов родителей. Потомки создаются по следующему правилу:

Потомок = Родитель 1 + (Родитель 2 - Родитель 1),

где множитель - случайное число на отрезке [-d, 1 + d], d 0. Как отмечают сторонники этого метода, наиболее оптимальное воспроизведение получается при d = 0,25. Для каждого гена создаваемого потомка выбирается отдельный множитель .

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

Линейная рекомбинация (Line recombination) отличается от промежуточной тем, что множитель выбирается для каждого потомка один раз. Если рассматривать особи популяции как точки в k-мерном пространстве, где k - количество генов в одной особи, то можно сказать, что при линейной рекомбинации генерируемые точки потомков лежат на прямой, заданной двумя точками - родителями.

Кроссинговер (бинарная рекомбинация)

Рекомбинацию бинарных строк принято называть кроссинговером (кроссовером) или скрещиванием.

Одноточечный кроссинговер (Single-point crossover) моделируется следующим образом. Пусть имеются две родительские особи с хромосомами XXXXXX и YYYYYY. Случайным образом определяется точка внутри хромосомы (точка разрыва), в которой обе хромосомы делятся на две части и обмениваются ими:

Такой тип кроссинговера называется одноточечным, так как при нем родительские хромосомы разделяются только в одной случайной точке.