XI. Křížení a mutace

Úvod

Křížení a mutace jsou dva základní operátory GA. Výkonnost GA na nich silně závisí. Typ i implementace těchto operátorů závisí na kódování a na samotném problému.

Existuje mnoho způsobů, jak provádět křížení a mutaci. Tato kapitola přináší jen několik příkladů a doporučení pro jejich použití u několika druhů kódování.

Binární kódování

Křížení

Jednobodové křížení - vybere se jeden bod křížení. Binární řetězec od začátku chromozomu po bod křížení se zkopíruje z jednoho rodiče a zbytek se zkopíruje z druhého rodiče.

11001011+11011111 = 11001111

Dvoubodové křížení - vyberou se dva body křížení. Binární řetězec od začátku chromozomu po první bod křížení se zkopíruje z jednoho rodiče, část od prvního do druhého bodu křížení se zkopíruje z druhého rodiče a zbytek zase z prvního rodiče.

11001011 + 11011111 = 11011111

Uniformní křížení - bity se náhodně kopírují z prvního nebo druhého rodiče.

11001011 + 11011101 = 11011111

Aritmetické křížení - k vytvoření nového potomka se provede nějaká aritmetická operace.

11001011 + 11011111 = 11001001 (AND)

Mutace

Invertování bitů - vybrané bity se obrátí.

11001001 =>  10001001

Permutační kódování

Křížení

Jednobodové křížení - vybere se jeden bod křížení. Do tohoto bodu se permutace zkopíruje z prvního rodiče. Potom se projde druhý rodič a přidávají se všechna čísla, která ještě v potomkovi nejsou.
Poznámka: existuje více způsobů, jak vytvořit zbytek za bodem křížení.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutace

Změna pořadí - vyberou se dvě čísla a prohodí se.

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Hodnotové kódování

Křížení

Lze použít všechny metody křížení z binárního kódování.

Mutace

Přičtení malého čísla (pro kódování reálných hodnot) - k vybraným hodnotám se přičte nebo odečte malé číslo.

(1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)

Stromové kódování

Křížení

Stromové křížení - v každém rodiči se vybere jeden bod křížení. Rodiče se v tomto bodě rozdělí a vymění si části pod bodem křížení, čímž vzniknou noví potomci.

Mutace

Změna operátoru, čísla - vybrané uzly se změní.