V. Operátory GA

---

Přehled

Jak je vidět ze schématu genetického algoritmu, křížení a mutace patří mezi nejdůležitější části genetického algoritmu. Jeho výkonnost je ovlivněna především těmito dvěma operátory. Než si křížení a mutaci popíšeme podrobněji, je užitečné říct si několik věcí o chromozomech.

---

Kódování chromozomu

Chromozom musí nějakým způsobem obsahovat informaci o řešení, které reprezentuje. Nejpoužívanějším kódováním je binární řetězec. Chromozom pak může vypadat takto:

Každý chromozom má jeden binární řetězec. Každý bit v tomto řetězci může reprezentovat nějakou vlastnost řešení. Nebo může celý řetězec reprezentovat jedno číslo - to bylo použito v základním ukázce GA.

Samozřejmě existuje mnoho dalších způsobů kódování. Záleží hlavně na řešeném problému. Lze takto kódovat například celá nebo reálná čísla, někdy je užitečné kódovat i nějaké permutace a podobně.

---

Křížení

Jakmile se rozhodneme, jaké kódování použít, můžeme přejít ke křížení. Křížení vybírá geny z rodičovských chromozomů a vytváří nové potomky. Nejjednodušší způsob je zvolit náhodný bod křížení, zkopírovat vše před tímto bodem z prvního rodiče a potom zkopírovat vše za tímto bodem z druhého rodiče.

Křížení pak může vypadat takto (| je bod křížení):

Existují i jiné způsoby, jak křížení provést. Můžeme například zvolit více než jeden bod křížení. Křížení může být poměrně složité a silně závisí na kódování chromozomu. Metoda křížení navržená pro konkrétní problém může zlepšit výkonnost genetického algoritmu.

---

Mutace

Po provedení křížení následuje mutace. Jejím účelem je zabránit tomu, aby celá populace ustrnula v lokálním optimu řešeného problému. Mutace náhodně mění nové potomky. U binárního kódování můžeme přepnout několik náhodně vybraných bitů z 1 na 0 nebo z 0 na 1. Mutace pak může vypadat takto:

Stejně jako křížení závisí i mutace na kódování. Například při kódování permutací může mutace znamenat prohození dvou genů.