Student World

Genetické algoritmy predstavujú vhodný prostriedok na optimalizáciu umelých neurónových sietí. Koevolúcia (evolúcia dvoch alebo viacerých súťažiacich populácií so spoločnou mierou vhodnosti) má niekoľko funkcií, ktoré môžu potencionálne rozšíriť silu adaptácie umelej evolúcie. V tomto článku bude uvedený spôsob nastavenia parametrov umelej neurónovej siete pomocou genetických algoritmov a pomocou koevolúcie, ktorá je realizovaná súčasnou činnosťou niekoľkých genetických algoritmov. Porovnanie oboch metód je vykonané na základe optimalizácie umelej neurónovej siete pre riadenie robotického systému.

Optimalizované systémy

Robotický systém, ktorý bude detailnejšie popísaný neskôr, je riadený pomocou umelej neurónovej siete. Koevolúcia je použitá na nastavenie parametrov neurónovej siete. Umelá neurónová sieť je použitá na riadenie robotického systému, ktorý môže reprezentovať korisť alebo predátora.
Parametre umelej neurónovej siete pre korisť majú byť nastavené tak, aby čo najdlhšie unikala predátorovi. Naopak parametre umelej neurónovej siete pre predátora majú byť nastavené tak, aby korisť unikala predátorovi čo najkratšie. Vstupom umelej neurónovej siete sú výstupy infračervených snímačov (rovnako pre korisť i pre predátora), ktorých má robotický systém 8 (5 v prednej a 3 v zadnej časti). Výstupy kamery so zorným uhlom 45 stupňov, ktorý je rozdelený na päť častí, sú použité taktiež ako vstupy robotického systému.
Citlivosť infračervených snímačov je rovná dvojnásobku dĺžky, ktorú je robotický systém schopný prekonať za jednotku času. Priebeh aktivačnej prechodovej funkcie výstupných neurónov odpovedá štandardnej sigmoide. Výstupné neuróny sú použité na riadenie motorov (pravý a ľavý motor) robotického systému, kde výstupná hodnota „1“ reprezentuje zapnutie príslušného motora na jeden časový krok. Ak je výstupná hodnota „0“ príslušný motor nie je aktivovaný.

Topológia neurónovej siete na riadenie robotického systému

Duel

Duel je súťaž predátora a koristi v ohraničenom priestore, ktorý možno nazvať aréna. Počiatočné umiestnenie predátora a koristi je rovnaké, ale mení sa počiatočné natočenie predátora (koristi) oproti koristi (predátorovi). Cieľom predátora je v čo najkratšom čase, ktorý je reprezentovaný počtom časových krokov, chytiť korisť. Cieľom koristi je prežitie čo najväčšieho počtu časových krokov bez chytenia predátorom. Dĺžka duelu je stanovená na 500 časových krokov, pričom duel môže skončiť skôr chytením koristi predátorom. Víťazom duelu je predátor, ak sa mu podarí chytiť korisť za menej ako 500 časových krokov. V opačnom prípade je víťazom korisť.
Ohodnotenie jedincov pre genetický algoritmus a pre koevolúciu je realizované na základe výsledkov, ktoré ohodnocovaní jedinci dosiahnu v duely. Dĺžka duelu je potom priamo úmerná vhodnosti koristi a nepriamo úmerná vhodnosti predátora.

Optimalizačné metódy

Optimalizácia umelých neurónových sietí na riadenie robotických systémov je vykonaná pomocou dvoch metód. Prvá metóda je založená na optimalizácii genetickým algoritmom. Druhá metóda používa koevolúciu, ktorá je realizovaná súčasným behom dvoch genetických algoritmov.
Optimalizácia pomocou genetických algoritmov je vykonaná na základe ohodnotenia jedincov z populácie na základe výsledkov dosiahnutých v duely s jedincami z učiacej množiny. Počas činnosti genetického algoritmu ostáva obsah množín nezmenený.
Pri použití koevolúcie je vykonané ohodnotenia jedincov na základe výsledkov dosiahnutých v duely s jedincami z tabuľky najlepších jedincov. Táto tabuľka je počas optimalizácie modifikovaná na základe dosiahnutých výsledkov populácie s opačným cieľom.

Genetický algoritmus

