Metaevoluce - syntéza evolučních algoritmů pomocí symbolické regrese

DSpace Repository

Login

Language: English čeština 

Metaevoluce - syntéza evolučních algoritmů pomocí symbolické regrese

Show simple item record

dc.contributor.advisor Zelinka, Ivan
dc.contributor.author Oplatková, Zuzana
dc.date.accessioned 2010-07-16T10:27:06Z
dc.date.available 2010-07-16T10:27:06Z
dc.date.issued 2007-12-14
dc.identifier Elektronický archiv Knihovny UTB cs
dc.identifier.uri http://hdl.handle.net/10563/5221
dc.description.abstract Toto pojednání je zaměřeno na vysvětlení, jak může být Analytické programování (AP) použito pro vytvoření nových optimalizačních algoritmů, pravděpodobně evolučního charakteru. Evoluční algoritmy (EA) jsou nástrojem pro optimalizaci složitých úloh. Jedním z cílů práce je ukázat, že je možné syntetizovat účinný algoritmus, který bude založený na evolučních principech. Toto všechno se skrývá pod pojmem metaevoluce, jak ji chápeme z našeho pohledu. Nejprve jsou popsány současné metody pro regresi - Genetické programování (GP), Gramatická evoluce a AP, které je použito v simulacích. Dále jsou popsány EA, které byly použity pro simulace a také k porovnání jejich robustnosti. Následující část popisuje simulační experimenty, které byly provedeny AP. Nejprve jsou zachyceny simulace pro aproximaci dat, hledání vhodného matematického zápisu. Tato formule, která je vystavěná z jednoduchých funkcí jako je plus, minus nebo proměnné x či konstanty, by měla proložit data co nejlépe. Simulace potvrdily, že AP je schopné pracovat s tímto typem problémů, dokonce s menším počtem ohodnocení účelové funkce než GP. Pro aproximaci dat byly provedené 4 studie - Quintic, Sextic, Three Sine and Four Sine problém. Druhou úlohou bylo navržení elektronických obvodů. Cílem bylo najít zapojení obvodu funkcí odpovídající dané pravdivostní tabulce. Z funkcí jako je And, Nand, Or a vstupů byly vytvořeny konečné výrazy k - symetrického a k - sudého problému. Hodnoty k byly postupně nastaveny na hodnoty 3 až 6 pro oba problémy. Poslední úlohou, která měla prokázat, že AP je schopné pracovat i s lingvistickými výrazy jako jsou např. příkazy pro robota, bylo nastavení jeho optimální trajektorie. Na definované cestě bylo rozmístěno jídlo a také překážky. Umělý mravenec (viz GP) měl sníst všechno jídlo na této trase. Mravenec musel také překonat umístěné překážky, které v tomto případě byly políčka na cestě, kde jídlo nebylo. Tyto předpoklady vedly k hypotéze, že AP je schopno vytvořit i nový optimalizační algoritmus, pravděpodobně evolučního charakteru. Sekce 6 popisuje vývoj od první studie tohoto druhu až po simulace s více operátory a ve vyšších dimenzích. Na začátku jsme začali s operátory jednoho algoritmu, následovalo použití více operátorů z dalších evolučních a stochastických algoritmů. V tomto případě jsme také použili vylepšenou verzi účelové funkce. S ohledem na řád jednotlivých hodnot z testovacích funkcí jsme změnili výpočet hodnoty na rozdíl mezi nalezeným a globálním extrémem. To také umožnilo snadnější penalizaci týkající se počtu ohodnocení účelové funkce. Simulace v této sekci byly provedeny v 2 dimensionálním prostoru. To vedlo k třetímu kroku a to použití benchmark funkcí ve vyšších dimenzích jako kritérium v AP. Obdržené výsledky z vícerozměrových testovacích funkcí - 4 nalezené algoritmy - byly aplikovány na 16 testovacích funkcí ve 2, 20 a 100 dimenzionálním prostoru. Celkem bylo provedeno 192 simulací, z nichž každá byla 100krát zopakována. Z výsledků lze usoudit, že nalezené algoritmy jsou schopné optimalizovat multimodální funkce. Není možno říci, který z nich zvítězil, jednak kvůli ne zcela totožný počtům ohodnocení účelové funkce, ale také proto, že žádný algoritmus nevyhrál ve všech testovacích funkcích. Soutěžili dokonce i v různých dimenzích v rámci jedné funkce. Budoucí výzkum je otevřený v oblasti přidávání operátorů, ladění parametrů nalezených algoritmů nebo syntéza nového evolučního operátoru. cs
dc.format.extent 13828658 bytes
dc.format.mimetype application/pdf cs
dc.language.iso en
dc.publisher Univerzita Tomáše Bati ve Zlíně cs
dc.rights Bez omezení cs
dc.subject symbolická regrese cs
dc.subject Analytické Programování cs
dc.subject AP cs
dc.subject evoluční algoritmy cs
dc.subject nové evoluční algoritmy cs
dc.subject Symbolic Regression en
dc.subject Analytic Programming en
dc.subject evolutionary algorithms en
dc.subject new evolutionary algorithms en
dc.title Metaevoluce - syntéza evolučních algoritmů pomocí symbolické regrese cs
dc.title.alternative Metaevolution - Synthesis of Evolutionary Algorithms by Means of Symbolic Regression en
dc.type disertační práce cs
dc.date.accepted 2008-03-14
dc.description.abstract-translated This thesis is aimed at the explanation as to how Analytic Programming(AP) could be used for the creation of new optimizing algorithms, probably of evolutionary character. Evolutionary algorithms (EA) are tools for the optimization of difficult tasks. The principle of this thesis is to show that it might be possible to synthesize a powerful algorithm based on evolutionary ideas. The name of this thesis - metaevolution - covers all these ideas. Firstly, tools for regression are described - Genetic Programming (GP), Grammatical Evolution and AP; the last one is used in this study. Other tools, which are seen here, depict EA which were used for simulations purposes in order to also to compare their robustness. The following part describes projects which were conducted by AP. Firstly, simulations of fitting measured data are mentioned, which implies the use of regression to finding a suitable mathematical formula. This complex formula, based on simple functions like plus, minus or variables "x" and constants, should fit the data as closely as possible. The simulations proved that AP is able to perform such kinds of computations even in a smaller number of cost function evaluations compared to GP (four problems were carried out - Quintic, Sextic, Three Sine and Four Sine problem - to show that this type of regression works). The second task was to design electronic circuits. The aim was to find a configuration of circuits according to the truth table. Whole expression of k-symmetry and even-k-parity problems were created from simple functions like And, Nand, Or and inputs. Values 3 to 6 for both types of problems were set up for k. The last task, which proved that AP is able to work also with linguistic terms like commands for robot, was setting of its optimal trajectory. In the defined problem trail pieces of food were placed including some obstacles. The artificial ant (see GP) should eat all the food on such a trail while overcoming all obstacles. These presumptions led to the hypothesis that a new algorithm of evolutionary character can be created by AP. Section 6 describes the progress from the first study of a new EA synthesis to the simulations with more operators and higher dimensional systems. The beginning started with operators of one algorithm, next step continued with more operators from other evolutionary and stochastic algorithms. In this case also a new cost function was designed. With respect to the order of obtained cost values, the measurement was changed to minimize the difference between found extreme and the global one. This also affords to apply penalization concerned to cost function evaluations. Simulations in this section were performed in 2 dimensional space. This led to the third step, to use high dimensional benchmark functions as criterion in AP. The obtained results from higher dimensional test functions were then applied on 16 benchmark function in 2, 20 and 100 dimensional space for 4 found algorithms. Altogether 192 simulations were carried out in 100 times repetition; it means nearly 4 milliards of cost function evaluations. From results obtained, it can be stated that found algorithms are able to optimize multimodal functions. However, it is not possible to say which one was better because each won in some cases. They compete even inside one benchmark function in different dimensions. Future research is open to add more operators, to tune parameters of found algorithms or to try to synthesize a new evolutionary operator itself. en
dc.description.department Ústav řízení procesů cs
dc.description.result obhájeno cs
dc.thesis.degree-discipline Technická kybernetika cs
dc.thesis.degree-discipline Technical Cybernetics en
dc.thesis.degree-grantor Univerzita Tomáše Bati ve Zlíně. Fakulta aplikované informatiky cs
dc.thesis.degree-grantor Tomas Bata University in Zlín. Faculty of Applied Informatics en
dc.thesis.degree-name Ph.D.
dc.thesis.degree-program Chemické a procesní inženýrství cs
dc.thesis.degree-program Chemical and Process Engineering en
dc.identifier.stag 9899
dc.date.assigned 2003-09-01
local.subject optimalizační metody cs
local.subject optimization methods en


Files in this item

Files Size Format View
oplatková_2008_dp.pdf 13.18Mb PDF View/Open
oplatková_2008_vp.pdf 44.68Kb PDF View/Open
oplatková_2008_op.pdf 314.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Find fulltext

Search DSpace


Browse

My Account