Testovacia úloha pre genetický algoritmus
| 1. | Teória genetických algoritmov |
| 2. | Implementácia genetických algoritmov |
| 3. | Testovacia úloha pre genetický algoritmus
|
Obsah
Pri testovaní funkčnosti navrhnutého algoritmu implementovaného vo finálnej aplikácii bol použitý súbor s nameranými dátami zo súboru data.dat, ktorý je spolu s aplikáciou uložený na CD ako príloha. Tento súbor obsahuje 1258 nameraných bodov v tvare x tabelátor y, pričom aj výsledný program je naprogramovaný tak, aby mohol načítať dáta v takomto tvare. Po nahratí súboru programom sa dáta automaticky zobrazia v grafe a je tak možné vidieť aký priebeh sa chystáme aproximovať. Do poľa určeného k zadávaniu aproximačnej funkcie bola zadaná funkcia v nasledujúcom tvare:
[math] sin(k*x+k)+sin(k*x+k)+sin(k*x+k)+sin(k*x+k) [/math]
Program umožňuje určiť aproximačný interval, teda hranice od akej hodnoty x po akú hodnotu x sa budú dáta aproximovať. V tomto konkrétnom príklade bol zvolený interval aproximácie < 4.9 ; 7.3 >.
Po prebehnutí analýzy mala výsledná aproximujúca krivka nasledovný tvar.
Na výstupnom priebehu Obr. 3.2 sú modrou farbou znázornené dáta, ktoré boli aproximované, červenou farbou je znázornená krivka, ktorú našiel genetický algoritmus a zelenou farbou je znázornený skutočný priebeh nameraných dát. Je vhodné tiež podotknúť ako bol genetický algoritmus nastavený, teda koľko iterácii bežal, aká bola hodnota pravdepodobnosti mutácie a koľko jedincov zachovával elitizmus respektíve či bol elitizmus vôbec použitý. Genetický algoritmus bol nastavený nasledovne:
- Počet iterácii algoritmu N = 1000
- Pravdepodobnosť mutácie pm = 1,5 %
- Elitizmus bol použitý a zachovával 10 jedincov
Program umožňuje tiež zobrazenie priebehu genetického algoritmu, čo môže dať veľmi dobrý obraz o tom, ako sa algoritmus počas výpočtu správal. Graf priebehu genetického algoritmu pre tento testovací príklad vyzerá nasledovne:
Experiment: Ako už bolo spomenuté použitie elitizmu v genetickom algoritme to, že algoritmus dokáže rýchlejšie skonvergovať populáciu a taktiež to, že hodnota najlepšieho jedinca nebude kolísať, ale sa veľmi rýchlo ustáli. V nasledujúcom experimente bolo nastavené, aby elitizmus nebol pri výpočte algoritmu použitý. Taktiež bola nastavená hodnota pravdepodobnosti mutácie vyššia, aby bolo zreteľnejšie vidieť vplyv elitizmu. Pravdepodobnosť mutácie bola teda nastavená na 10%. Interval aproximácie a taktiež počet iterácii genetického algoritmu bol nastavený tak isto ako v predchádzajúcom teste. Taktiež zadaná funkcia, podľa ktorej budú dáta aproximované zostala zachovaná. Po prebehnutí výpočtu mala aproximujúca funkcia nasledujúcu podobu:
Je vidno mierny rozdiel oproti predchádzajúcemu testu, ale príčinu prečo je tomu tak je možné zistiť až z grafu priebehu genetického algoritmu, ktorý má nasledujúci tvar.
Z priebehu na Obr. 3.5 je možné usúdiť, prečo bol priebeh aproximujúcej funkcie na Obr. 3.4 odlišnejší od priebehu na Obr. 3.2, kde bol elitizmus použitý. Vidno tu, že ohodnotenie najlepšieho jedinca sa neustále menilo a neudržiavalo sa na ustálenej hodnote. Takýto značne veľký rozkmit ohodnotenia najlepšieho jedinca bol spôsobený aj vyššou hodnotou pravdepodobnosti mutácie.
Záver
Úlohou tejto práce bolo vytvoriť aplikáciu v ľubovoľnom programovacom jazyku, ktorá pre zadanú množinu vstupných bodov nájde aproximujúcu funkciu vo vopred určenom, užívateľom definovanom tvare použitím vhodného genetického algoritmu. Pri riešení práce som sa zaoberal pochopeniu princípov genetického algoritmu, spracoval som teóriu týkajúcu sa tohto algoritmu a hlavným výstupom bolo to, že som naprogramoval v programovacom jazyku c++ danú aplikáciu. Túto aplikáciu som sa snažil vytvoriť čo najviac používateľsky prijateľnú, tak aby mal užívateľ čo najviac možností nastavenia jednotlivých vlastností či už samotného genetického algoritmu alebo zobrazenia priebehov funkcii v grafe. Užívateľ má tiež možnosť si uložiť výsledný priebeh aproximujúcej funkcie vo formáte bmp alebo si môže nastaviť hranice aproximácie a pod. Tento výsledný program je určený pre platformu Windows a je spolu aj s testovacími dátami uložený na CD v prílohe.
Použitá literatúra
- OBITKO, Marek. Biological background - Introduction to Genetic Algorithms [online]. verzia 1.0. c1998 , 1998 [cit. 2009-11-16]. Dostupný z WWW: <http://www.obitko.com/tutorials/genetic-algorithms/biological-background.php>.
- KVASNIČKA, Vladimír, POSPÍCHAL, Jiří, TIŇO, Peter. Evolučné algoritmy. Bratislava : STU, 2000. 215 s. ISBN 80-227-1377-5.
- HYNEK, Josef. Genetické algoritmy a genetické programování. 1. vyd. Praha : Grada, 2008. 200 s. ISBN 978-80-247-2695-3.
- Genetický algoritmus [online]. [2008] , 10.12.2009 [cit. 2009-10-21]. Text v češtine. Dostupný z WWW: <http://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus>.
