| Seznam |
| Téma: | Studium a srovnávání hlavních typů evolučních algoritmů |
|---|---|
| Vedoucí: | |
| Vypsáno jako: | Diplomová práce |
| Popis: | Zadání je externí, zadavatel: Dr.Martin Holena,CSc. - Ústav informatiky AV ČR, Pod vodárenskou věží 2, Praha 8 (e:mail: martin@cs.cas.cz).
Garantem za katedru kybernetiky je: Ing.Petr Pošík,Ph.D. (e:mail: posik@labe.felk.cvut.cz) (Klíčová slova: EVOLUČNÍ ALGORITMY, OPTIMALIZACE, GENETICKÉ ALGORITMY, ROZDĚLENÍ PRAVDĚPODOBNOSTI, DIFERENCIÁLNÍ EVOLUCE, ADAPTACE KOVARIANCÍ) Jednou z nejrychleji se rozvíjejících oblastí moderní informatiky jsou algoritmy zahrnující heuristiky inspirované vývojovými procesy v přírodě, které se označují jako evoluční algoritmy. Nejstarší a nejznámější z nich jsou algorimty genetické, jejichž heuristiky byly inspirovány vývojem genotypu organizmů v závislosti na podmínkách, které působí na jejich fenotyp. Díky biologické motivaci svých heuristik mají všechny evoluční algoritmy dva důležité rysy: za prvé pracují s celou populací řešení, za druhé kombinují informace o úspěšnosti jednotlivých řešení s náhodnými vlivy. Hlavním důvodem intenzivního rozvoje evolučních algoritmů však není snaha přírodní vývojové procesy modelovat, ale skutečnost, že tyto procesy vykazují obdivuhodnou schopnost nalézat optimální nebo téměř optimální řešení i při velmi složitých podmínkách. Kvůli ní se evoluční algoritmy používají především k řešení složitých optimalizačních problémů, např. k optimalizaci empirických funkcí, které nelze popsat matematicky, k optimalizaci na složitých množinách, jako jsou množiny dokumentů nebo informací, či k optimalizaci při dynamicky se měnících podmínkách. Přitom se biologicky motivované heuristiky vždy kombinují s matematickými a informatickými přístupy. V závislosti na tom, se kterými a jakým způsobem, vznikají tímto kombinováním evoluční algoritmy různých typů. Kromě již zmíněných genetických algoritmů jsou v aplikacích asi nejúspěšnější algoritmy založené na odhadech rozdělení pravděpodobnosti, diferenciální evoluční algoritmy a evoluce kovarianční matice. Protože jde o novou oblast, soustřeďuje se výzkum v ní především na hledání dalších, dokonalejších algoritmů. Nové algoritmy jsou přitom srovnávány převážně s těmi, jejichž zdokonalením vznikly, aby bylo vidět, jak výrazná zlepšení přinášejí. Srovnání napříč spektrem různých typů evolučních algoritmů jsou naproti tomu vzácná, přestože právě taková srovnání jsou nejpřínosnější pro rozhodování, jaký typ použít v konkrétní aplikaci. Navrhovaná diplomová práce by proto měla být příspěvkem právě do této oblasti výzkumu. |
| Pokyny: | Student se nejdříve seznámí s výše uvedenými čtyřmi typy evolučních algoritmů. Implementuje je ve vývojovém prostředí Matlab, s využitím existujícího Genetic Algorithm and Direct Search Toolbox, a otestuje je na jedné mezinárodně používané optimalizační úloze, jakož i na jedné úloze ze skutečné aplikace, kterou dostane od vedoucího práce. Poté se bude seznamovat s různými variantami těchto typů evolučních algoritmů, s jejich kombinacemi a v případě zájmu i s dalšími typy evolučních algoritmů. Odpovídajícím způsobem rozšíří svou implementaci různých typů evolučních algoritmů. Současně rozšíří baterii používaných testů o řadu dalších mezinárodně používaných optimalizačních úloh a jednu další úlohu ze skutečné aplikace. Práci uzavře analýzou vhodnosti různých typů evolučních algoritmů, jejich variant a kombinací, pro různé typy optimalizačních úloh, kterou založí jednak na teoretických vlastnostech jednotlivých algoritmů, zejména ale na výsledcích svého testování. |
| Literatura: | •T. Bartz-Beielstein. Experimental Resarch in Evolutionary Computation, Springer, 2006. •P. Larranaga, J.A. Lozano. Estimation of Distribution Algorithms. Wiley, 2004. •O.M. Shir, T. B |
| Vypsáno dne: | 16.10.2009 |