Дискретна рекомбінація

Дискретна рекомбінація (Discrete recombination) - це один із видів оператора рекомбінації генетичного алгоритму. В основному застосовується на хромосомах з дійсними (не двійковими) генами. Основними способами дискретної рекомбінації є власне дискретна рекомбінація, проміжна, лінійна і розширено лінійна рекомбінації. Дискретна рекомбінація відповідає обміну генами між особинами.

Приклад дискретної рекомбінації

Для ілюстрації дискретної рекомбінації порівняємо дві особини з трьома генами:

Особина 1	12	25	7
Особина 2	116	4	34

Для створення двох потомків з рівною ймовірністю випадково оберемо номер особини для кожного гена.

Схема 1	2	2	1
Схема 2	1	2	1

Відповідно до схеми створимо потомків:

Нащадок 1	116	4	7
Нащадок 2	12	4	7

Дискретна рекомбінація може застосовуватись для будь-якого типу генів (двійкові, дійсні і символьні).

Проміжна рекомбінація

Проміжна рекомбінація (Intermediate recombination) може застосовуватись тільки для дійсних змінних, але не до бінарних. У даному методі заздалегідь визначається числовий інтервал значень генів нащадків, який повинен містити значення генів батьків. Нащадки створюються за наступним правилом:

Нащадок = Батько 1 + $\alpha$ (Батько 2 - Батько 1),

де множник $\alpha$ - випадкове число на відрізку $[-d,1+d],d\geq 0$. Як зазначають прихильники цього методу, найкращі дані виходять при $d=0,25$. Для кожного гена створюваного нащадка вибирається окремий множник $\alpha$. Розглянемо застосування оператора на прикладі. Нехай два батьки мають такі значення генів:

Особина 1	12	25	7
Особина 2	116	4	34

Випадковим чином оберемо значення $\alpha \in [-0,25;1,25]$ для кожного гена обох нащадків:

Схема 1	0,5	1,1	-0,1
Схема 2	0,1	0,8	0,5

Обчислимо значення генів нащадків по запропонованій вище формулі:

Нащадок 1	12+0,5(116-12)=64	25+1,1(4-25)=1,9	7-0,1(34-7)=4,3
Нащадок 2	12+0,1(116-12)=22,4	25+0,8(4-25)=8,2	7+0,8(34-7)=20,5

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

Лінійна рекомбінація

Лінійна рекомбінація (Line recombination) відрізняється від проміжної тим, що множник $\alpha$ вибирається для кожного нащадка один раз. Розглянемо гени наведених вище батьків. Нехай значення $\alpha$ визначається таким чином:

Схема 1	0,5
Схема 2	0,1

Тоді гени створених нащадків матимуть наступні значення:

Нащадок 1	12+0,5(116-12)=64	25+0,5(4-25)=14,5	7-0,5(34-7)=20,5
Нащадок 2	12+0,1(116-12)=22,4	25+0,1(4-25)=22,9	7+0,1(34-7)=9,7

Якщо розглядати особини популяції як точки в $k$-мірному просторі, де $k$ – кількість генів в одній особині, то можна сказати, що при лінійній рекомбінації точки, які відповідають згенерованим нащадкам, лежать на прямій, заданій двома точками – батьками.

Посилання

• Генетичні алгоритми. Т.В. Панченко [Архівовано 29 листопада 2013 у Wayback Machine.]