Кросинговер (генетичний алгоритм)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Кросинговер - це один із видів оператора рекомбінації генетичного алгоритму. Застосовується на хромосомах з бінарними генами. В літературі зустрічаються ще такі варіанти назви оператора рекомбінації: кроссовер або схрещування.

Одноточковий кросинговер[ред.ред. код]

Одноточковий кросинговер (Single-point crossover) моделюється наступним чином. Нехай є дві батьківські особини з хромосомами X={x_i,i \in [0,L]} і Y={y_i,i \in [0,L]}. Випадковим чином визначається точка всередині хромосоми (точка розриву), в якій обидві хромосоми діляться на дві частини і обмінюються ними. Такий тип кросинговеру називаються одноточковим, так як при ньому батьківські хромосоми розділяються тільки в одній випадкової точці. Принцип роботи одноточкового кросинговеру зображений на наступному рисунку.

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

Також застосовується двоточковий і N-точковий кросинговер.

Двоточковий кросинговер[ред.ред. код]

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

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

Багатоточковий кросинговер[ред.ред. код]

Для багатоточкового кросинговеру (Multi-point crossover), вибираємо m точок розриву k_i \in [1,Nvar], i=(1,...,m), Nvar- кількість змінних (генів) у особині. Точки розриву вибираються випадково без повторень і сортуються в порядку зростання. При кросинговері походить обмін ділянками хромосом, обмеженими точками розрізу і таким чином отримують двох нащадків. Ділянка особини з першим геном до першої точки розрізу в обміні не бере участь. Порівняємо наступні дві особини по 11 двійковим генам.

Multi-point crossover1.jpg

Оберемо такі точки розриву кросинговеру: 2, 6 і 10. Отримаємо таких нащадків:

Multi-point crossover2.jpg

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

Одноточковий і багатоточковий кросинговер визначають точки розрізу, які поділяють особини на частини. Однорідний кросинговер (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

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

Посилання[ред.ред. код]