Дискретна рекомбінація
Дискретна рекомбінація (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 + (Батько 2 - Батько 1),
де множник - випадкове число на відрізку . Як зазначають прихильники цього методу, найкращі дані виходять при . Для кожного гена створюваного нащадка вибирається окремий множник . Розглянемо застосування оператора на прикладі. Нехай два батьки мають такі значення генів:
| Особина 1 | 12 | 25 | 7 |
| Особина 2 | 116 | 4 | 34 |
Випадковим чином оберемо значення для кожного гена обох нащадків:
| Схема 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) відрізняється від проміжної тим, що множник вибирається для кожного нащадка один раз. Розглянемо гени наведених вище батьків. Нехай значення визначається таким чином:
| Схема 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 |
Якщо розглядати особини популяції як точки в -мірному просторі, де – кількість генів в одній особині, то можна сказати, що при лінійній рекомбінації точки, які відповідають згенерованим нащадкам, лежать на прямій, заданій двома точками – батьками.
