Кроссинговер — это один из видов оператора рекомбинации генетического алгоритма. Применяется на хромосомах с бинарными генами. В литературе встречаются еще такие варианты названия оператора рекомбинации: кроссовер или скрещивание.

Одноточечный кроссинговер

Одноточечный кроссинговер (Single-point crossover) моделируется следующим образом. Пусть есть две родительские особи с хромосомами X = x i, i E [0, l] и Y = y i i E [0, L]. Случайным образом определяется точка внутри хромосомы (точка разрыва), в которой обе хромосомы делятся на две части и обмениваются ими. Такой тип кроссинговера называются Одноточечный, так как при нем отцовские хромосомы разделяются только в одной случайной точке. Принцип работы одноточечного кроссинговера изображен на следующем рисунке.

Также применяется двухточечный и N-точечный кроссинговер.

Двухточечный кроссинговер

В двухточечном кроссинговере (и в многоточечном кроссинговере тоже) хромосомы рассматриваются как циклы, которые формируются соединением концов линейной хромосомы вместе. Для замены сегмента одного цикла сегментом другого цикла нужно выбрать две точки разреза. С этой точки зрения, одноточечный кроссинговер может быть рассмотрен как кроссинговер с двумя точками, но с одной точкой разрыва, зафиксированной в начале строки. Итак, двухточечный кроссинговером можно решать те же задачи, что и одноточечный, но более детально. Хромосома, рассматривается как цикл, может содержать большее количество стандартных блоков, так как они могут осуществить «циклическое возвращение» в конце строки. На данный момент многие исследователи соглашаются, что двухточечный кроссинговер лучше, чем одноточечный. Принцип работы двухточечной кроссинговера изображен на следующем рисунке.

Многоточечный кроссинговер

Для многоточечной кроссинговера (Multi-point crossover), выбираем точек m разрыва k i [1, N var], i = (1, …, m), Nvar — количество переменных (генов) в особи. Точки разрыва выбираются случайно без повторений и сортируются в порядке возрастания. При кроссинговере происходит обмен участками хромосом, ограниченными точками разреза и таким образом получают двух потомков. Участок особи с первым геном первой точке разреза в обмене не участвует. Сравним следующие две особи по 11 двоичным генам.

Выберем такие точки разрыва кроссинговера: 2, 6 и 10. Получим таких потомков:

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

Одноточечный и многоточечный кроссинговер определяют точки разреза, которые разделяют особи на части. Однородной кроссинговер (Uniform crossover) создает маску (схему) особи, в каждом локусе которой находится потенциальная точка кроссинговера. Маска кроссинговера имеет ту же длину, что и перекрестные особи. Создать маску можно следующим образом: введем некоторую величину 0 <p 0 <1, и если случайное число больше p 0, то на n-в позицию маски ставим 0, иначе — 1. Таким образом, гены маски являются случайными двоичными числами (0 или 1). Согласно этим значениям, геном потомка становится первая (если ген маски = 0) или друга (если ген маски = 1) особь-отец. Например, рассмотрим особи:

Особь 1 0 1 1 1 0 0 1 1 0 1 0
Особь 2 1 0 1 0 1 1 0 0 1 0 1

Для каждого созданного потомка предварительно создается маска из 11 случайно выбранных элементов из множества {0,1}

Маска 1 0 1 1 0 0 0 1 1 0 1 0
Маска 2 1 0 0 1 1 1 0 0 1 0 1

Создадим потомков по следующему правилу: если на i-м месте с соответствующей маске стоит 1, то ген первого отца переходит к потомка, иначе унаслидуеться ген второго родителя. Получим следующие особи:

Потомок 1 1 1 1 0 1 1 1 1 1 1 1
Потомок 2 0 0 1 1 0 0 0 0 0 0 0

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