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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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