Masarykova Univerzita Aplikácia evolučných algorimtov Supervisor Candidate Radovan Oprendek Radovan Oprendek - Aplikácia evolučných algorimtov 1 of 12 Obsah • Čo sú to evolučné algoritmy • Ako fungujú evolučné algoritmy • Ako ich využiť • Aplikácie v ekonómii a financiách 2 of 12 Radovan Oprendek - Aplikácia evolučných algorimtov Teória evolučných algoritmov • Evolúcia o evolúcia má tri základné prvky: prežitie najlepších, dedičnosť genetickej informácie, náhodné mutácie a kríženie • Evolučný algoritmus (EA) je vytvorenie evolúcie jedincov vo formálnom svete matematiky. o vytvorenie matematickej reprezentácie o určenie fitness funkcie • Využitie EA: o riešenie zložitých optimalizácií (genetický algoritmus) o hľadanie funkčného zápisu (genetické programovanie) o simulácia vyvíjajúceho sa procesu (evolučné programovanie) Radovan Oprendek - Aplikácia evolučných algorimtov 3 of 12 Genetický algoritmus • Reprezentácia (reťazce, vektory) • Fitness funkcia (jedincov treba usporiadať podľa vhodnosti riešenia) • Selekcia rodičov (najskôr vypočítať pravdepodobnosť, potom vyberať) • Rekombinácia (diskrétne: v jednom bode, uniformné / spojité: priemer) l|2|3|4|5|ó| 1 2 c d e | f • Mutácia (diskrétne: obrátený bit, náhodný reset, výmena, inverzia, vloženie / spojité: pričítanie náhodného čísla) 11 | m | i | 1b | • Inicializácia a terminácia (nastaviť podmienky ukončenia algoritmu) Radovan Oprendek - Aplikácia evolučných algorimtov 5 of 12 Genetické programovanie • Reprezentácia stromom • Rekombinácia výmenou podstromov 6 of 12 Radovan Oprendek - Aplikácia evolučných algorimtov Ako to využiť (bez veľkej námahy) • MATLAB obsahuje genetický algoritmus v rámci balíčku global optimization. »gatool • GPLAB: Sarah Silvia vytvorila voľne použiteľnú knižnicu pre MATLAB na genetické programovanie http://gplab.sourceforge.net. Radovan Oprendek - Aplikácia evolučných algorimtov 7 of 12 Využitie v ekonómii a financiách I • Akákoľvek ťažká optimalizácia o keď je ťažké zistiť konvexitu problému o keď je problém nekonvexný a nedá sa na konvexný ľahko tranformovať o keď má problém mnoho lokálnych optim • Data mining o hľadanie parametrov regresie o symbolická regresia (keď hľadáme aj podobu modelu) o hľadanie nastavení pre neurónovú sieť • Stock picking ° knapsack problém Radovan Oprendek - Aplikácia evolučných algorimtov 8 of 12 Využitie v ekonómii a financiách II. • Prechod k rovnovážnemu stavu v ekonómii o mainstreamová neoklasická ekonómia je úspešná v popisoch rovnovážnych stavov, avšak dynamika nieje zanedbateľná! ° existuje možnosť, že sa bežní ľudia predsa len nerozhodujú podľa diferenciálnych rovníc o iný prístup napr. Thomas Reichman: Genetic Algorithm Learning and Economic Evolution • spojenie EA, evolučných hier a ekonómie vytvorilo simuláciu zmien • reprodukcia = učenie sa nových stratégií komunikáciou • mutácia = učenie sa experimentom • fitness = úspech na trhu • týmto prístupom môžeme obísť častý a pomerne kontroverzný predpoklad úplnej racionality agentov • východisko z problému nemožnosti opakovaného ekonomického experimentu 9 of 12 Radovan Oprendek - Aplikácia evolučných algorimtov Využitie v ekonómii a financiách III • Vytvorenie pravidiel pre technické obchodovanie na burze o Mahmound Kaboudan: GP Forecasts of Stock Prices for Profitable Trading o prepoklad behaviorálnych vplyvov (napr. že niekto verí v technickú analýzu) o konštrukcia rozhodovacích pravidiel pomocou genetického programovania, kde jedinec je rozhodovací strom výsledok: o 20 % vyšší výnos ako pri pasívnom držaní akcií. o kritika: malá vzorka (4 akcie, krátky čas) o užitočnejší výsledok: možnosť konštruovať rozhodovacie pravidlá genetickým programovaním podľa nameraných dát Radovan Oprendek - Aplikácia evolučných algorimtov 10 of 12 Zoznam literatúry • J. E. Smith, A. E. Eiben. An Introduction to Evolutionary Computing. Springer, 2003. • Shu-Heng Chen. Evolutionary computations in economics and finance overview. In Shu-Heng Chen, editor, Evolutionary Computations in Economics and Finance. Physica-Verlad Heidelberg, 2002. • R. Oprendek. Aplikácia evolučných algoritmov. is.muni.cz/auth/th/323450/prif_b/ 4 □ ► Radovan Oprendek - Aplikácia evolučných algorimtov 11 of 12 J Ďakujem za pozornosť 12 of 12 Radovan Oprendek - Aplikácia evolučných algorimtov