Genetický algoritmus možno použiť na nastavenie parametrov umelých neurónových sietí (topológie, váhových a práhových koeficientov). V našom článku sú nastavované parametre umelej neurónovej siete (váhové a práhové koeficienty), ale topológia siete sa nemení.
Prvá populácia je generovaná náhodne. Veľkosť populácie je 100 genotypov, činnosť genetického algoritmu je ukončená po 500 generáciách. Genetický algoritmus používa operátor selekcie („roulette wheel“), kde pravdepodobnosť výberu proporcionálne odpovedá miere vhodnosti príslušného genotypu. Použitý genetický algoritmus aplikuje na populáciu homogénny operátor kríženia a štandardný operátor mutácie. Genotyp reprezentuje váhové a práhové koeficienty umelej neurónovej siete.
Miera vhodnosti predátora odpovedá prevrátenej hodnote počtu časových krokov, ktoré boli potrebné na chytenie koristi. Čim je menší počet časových krokov, ktoré boli potrebné na chytenie koristi, tým je miera vhodnosti predátora väčšia. Miera vhodnosti koristi odpovedá priamo počtu časových krokov, počas ktorých korisť nebola chytená. Čim je väčší počet časových krokov, počas ktorých korisť nebola chytená, tým je miera vhodnosti koristi väčšia.
Genetický algoritmus je použitý na optimalizáciu parametrov umelej neurónovej siete pre populáciu koristí a populáciu predátorov. Boli vytvorené dve učiace množiny, ktoré sú použité genetickým algoritmom na určenie miery vhodnosti každého jedinca z populácie. Prvá množina obsahuje predátorov (viď obrázok), ktorých správanie a použitá stratégia na chytenie koristi sú náhodne generované. Druhá množina obsahuje koristi (opäť viď obrázok), ktorých správanie a použitá stratégia na prežitie čo najväčšieho počtu časových krokov sú náhodne generované.
Počas vyhodnocovania miery vhodnosti každého jedinca z populácie koristí je realizovaný duel príslušného jedinca s každým predátorom z učiacej množiny predátorov. Výsledná miera vhodnosti je rovná súčtu mier vhodnosti pre každý duel, ktorého sa príslušný jedinec zúčastnil. Jedinci z populácie koristí sú potom adaptovaní na správanie niekoľkých predátorov a nie na správanie jedného. Rovnako je použitá učiacia množina koristí je použitá genetickým algoritmom na optimalizáciu parametrov umelej neurónovej siete pre populáciu predátorov.
Počas vyhodnocovania miery vhodnosti každého jedinca z populácie predátorov je realizovaný duel príslušného jedinca s každou korisťou z učiacej množiny koristí. Výsledná miera vhodnosti je rovná súčtu mier vhodnosti pre každý duel, ktorého sa príslušný jedinec zúčastnil. Jedinci z populácie predátorov sú týmto adaptovaní na správanie niekoľkých koristí a nie na správanie jednej.

Koevolúcia

Koevolúcia je reprezentovaná súčasným priebehom činnosti dvoch genetických algoritmov, ktorých populácie sú vzájomne ovplyvňované. Nastavenie a použité operátory genetických algoritmov pre koevolúciu sú rovnaké ako v prípade optimalizácie pomocou genetického algoritmu. Prvý genetický algoritmus optimalizuje nastavenie parametrov umelej neurónovej siete alebo množinu pravidiel pre produkčný systém pre populáciu predátorov. Druhý optimalizuje nastavenie parametrov umelej neurónovej siete alebo množinu pravidiel pre produkčný systém pre populáciu koristí.
Postupne je vytvorená tabuľka najlepších predátorov („hall of fame“), ktorí počas činnosti genetického algoritmu dosiahli najväčšiu mieru vhodnosti. Najlepší genotyp z populácie je do tejto tabuľky zaradený, ak jeho miera vhodnosti je väčšia než miera vhodnosti jedinca, ktorý ju má najmenšiu zo všetkých jedincov v tabuľke. Pred zaradením nového jedinca do tabuľky najlepších jedincov (predátorov alebo koristí) je jedinec s najmenšou mierou vhodnosti vyradený z tabuľky. Počiatočne nastavenie tabuľky je náhodné, pričom všetky jedinci majú vhodnosť minimálnu. Podobne je vytvorená tabuľka najlepších koristí, ktorí počas činnosti genetického algoritmu dosiahli najväčšiu mieru vhodnosti.
Tabuľka najlepších predátorov je použitá genetickým algoritmom na optimalizáciu parametrov umelej neurónovej siete pre populáciu koristí. Počas vyhodnocovania miery vhodnosti každého jedinca z populácie koristí je realizovaný duel príslušného jedinca s každým predátorom z tabuľky najlepších predátorov. Výsledná miera vhodnosti je rovná súčtu mier vhodnosti pre každý duel, ktorého sa príslušný jedinec zúčastnil. Týmto je zabezpečená adaptácia jedincov z populácie koristí na niekoľko najlepších predátorov a nie na správanie jedného. Rovnako tabuľka najlepších koristí je použitá genetickým algoritmom na optimalizáciu parametrov umelej neurónovej siete pre populáciu predátorov.
Počas vyhodnocovania miery vhodnosti každého jedinca z populácie predátorov je realizovaný duel príslušného jedinca s každou korisťou z tabuľky najlepších koristí. Výsledná miera vhodnosti je rovná súčtu mier vhodnosti pre každý duel, ktorého sa príslušný jedinec zúčastnil. Týmto je zabezpečená adaptácia jedincov z populácie predátorov na niekoľko najlepších koristí a nie na správanie jedného.
Simulačný model bol vytvorený v prostredí programu Matlab od firmy MathWorks. Obsahuje model arény, model neurónovej siete pre predátora a korisť, ktoré sú použité genetickým algoritmom na vyhodnotenie miery vhodnosti.

