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

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

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

Одноточковий кросинговер (Single-point crossover) моделюється наступним чином. Нехай є дві батьківські особини з хромосомами і . Випадковим чином визначається точка всередині хромосоми (точка розриву), в якій обидві хромосоми діляться на дві частини і обмінюються ними. Такий тип кросинговеру називаються одноточковим, так як при ньому батьківські хромосоми розділяються тільки в одній випадкової точці. Принцип роботи одноточкового кросинговеру зображений на наступному рисунку.

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

Циклічний кросинговер

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

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

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

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

Особина 101110011010
Особина 210101100101

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

Нащадок 101 1 0 1 11101 1
Нащадок 210 1 1 0 00010 0

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

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

Особина 101110011010
Особина 210101100101

Для кожного створеного потомка попередньо створюється маска із 11 випадково обраних елементів із множини {0,1}:

Маска 101100011010
Маска 210011100101

Створимо нащадків за наступним правилом: якщо на i-му місці з відповідній масці стоїть 1, то ген першого батька переходить до потомка, інакше унаслідується ген другого батька. Отримаємо наступні особини:

Нащадок 111101111111
Нащадок 200110000000

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

Відношення до дійсності

Джерелом натхнення при розробці цих операторів є оперони, взаємодія яких суттєво впливає на кросинговер

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.