Дискретна рекомбінація (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.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Diskretna rekombinaciya Discrete recombination ce odin iz vidiv operatora rekombinaciyi genetichnogo algoritmu V osnovnomu zastosovuyetsya na hromosomah z dijsnimi ne dvijkovimi genami Osnovnimi sposobami diskretnoyi rekombinaciyi ye vlasne diskretna rekombinaciya promizhna linijna i rozshireno linijna rekombinaciyi Diskretna rekombinaciya vidpovidaye obminu genami mizh osobinami Priklad diskretnoyi rekombinaciyiDlya ilyustraciyi diskretnoyi rekombinaciyi porivnyayemo dvi osobini z troma genami Osobina 1 12 25 7 Osobina 2 116 4 34 Dlya stvorennya dvoh potomkiv z rivnoyu jmovirnistyu vipadkovo oberemo nomer osobini dlya kozhnogo gena Shema 1 2 2 1 Shema 2 1 2 1 Vidpovidno do shemi stvorimo potomkiv Nashadok 1 116 4 7 Nashadok 2 12 4 7 Diskretna rekombinaciya mozhe zastosovuvatis dlya bud yakogo tipu geniv dvijkovi dijsni i simvolni Promizhna rekombinaciyaPromizhna rekombinaciya Intermediate recombination mozhe zastosovuvatis tilki dlya dijsnih zminnih ale ne do binarnih U danomu metodi zazdalegid viznachayetsya chislovij interval znachen geniv nashadkiv yakij povinen mistiti znachennya geniv batkiv Nashadki stvoryuyutsya za nastupnim pravilom Nashadok Batko 1 a displaystyle alpha Batko 2 Batko 1 de mnozhnik a displaystyle alpha vipadkove chislo na vidrizku d 1 d d 0 displaystyle d 1 d d geq 0 Yak zaznachayut prihilniki cogo metodu najkrashi dani vihodyat pri d 0 25 displaystyle d 0 25 Dlya kozhnogo gena stvoryuvanogo nashadka vibirayetsya okremij mnozhnik a displaystyle alpha Rozglyanemo zastosuvannya operatora na prikladi Nehaj dva batki mayut taki znachennya geniv Osobina 1 12 25 7 Osobina 2 116 4 34 Vipadkovim chinom oberemo znachennya a 0 25 1 25 displaystyle alpha in 0 25 1 25 dlya kozhnogo gena oboh nashadkiv Shema 1 0 5 1 1 0 1 Shema 2 0 1 0 8 0 5 Obchislimo znachennya geniv nashadkiv po zaproponovanij vishe formuli Nashadok 1 12 0 5 116 12 64 25 1 1 4 25 1 9 7 0 1 34 7 4 3 Nashadok 2 12 0 1 116 12 22 4 25 0 8 4 25 8 2 7 0 8 34 7 20 5 Pri promizhnij rekombinaciyi vinikayut znachennya geniv vidminni vid znachennya geniv osobin batkiv Ce prizvodit do viniknennya novih osobin pristosovanist yakih mozhe buti krashoyu nizh pristosovanist batkiv U literaturi takij operator rekombinaciyi inodi nazivayetsya diferencialnim shreshuvannyam Linijna rekombinaciyaLinijna rekombinaciya Line recombination vidriznyayetsya vid promizhnoyi tim sho mnozhnik a displaystyle alpha vibirayetsya dlya kozhnogo nashadka odin raz Rozglyanemo geni navedenih vishe batkiv Nehaj znachennya a displaystyle alpha viznachayetsya takim chinom Shema 1 0 5 Shema 2 0 1 Todi geni stvorenih nashadkiv matimut nastupni znachennya Nashadok 1 12 0 5 116 12 64 25 0 5 4 25 14 5 7 0 5 34 7 20 5 Nashadok 2 12 0 1 116 12 22 4 25 0 1 4 25 22 9 7 0 1 34 7 9 7 Yaksho rozglyadati osobini populyaciyi yak tochki v k displaystyle k mirnomu prostori de k displaystyle k kilkist geniv v odnij osobini to mozhna skazati sho pri linijnij rekombinaciyi tochki yaki vidpovidayut zgenerovanim nashadkam lezhat na pryamij zadanij dvoma tochkami batkami PosilannyaGenetichni algoritmi T V Panchenko 29 listopada 2013 u Wayback Machine