Porovnanie metód

Z dôvodu realizácie porovnania boli vytvorené dve testovacie množiny, ktoré sú odlišné ako učiace množiny použité genetickým algoritmom. Prvá množina obsahuje predátorov, ktorých správanie a použitá stratégia na chytenie koristi sú náhodne generované. Druhá množina obsahuje koristi, ktorých správanie a použitá stratégia na prežitie čo najväčšieho počtu časových krokov sú náhodne generované. Porovnanie oboch optimalizačných metód je potom realizované na základe výsledkov, ktoré dosiahnú vybraní jedinci v duely s testovacou množinou jedincov. Vybraní jedinci reprezentujú najlepšie riešenia pre obidve optimalizačné metódy.
Najlepší predátor (korisť) sa stretne v duely so všetkými jedincami z testovacej množiny koristí (predátorov), ktorá obsahuje 10 jedincov. Jeden duel trvá maximálne 500 časových krokov. Celková dĺžka duelov, ktoré absolvuje každý predátor (korisť) je potom z intervalu 0 až 5000.

Prednosti koevolúcie

Z porovnania oboch metód jednoznačne vyplýva lepšia schopnosť adaptácie jedincov, ktorí boli získaní pomocou koevolúcie, na neznáme vzorky z testovacej množiny. Dĺžka trvania duelu pre jedincov, ktorí boli získaní pomocou genetických algoritmov, bola väčšia než pre jedincov získaných pomocou koevolúcie. Dôvodom je existencia učiacich množín pre genetický algoritmus, ktorých obsah ostal počas optimalizácie nezmenený. Naopak, obsah tabuliek najlepších jedincov pre optimalizáciu pomocou koevolúcie bol menený na základe ovplyvňovania populáciou s opačným cieľom.
Koevolúciu teda možno vhodne použiť v prípade, kedy nie je možné jednoducho vytvoriť učiacu množinu, a taktiež v prípade, ak do učiacej množiny nie možné zahrnúť všetky vzorky z dôvodu ich zložitého vytvárania. Pri použití koevolúcie je učiaca množina postupne vytváraná a modifikovaná. Takto možno zabezpečiť adaptáciu populácie i na situácie, ktoré nie sú štandardné alebo nebolo predpokladané, že nastanú.
Koevolúcia dvoch súťažiacich populácií môže produkovať komplexnejšie riešenia. Úspech populácie predátorov spôsobuje neúspech populácie koristí a naopak neúspech populácie predátorov je zapríčinený úspechom populácie koristí. Snahou neúspešnej populácie je adaptácia na víťaznú populáciu, ktorej výsledkom je úspech v nasledujúcej generácii, čo platí pre populáciu predátorov i koristí. Výkonnosť jedinca v populácii závisí taktiež od individuálnych stratégií jedincov v druhej populácii počas procesu evolúcie. Zmena povrchu miery vhodnosti („landscape“), vzhľadom na zmeny jedincov v druhej populácii, pôsobí preventívne proti uviaznutiu v lokálnom minime. Koevolúcia dvoch populácií (predátorov a koristí) je podobná evolúcii jednej populácie s meniacim sa okolným prostredím, ktoré na ňu pôsobí.

Znázornenie vybraných trajektórií učiacej množiny predátorov

Znázornenie vybraných trajektórií učiacej množiny koristí

autor Michal Turčaník