Hromádky II - Genetické operátory

Minule jsme si začali hrát s problémem loupežníků a některým z vás se podařilo pomocí hrubé síly nebo dlouhého ladění parametrů dosáhnout pěkných výsledků. Na dnešních cvičeních se pokusíme získat podobně pěkné výsledky s menší námahou, rychleji a spolehlivěji.

Genetické operátory

Během minulých cvičení jsem vám záměrně zakázal měnit genetické operátory a nechal jsem vás hrát si jen s fitness a nastavením, abyste viděli, jak se pomocí těchto parametrů dá ovlivnit úspěšnost evoluce. Část z vás ale už nejspíš tušila (minimálně podle dotazů), že správná volba operátorů ovlivní výsledek více.

Volba operátorů samozřejmě hodně závisí na volbě kódování jedince. V našem případě, kdy je jednoduché udržet kódování jedinců platné, mohou být jednoduché i operátory.

Pro křížení máme několik variant:

• Jednobodové křížení - to jsme používali minule, náhodně se vybere místo pro křížení a části jedinců za tímto místem se prohodí
• Dvoubodové křížení - vyberou se dvě místa v jedinci a prohodí se to, co je mezi nimi, samozřejmě můžete zobecnit na n-bodové křížení
• Uniformní křížení - jedinec se prochází od začátku do konce a na každé pozici se rozhoduje, jestli se prohodí s druhým jedincem, nebo ne, jedná se vlastně o zobecnění n-bodového křížení

Stejným způsobem máme i několik jednoduchých mutací, které se dají použít:

• Mutace, která náhodně mění jednu pozici na platnou hodnotu - tu jsme používali minule, je hodně jednoduchá a často první, co vyzkoušíte
• Mutace, která prohazuje části kódu uvnitř jedince - náhodně se vyberou dva stejně dlouhé úseky jedince a prohodí se mezi sebou, v nejjednodušším případě se prohodí jen dvě pozice mezi sebou

Čemu odpovídá první a druhá mutace v našem zadání s hromádkami? První mutace vezme předmět a dá ho na jinou hromádku, druhá mutace vezme předměty ze dvou hromádek a prohodí je mezi sebou (v případě, že délka úseků je 1, jinak je to složitější). Je některá z těchto mutací pro naše zadání lepší?

Chytré operátory

Operátory uvedené výše fungují zcela náhodně, ale můžeme si představit i operátory, které využívají toho, že znají konkrétní instanci konkrétního problému, který řeší. Takové operátory potom nazýváme chytré (informované).

V našem případě si lze snadno představit chytrou mutaci - například takovou, že vždy přehodí nějaký předmět z těžké hromádky na lehkou hromádku. Můžeme jít ještě dál a vzít několik předmětů z jedné hromádky a několik předmětů z druhé tak, aby se rozdíl mezi těmi hromádkami co nejvíce zmenšil.

V extrémním případě bychom samozřejmě mohli v rámci mutace problém rovnou vyřešit. Je otázka, jestli v takovém případě ještě půjde o evoluční algoritmus, jestli takový postup bude efektivní, a jestli by nebylo lepší pustit jen tu mutaci samostatně.

Pro problém hromádek je dost těžké vymyslet nějaké chytré křížení, ale obecně by se takové najít mohlo. Nicméně mnohem častější jsou chytré mutace.