Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Кросинговер - це один із видів оператора рекомбінації генетичного алгоритму. Застосовується на хромосомах з бінарними генами. В літературі зустрічаються ще такі варіанти назви оператора рекомбінації: кроссовер або схрещування.
Одноточковий кросинговер
Одноточковий кросинговер (Single-point crossover) моделюється наступним чином. Нехай є дві батьківські особини з хромосомами 
і 
. Випадковим чином визначається точка всередині хромосоми (точка розриву), в якій обидві хромосоми діляться на дві частини і обмінюються ними. Такий тип кросинговеру називаються одноточковим, так як при ньому батьківські хромосоми розділяються тільки в одній випадкової точці. Принцип роботи одноточкового кросинговеру зображений на наступному рисунку.
Циклічний кросинговер
У циклічному кросинговері хромосоми розглядаються як цикли, які формуються з'єднанням кінців лінійної хромосоми разом. Для заміни сегменту одного циклу сегментом іншого циклу потрібно вибрати дві точки розрізу. З цієї точки зору, одноточковий кросинговер може бути розглянутий як циклічний кросинговер, перша точка розриву якого зафіксована на початку рядка. Отже, циклічним кросинговером можна вирішувати ті ж задачі, що і одноточковим, але більш детально. Хромосома, що розглядається як цикл, може містити більшу кількість стандартних блоків, так як вони можуть здійснити «циклічне повернення» в кінці рядка. Принцип роботи циклічного кросинговеру зображений на наступному рисунку.
Багатоточковий кросинговер
Для багатоточкового кросинговеру (Multi-point crossover), вибираємо 
точок розриву 
, 
, 
- кількість змінних (генів) у особині. Точки розриву вибираються випадково без повторень і сортуються в порядку зростання. При кросинговері походить обмін ділянками хромосом, обмеженими точками розрізу і таким чином отримують двох нащадків. Ділянка особини з першим геном до першої точки розрізу в обміні не бере участь. Порівняємо наступні дві особини по 11 двійковим генам.
| Особина 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Особина 2 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Оберемо такі точки розриву кросинговеру: 2, 6 і 10. Отримаємо таких нащадків:
| Нащадок 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| Нащадок 2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
Застосування багатоточкового кросинговеру вимагає введення декількох змінних (точок розриву), і для відтворення вибираються особини з найбільшою пристосованістю.
Одноточковий і багатоточковий кросинговер визначають точки розрізу, які поділяють особини на частини. Однорідний кросинговер (Uniform crossover) створює маску (схему) особини, в кожному локусі якої знаходиться потенційна точка кросинговеру. Маска кросинговеру має ту ж довжину, що і перехресні особини. Створити маску можна наступним чином: введемо деяку величину 
, і якщо випадкове число більше 
, то на 
-у позицію маски ставимо 0, інакше - 1. Таким чином, гени маски є випадковими двійковими числами (0 або 1). Згідно з цими значеннями, геном нащадка стає перша (якщо ген маски = 0) або друга (якщо ген маски = 1) особина-батько. Наприклад, розглянемо особини:
| Особина 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Особина 2 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Для кожного створеного потомка попередньо створюється маска із 11 випадково обраних елементів із множини {0,1}:
| Маска 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| Маска 2 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Створимо нащадків за наступним правилом: якщо на i-му місці з відповідній масці стоїть 1, то ген першого батька переходить до потомка, інакше унаслідується ген другого батька. Отримаємо наступні особини:
| Нащадок 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Нащадок 2 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Однорідний кросинговер дуже схожий на багатоточковий, але рядок випадкових бітових значень в ньому довший. Це гарантує, що в потомках будуть чергуватися короткі рядки особин-батьків. Алгоритм однорідного кросинговеру для двійкових рядків повністю ідентичний дискретному відтворенню для дійсних хромосом. Такий вид кросинговеру ще називають уніфікованим.
Відношення до дійсності
Джерелом натхнення при розробці цих операторів є оперони, взаємодія яких суттєво впливає на кросинговер
Посилання
- Генетичні алгоритми. Т.В. Панченко [ 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, Інтернет
Krosingover ce odin iz vidiv operatora rekombinaciyi genetichnogo algoritmu Zastosovuyetsya na hromosomah z binarnimi genami V literaturi zustrichayutsya she taki varianti nazvi operatora rekombinaciyi krossover abo shreshuvannya Odnotochkovij krosingoverOdnotochkovij krosingover Single point crossover modelyuyetsya nastupnim chinom Nehaj ye dvi batkivski osobini z hromosomami X xi i 0 L displaystyle X x i i in 0 L i Y yi i 0 L displaystyle Y y i i in 0 L Vipadkovim chinom viznachayetsya tochka vseredini hromosomi tochka rozrivu v yakij obidvi hromosomi dilyatsya na dvi chastini i obminyuyutsya nimi Takij tip krosingoveru nazivayutsya odnotochkovim tak yak pri nomu batkivski hromosomi rozdilyayutsya tilki v odnij vipadkovoyi tochci Princip roboti odnotochkovogo krosingoveru zobrazhenij na nastupnomu risunku Odnotochkovij krosingoverCiklichnij krosingoverU ciklichnomu krosingoveri hromosomi rozglyadayutsya yak cikli yaki formuyutsya z yednannyam kinciv linijnoyi hromosomi razom Dlya zamini segmentu odnogo ciklu segmentom inshogo ciklu potribno vibrati dvi tochki rozrizu Z ciyeyi tochki zoru odnotochkovij krosingover mozhe buti rozglyanutij yak ciklichnij krosingover persha tochka rozrivu yakogo zafiksovana na pochatku ryadka Otzhe ciklichnim krosingoverom mozhna virishuvati ti zh zadachi sho i odnotochkovim ale bilsh detalno Hromosoma sho rozglyadayetsya yak cikl mozhe mistiti bilshu kilkist standartnih blokiv tak yak voni mozhut zdijsniti ciklichne povernennya v kinci ryadka Princip roboti ciklichnogo krosingoveru zobrazhenij na nastupnomu risunku Dvotochkovij krosingoverBagatotochkovij krosingoverDlya bagatotochkovogo krosingoveru Multi point crossover vibirayemo m displaystyle m tochok rozrivu ki 1 Nvar displaystyle k i in 1 Nvar i 1 m displaystyle i 1 m Nvar displaystyle Nvar kilkist zminnih geniv u osobini Tochki rozrivu vibirayutsya vipadkovo bez povtoren i sortuyutsya v poryadku zrostannya Pri krosingoveri pohodit obmin dilyankami hromosom obmezhenimi tochkami rozrizu i takim chinom otrimuyut dvoh nashadkiv Dilyanka osobini z pershim genom do pershoyi tochki rozrizu v obmini ne bere uchast Porivnyayemo nastupni dvi osobini po 11 dvijkovim genam Osobina 1 0 1 1 1 0 0 1 1 0 1 0Osobina 2 1 0 1 0 1 1 0 0 1 0 1 Oberemo taki tochki rozrivu krosingoveru 2 6 i 10 Otrimayemo takih nashadkiv Nashadok 1 0 1 1 0 1 1 1 1 0 1 1Nashadok 2 1 0 1 1 0 0 0 0 1 0 0 Zastosuvannya bagatotochkovogo krosingoveru vimagaye vvedennya dekilkoh zminnih tochok rozrivu i dlya vidtvorennya vibirayutsya osobini z najbilshoyu pristosovanistyu Odnotochkovij i bagatotochkovij krosingover viznachayut tochki rozrizu yaki podilyayut osobini na chastini Odnoridnij krosingover Uniform crossover stvoryuye masku shemu osobini v kozhnomu lokusi yakoyi znahoditsya potencijna tochka krosingoveru Maska krosingoveru maye tu zh dovzhinu sho i perehresni osobini Stvoriti masku mozhna nastupnim chinom vvedemo deyaku velichinu 0 lt p0 lt 1 displaystyle 0 lt p 0 lt 1 i yaksho vipadkove chislo bilshe p0 displaystyle p 0 to na n displaystyle n u poziciyu maski stavimo 0 inakshe 1 Takim chinom geni maski ye vipadkovimi dvijkovimi chislami 0 abo 1 Zgidno z cimi znachennyami genom nashadka staye persha yaksho gen maski 0 abo druga yaksho gen maski 1 osobina batko Napriklad rozglyanemo osobini Osobina 1 0 1 1 1 0 0 1 1 0 1 0Osobina 2 1 0 1 0 1 1 0 0 1 0 1 Dlya kozhnogo stvorenogo potomka poperedno stvoryuyetsya maska iz 11 vipadkovo obranih elementiv iz mnozhini 0 1 Maska 1 0 1 1 0 0 0 1 1 0 1 0Maska 2 1 0 0 1 1 1 0 0 1 0 1 Stvorimo nashadkiv za nastupnim pravilom yaksho na i mu misci z vidpovidnij masci stoyit 1 to gen pershogo batka perehodit do potomka inakshe unasliduyetsya gen drugogo batka Otrimayemo nastupni osobini Nashadok 1 1 1 1 0 1 1 1 1 1 1 1Nashadok 2 0 0 1 1 0 0 0 0 0 0 0 Odnoridnij krosingover duzhe shozhij na bagatotochkovij ale ryadok vipadkovih bitovih znachen v nomu dovshij Ce garantuye sho v potomkah budut cherguvatisya korotki ryadki osobin batkiv Algoritm odnoridnogo krosingoveru dlya dvijkovih ryadkiv povnistyu identichnij diskretnomu vidtvorennyu dlya dijsnih hromosom Takij vid krosingoveru she nazivayut unifikovanim Vidnoshennya do dijsnostiDzherelom nathnennya pri rozrobci cih operatoriv ye operoni vzayemodiya yakih suttyevo vplivaye na krosingoverPosilannyaGenetichni algoritmi T V Panchenko 29 listopada 2013 u Wayback Machine