Algoritmy umelej inteligencie 4 - Genetické algoritmy
Mobile
4
 min read
September 5, 2022

Algoritmy umelej inteligencie 4 - Genetické algoritmy

Jan Kandráč
Jan Kandráč
Android Developer
LinkedIn Logo

Všetky optimalizačné algoritmy, ktoré sme doteraz skúšali, upravovali jedno náhodne vygenerované riešenie upravili ho a za určitých podmienok ho akceptovali do ďalšieho “kola”. Algoritmy, ktoré nás čakajú teraz, fungujú na trochu inom princípe. Namiesto jedného riešenia vygenerujeme náhodných riešení hneď niekoľko a budú na seba navzájom vplývať.

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.

Kríženie - Rodičia
Kríženie - Potomkovia

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:

Mutácia

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)

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

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

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 🙂

Like what you see?
Join our newsletter.

Great! Welcome to newsletter.
Oops! Something went wrong while submitting your email.
High quality content once a month. No spam, we promise.
Your personal data is processed in accordance with our Memorandum on Personal Data Protection.

Páči sa vám náš content?
Odoberajte newsletter.

Great! Welcome to newsletter.
Oops! Something went wrong while submitting your email.
Vaše osobné údaje sú spracované v súlade s našim Memorandom na ochranu osobných údajov.