Testovacia úloha pre genetický algoritmus - História úprav

Juraj na 08:45, 20. júl 2010

2010-07-20T08:45:40Z

Juraj: Vytvorená stránka „Kategória:Študentské práce Kategória:Ročníkové práce Kategória:Matematika {{Praca_uvod|3|Analyzátor nameraných dát z meracích prístrojov v priemy…“

2010-07-20T08:44:54Z

Vytvorená stránka „Kategória:Študentské práce Kategória:Ročníkové práce Kategória:Matematika {{Praca_uvod|3|Analyzátor nameraných dát z meracích prístrojov v priemy…“

Nová stránka

[[Kategória:Študentské práce]]
[[Kategória:Ročníkové práce]]
[[Kategória:Matematika]]
{{Praca_uvod|3|Analyzátor nameraných dát z meracích prístrojov v priemysle|Teória genetických algoritmov|Implementácia genetických algoritmov|Testovacia úloha pre genetický algoritmus}}
__TOC__
= =
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 <nowiki>< 4.9 ; 7.3 ></nowiki>.

[[Súbor:rpphga3.1.jpg:framed|center|Obr. 3.1: Zadávanie intervalu aproximácie]]

Po prebehnutí analýzy mala výsledná aproximujúca krivka nasledovný tvar.

[[Súbor:rpphga3.2.jpg:framed|center|Obr. 3.2: Aproximujúca krivka (výstup programu)]]

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:

[[Súbor:rpphga3.3.jpg:framed|center|Obr. 3.3: Priebeh genetického algoritmu]]

'''''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:

[[Súbor:rpphga3.4.jpg:framed|center|Obr. 3.4: Aproximujúca krivka bez elitizmu]]

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.

[[Súbor:rpphga3.5.jpg:framed|center|Obr. 3.5: Priebeh genetického algoritmu bez použitia elitizmu]]

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>.

@@ Riadok 13: / Riadok 13: @@
 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 <nowiki>< 4.9 ; 7.3 ></nowiki>.
-[[Súbor:rpphga3.1.jpg:framed|center|Obr. 3.1: Zadávanie intervalu aproximácie]]
+[[Súbor:rpphga3.1.jpg|framed|center|Obr. 3.1: Zadávanie intervalu aproximácie]]
 Po prebehnutí analýzy mala výsledná aproximujúca krivka nasledovný tvar.
-[[Súbor:rpphga3.2.jpg:framed|center|Obr. 3.2: Aproximujúca krivka (výstup programu)]]
+[[Súbor:rpphga3.2.jpg|framed|center|Obr. 3.2: Aproximujúca krivka (výstup programu)]]
 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:
@@ Riadok 25: / Riadok 25: @@
 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:
-[[Súbor:rpphga3.3.jpg:framed|center|Obr. 3.3: Priebeh genetického algoritmu]]
+[[Súbor:rpphga3.3.jpg|framed|center|Obr. 3.3: Priebeh genetického algoritmu]]
 '''''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:
-[[Súbor:rpphga3.4.jpg:framed|center|Obr. 3.4: Aproximujúca krivka bez elitizmu]]
+[[Súbor:rpphga3.4.jpg|framed|center|Obr. 3.4: Aproximujúca krivka bez elitizmu]]
 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.
-[[Súbor:rpphga3.5.jpg:framed|center|Obr. 3.5: Priebeh genetického algoritmu bez použitia elitizmu]]
+[[Súbor:rpphga3.5.jpg|framed|center|Obr. 3.5: Priebeh genetického algoritmu bez použitia elitizmu]]
 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.