X. Kódování


Úvod

Volba kódování chromozomů je jedna z prvních otázek, které je třeba řešit, když používáte GA na nějaký problém. Správné kódování silně závisí na problému.

Tato kapitola představuje několik způsobů kódování, které byly úspěšně použity v genetických algoritmech.

Binární kódování

Binární kódování je nejběžnější přístup, hlavně proto, že první práce o genetických algoritmech používaly právě tento typ kódování.

Při binárním kódování je každý chromozom řetězcem bitů, 0 nebo 1.

Chromozom A 101100101100101011100101
Chromozom B 111111100000110000011111

Příklad chromozomů s binárním kódováním

Binární kódování umožňuje i s malým počtem alel velké množství možných chromozomů. Na druhou stranu toto kódování často není pro mnoho problémů přirozené a někdy je nutné po křížení a/nebo mutaci dělat opravy.

image
Příklad problému: Problém batohu
Problém: Máme předměty s danou hodnotou a velikostí. Batoh má pevně danou kapacitu. Vyberte předměty tak, aby celková hodnota v batohu byla co nejvyšší, ale nebyla překročena jeho kapacita.
Kódování: Každý bit určuje, zda je odpovídající předmět v batohu.
image

Permutační kódování

Permutační kódování lze použít u problémů uspořádávání, například u problému obchodního cestujícího nebo při pořadí úkolů.

Při permutačním kódování je každý chromozom řetězcem čísel, který reprezentuje číslo v posloupnosti.

Chromozom A 1  5  3  2  6  4  7  9  8
Chromozom B 8  5  6  7  2  3  1  4  9

Příklad chromozomů s permutačním kódováním

Permutační kódování je užitečné pouze pro problémy uspořádávání. I v těchto problémech vyžadují některé typy křížení a mutace opravy, aby chromozom zůstal konzistentní (tedy aby pořád tvořil platnou posloupnost).

image
Příklad problému: Problém obchodního cestujícího (TSP)
Problém: Máme města a dané vzdálenosti mezi nimi. Obchodní cestující musí navštívit všechna města a přitom urazit co nejmenší vzdálenost. Hledáme takovou posloupnost měst, která minimalizuje celkovou uraženou vzdálenost.
Kódování: Chromozom určuje pořadí, v jakém obchodní cestující města navštíví.
image

Hodnotové kódování

Přímé hodnotové kódování lze použít u problémů, kde je potřeba pracovat se složitějšími hodnotami, např. reálnými čísly. Použít u těchto problémů binární kódování by často bylo velmi obtížné.

Při hodnotovém kódování je každý chromozom řetězcem nějakých hodnot. Hodnotami může být cokoli, co souvisí s problémem - od čísel, reálných čísel nebo znaků až po složitější objekty.

Chromozom A 1.2324  5.3243  0.4556  2.3293  2.4545
Chromozom B ABDJEIFJDHDIERJFDLDFLFEGT
Chromozom C (back), (back), (right), (forward), (left)

Příklad chromozomů s hodnotovým kódováním

Hodnotové kódování funguje velmi dobře pro některé specializované problémy. Na druhou stranu je často nutné navrhnout nové operátory křížení a mutace, které budou specifické pro daný problém.

image
Příklad problému: Hledání vah pro neuronovou síť
Problém: Je dána neuronová síť s určitou architekturou. Hledejte váhy vstupů neuronů tak, aby síť produkovala požadovaný výstup.
Kódování: Reálné hodnoty v chromozomech reprezentují odpovídající váhy vstupů.
image

Stromové kódování

Stromové kódování se používá hlavně pro evoluci programů nebo výrazů, tedy pro genetické programování.

Při stromovém kódování je každý chromozom strom objektů, jako jsou funkce nebo příkazy v programovacím jazyce.

Chromozom A

Chromozom B
image image

( +  x  ( /  5  y ) )

( do_until  step  wall )

Příklad chromozomů se stromovým kódováním

Stromové kódování je velmi vhodné pro evoluci programů. Programovací jazyk LISP se k tomu často používá, protože jeho programy jsou v této podobě přirozeně reprezentovány a lze je snadno parsovat jako stromy, takže křížení a mutaci lze provádět poměrně snadno.

image
Příklad problému: Hledání funkce z daných hodnot
Problém: Jsou dána některá vstupní a výstupní data. Úkolem je najít funkci, která dává nejlepší výstup (nejbližší požadovanému) pro všechny vstupy.
Kódování: Chromozomy jsou funkce reprezentované jako stromy.
image