Prírodou inšpirované algoritmy
študijné materiály pre projekt mobilnej triedy umelej inteligencie
Ako GA pracujú?
Ako GA pracujú?
Najprv je potrebné vybrať počiatočnú populáciu prístupných riešení. To sa deje väčšinou náhodne, ale ak máme k dispozícii nejaké heuristiky, môžeme ich uplatniť práve v tomto kroku. Ďalej, pretože budeme chcieť na tieto riešenia uplatňovať genetické operátory, ako kríženie a mutácia, potrebujeme ich mať k tomuto účelu reprezentované v nejakej vhodnej podobe. Ako dostatočne všeobecné sa javí kódovanie vo forme reťazca či poľa hodnôt. Máme teda nejakú počiatočnú populáciu organizmov (kde každý organizmus zodpovedá jednému chromozómu) a zápas o život môže začať. Prvý na radu prichádza výber jedincov, ktorí sa budú podieľať na vzniku novej generácie. Klasický prístup k tomuto problému obnáša ohodnotenie jedincov aktuálnej populácie na základe cieľovej funkcie a následný výber, kde pravdepodobnosť výberu daného jedinca je úmerná jeho relatívnemu ohodnoteniu. Štandardný genetický algoritmus pracuje s populáciou konštantnej veľkosti, takže sa vyberá presne toľko jedincov, aká je táto veľkosť. Samotný výber ešte samozrejme nedá vzniknúť žiadnym novým štruktúram. Na to sú tu genetické operátory, ako kríženie a mutácia. Kríženie samo o sebe znamená výmenu genetického materiálu, teda častí reťazcov medzi oboma jedincami. Mutácia slúži na udržovanie genetickej variácie v populácii a tým bráni, aby proces hľadania skĺzol len do oblasti nejakého lokálneho optima. Úlohou EA je teda nájsť globálny extrém hyperplochy a neuviaznuť pri jeho hľadaní v niektorom z lokálnych extrémov. EA pracujú obvykle paralelne s viacerými jedincami tvoriacimi populáciu - analogicky ako sa to deje v prírode. Jedná sa pritom o proces diskrétny v čase - postupne sa striedajú jednotlivé generácie. Proces opakujeme tak dlho, kým nie je splnená ukončovacia podmienka, ktorá môže byť daná napr. vo forme maximálneho počtu generácií alebo vo forme nejakého prijateľného limitu.
Na prehľadávanie problémového priestoru existujú vo všeobecnosti dva spôsoby:
- exploatácia - pri vytvorení novej generácie sa dôsledne využívajú "skúsenosti" predošlých generácií na určenie oblastí, sľubujúcich úspech pri hľadaní optimálneho riešenia; tento postup však nesie v sebe riziko uviaznutia v lokálnom extréme,
- explorácia - pri vytvorení novej generácie sa neberie ohľad na "skúsenosti" predošlých generácií (volíme ju napríklad náhodne); tento postup produkuje "skoky do neznáma", teda do úplne nových, neprebádaných oblastí - zabráni sa tým uviaznutiu v lokálnom extréme ale proces prehľadávania sa obvykle výrazne spomalí.
Zapísané vo forme pseudo-kódu by štandardný genetický algoritmus vyzeral nasledovne:
| t := 0 | |
| Initialize G(0) | ;inicializuj počiatočnú generáciu |
| Evaluate G(0) | ;ohodnoť |
| do while not Done | |
| t := t + 1 | |
| Select G(t) from G(t-1) | ;vykonaj prirodzený výber |
| Crossover G(t) | ;aplikuj kríženie |
| Mutate G(t) | ;aplikuj mutáciu |
| Evaluate G(0) | ;ohodnoť |
| Replace G(t-1) with G(t) | ;ohodnoť |
| loop |
 Vývojový diagram štandardného genetického algoritmu |
t=0 a vygeneruje sa východzia populácia G(0) pozostávajúca obvykle z náhodne vytvorených jedincov. Pre každého z nich sa v bloku Vyhodnotenie vypočíta jeho vhodnosť.Po teste na splnenie ukončovacej podmienky sa v bloku Selekcia vyberú z populácie G(t) na základe vhodnosti jedinci, určení na rozmnožovanie. Z nich sa v bloku Generovanie potomkov vytvoria noví jedinci pomocou genetických operátorov (obvykle krížením a mutáciou). V bloku Vyhodnotenie sa pre každého potomka vypočíta jeho vhodnosť. Blok Náhrada inkrementuje počítadlo generácií a realizuje vytvorenie novej generácie G(t+1) obvykle z potomkov, ale niekedy aj z jedincov generácie G(t). Naznačený cyklus pokračuje až po úspešný test v bloku Splnenie ukončovacej podmienky. |
