Úvod do algoritmov umelej inteligencie #4 - Genetické algoritmy

Nazvime teda jedno riešenie jedincom alebo chromozómom a viacero riešení populáciou alebo genómom. Kto je najsilnejší jedinec v populácii? Ten, ktorý je najlepšie prispôsobený životu v prostredí. Hovoríme, že tento jedinec má najvyššie fitness.

Algoritmus

Pri tomto algoritme sa hodí nazrieť pod kapotu okamžite

1. vytvoríme populacia = náhodných riešení (jedincov, chromozómov)
2. kým nebudeme spojoní s výsledkom
   a. vytvor novú prázdnu populáciu nova_populacia
   b. do nova_populacia pridaj elite najlepších riešení z populacia
   c. kým |nova_populacia| < |populacia|
         i.   rodic1 = náhodný jedinec z populacia
         ii.  rodic2 = náhodný jedinec z populacia
         iii. dieta = krizenie(rodic1, rodic2)
         iv. mutacia(dieta)
         v.  nova_populacia pridaj dieta
   d. populacia = nova_populacia

Čo sa teda deje v našom cykle (2)? Do ďalšej populácie nechávame prežiť niekoľko najlepších riešení bez akejkoľvek zmeny. A zvyšných potomkov generujeme krížením a mutáciami. Rodičov do kríženia vyberáme riadenou náhodou tak, aby lepší jedinci mali väčšiu šancu zúčastniť sa kríženia. Poďme si ale všetky tieto kroky vyskúšať zaradom.

Výber rodičov do kríženia (Selection)

Pre výber rodičov sa používajú viaceré algoritmy:

1. Turnajový výber - z populácie vyberieme n jedincov. Do kríženia vyberáme toho z nich, ktorý má najvyššiu fitness
2. Ruleta - každý jedinec populácie dostane na kolese šťastia taký veľký dielik, aká veľká je jeho fitness v rámci populácie. Zatočíme kolesom a na koho padne, bude vybraný do ďalšej populácie
3. a ďalšie

V praxi som ale použil len prvé 2 pričom turnaj je oveľa jednoduchší na implementáciu.

Kríženie (Crossover)

Obaja rodičia sú chromozómami, ktoré vieme v akomkoľvek mieste preseknúť. Ak oboch rodičov presekneme na rovnakom mieste, vieme z ich opačných častí vyskladať nového jedinca. Hneď bude aj obrázok, ale najprv si predstavme ako vyzerá jedinec pri probléme ôsmich dám. Jedinec bude zložený z 8 čísel. Prvé číslo určuje na koľkom riadku v prvom stĺpci sa nachádza dáma.

Takže napríklad jedinec { 1, 3, 5, 3, 7, 7, 0, 5 } reprezentuje takúto šachovnicu.

Teda krížením rodičov { 1, 3, 5, 7, 7, 0, 5 } a { 7, 4, 1, 0, 2, 6, 4, 7} môžeme dostať napríklad potomkov { 1, 3, 5, 0, 2, 6, 4, 7 } a { 7, 4, 1, 3, 7, 7, 0, 5}. To v prípade, ak miesto kríženia bude rovné 3.

Mutácia

Mutácia je len dodatočnou maličkou (ak vôbec) úpravou potomka. Nikdy ju neaplikujeme nad rodičmi. Vieme si ju predstaviť napríklad nasledovne: S pravdepodobnosťou 10% vyber náhodnú vlastnosť jedinca a prideľ jej náhodnú hodnotu. Prvého potomka z predchádzajúceho obrázku by sme mutáciou upravili napríklad nasledovne:

Riešenie pre problém 8 dám

Teraz si ukážme ako presne vieme naprogramovať riešenie pre problém 8 dám. Budeme postupovať podľa návodu vyššie.

1. Vytvoríme si náhodnú populáciu (1)

var populacia = (0 until populationSize).map { nahodnyChromozom() }
fun nahodnyChromozom() = (0 until chromosomeSize).map { nahodnyGen() }

2. V cykle si do novej populácie uložíme niekoľko najlepších jedincov z predchádzajúcej populácie (2b)

val najlepsi_jedinci = (0 until pocet_najlepsich).map { populacia[it] }

3. Vyberieme si dvoch rodičov pomocou turnaja, získamedieťa pomocou kríženia týchto rodičov a pripadne dieťa zmutujeme (2c)

val individual1 = turnaj()
val individual2 = turnaj()
val child = krizenie(individual1, individual2)
mutacia(child)

4. Novú populáciu si uložíme a pokračujeme (2d)

Celé riešenie problému ôsmich dám môžete nájsť na tomto giste. Riešenie je pomalšie ako v prípade simulovaného žíhania. Prakticky je pekne využiteľný pre ~20 dám. Dôvodov môže byť viacero. Buď je nízka miera mutácie, alebo príliš rýchla konvergencia populácie do príliš podobných jedincov, alebo… alebo…

Žiaľ pri optimalizačných algoritmoch nikdy nevieme na prvýkrát určiť, aké najlepšie parametre pre náš problém potrebujeme zvoliť.

Nabudúce sa skúsme pozrieť na ďalšie optimalizačné algoritmy. Konkrétne teda ACO a PSO. Ak vám tieto skratky nič nehovoria, aspoň vás prekvapím 🙂