Дискретна рекомбінація
Дискретна рекомбінація (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 |
Якщо розглядати особини популяції як точки в -мірному просторі, де – кількість генів в одній особині, то можна сказати, що при лінійній рекомбінації точки, які відповідають згенерованим нащадкам, лежать на прямій, заданій двома точками – батьками.
Посилання[ред. | ред. код]
- Генетичні алгоритми. Т.В. Панченко [Архівовано 29 листопада 2013 у Wayback Machine.]