Page 23 - 4521

1.4.2 Кросинговер (бінарна рекомбінація)
Рекомбінацію бінарних рядків прийнято називати кро-
синговером (кросовером) або схрещуванням.
Одноточковий кросинговер (Single-point crossover)
моделюється таким чином. Нехай є дві батьківські особини з
хромосомами X = {x і i є [0;L]} і Y = {y і ,iє [0;L]}. Випадковим
чином визначається точка усередині хромосоми (точка розри-
ву), в якій обидві хромосоми діляться на дві частини і обміню-
ються ними. Такий тип кросинговера називається одноточко-
вим, оскільки при ньому батьківські хромосоми розділяються
тільки в одній випадковій точці.

Рисунок 1.6 – Одноточковий кросинговер
Також застосовується двох- і N-точковий кросинго-
вер.
У двоточковому кросинговері (і багатоточковому кро-
синговері взагалі) хромосоми розглядаються як цикли, які фо-
рмуються з'єднанням кінців лінійної хромосоми разом. Для
заміни сегменту одного циклу сегментом іншого циклу потрі-
бний вибір двох точок розрізу. У цьому предствленні, одното-
чковий кросинговер може бути розглянутий як кросинговер з
двома точками, але з однією точкою розрізу, зафіксованою на
початку рядка. Отже, двоточковий кросинговер вирішує ту ж
саму задачу, що і одноточковий, але більш повно. Хромосома,
що розглядається як цикл, може містити більшу кількість ста-
ндартних блоків, оскільки вони можуть зробити «циклічне
повернення» в кінці рядка (рис. 7). Зараз багато дослідників
погоджуються, що двоточковий кросинговер кращий, ніж од-
ноточковий.

22