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

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.