Кросинговер (генетичний алгоритм)
Кросинговер - це один із видів оператора рекомбінації генетичного алгоритму. Застосовується на хромосомах з бінарними генами. В літературі зустрічаються ще такі варіанти назви оператора рекомбінації: кроссовер або схрещування.
Одноточковий кросинговер
Одноточковий кросинговер (Single-point crossover) моделюється наступним чином. Нехай є дві батьківські особини з хромосомами і . Випадковим чином визначається точка всередині хромосоми (точка розриву), в якій обидві хромосоми діляться на дві частини і обмінюються ними. Такий тип кросинговеру називаються одноточковим, так як при ньому батьківські хромосоми розділяються тільки в одній випадкової точці. Принцип роботи одноточкового кросинговеру зображений на наступному рисунку.
Циклічний кросинговер
У циклічному кросинговері хромосоми розглядаються як цикли, які формуються з'єднанням кінців лінійної хромосоми разом. Для заміни сегменту одного циклу сегментом іншого циклу потрібно вибрати дві точки розрізу. З цієї точки зору, одноточковий кросинговер може бути розглянутий як циклічний кросинговер, перша точка розриву якого зафіксована на початку рядка. Отже, циклічним кросинговером можна вирішувати ті ж задачі, що і одноточковим, але більш детально. Хромосома, що розглядається як цикл, може містити більшу кількість стандартних блоків, так як вони можуть здійснити «циклічне повернення» в кінці рядка. Принцип роботи циклічного кросинговеру зображений на наступному рисунку.
Багатоточковий кросинговер
Для багатоточкового кросинговеру (Multi-point crossover), вибираємо точок розриву , , - кількість змінних (генів) у особині. Точки розриву вибираються випадково без повторень і сортуються в порядку зростання. При кросинговері походить обмін ділянками хромосом, обмеженими точками розрізу і таким чином отримують двох нащадків. Ділянка особини з першим геном до першої точки розрізу в обміні не бере участь. Порівняємо наступні дві особини по 11 двійковим генам.
| Особина 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Особина 2 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Оберемо такі точки розриву кросинговеру: 2, 6 і 10. Отримаємо таких нащадків:
| Нащадок 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| Нащадок 2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
Застосування багатоточкового кросинговеру вимагає введення декількох змінних (точок розриву), і для відтворення вибираються особини з найбільшою пристосованістю.
Одноточковий і багатоточковий кросинговер визначають точки розрізу, які поділяють особини на частини. Однорідний кросинговер (Uniform crossover) створює маску (схему) особини, в кожному локусі якої знаходиться потенційна точка кросинговеру. Маска кросинговеру має ту ж довжину, що і перехресні особини. Створити маску можна наступним чином: введемо деяку величину , і якщо випадкове число більше , то на -у позицію маски ставимо 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 |
Однорідний кросинговер дуже схожий на багатоточковий, але рядок випадкових бітових значень в ньому довший. Це гарантує, що в потомках будуть чергуватися короткі рядки особин-батьків. Алгоритм однорідного кросинговеру для двійкових рядків повністю ідентичний дискретному відтворенню для дійсних хромосом. Такий вид кросинговеру ще називають уніфікованим.
Відношення до дійсності
Джерелом натхнення при розробці цих операторів є оперони, взаємодія яких суттєво впливає на кросинговер