Studium a srovnávání hlavních typů evolučních algoritmů

• Název práce v češtině: Studium a srovnávání hlavních typů evolučních algoritmů
• Název v anglickém jazyce: Study and comparison of main kinds of evolutionary algorithms
• Klíčová slova: evoluční algoritmy, smíšená optimalizace, lineární omezení, genetický algoritmus, diferenciální evoluce, evoluční strategie s adaptací kovarianční matice a dynamickým vytvářením nik
• Klíčová slova anglicky: evolutionary algorithms, mixed optimization, linear constraints, genetic algorithm, differential evolution, evolutionary strategy with covariance matrix adaptation and dynamic niching
• Akademický rok vypsání: 2008/2009
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra softwarového inženýrství (32-KSI)
• Vedoucí / školitel: prof. RNDr. Ing. Martin Holeňa, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 12.11.2008
• Datum zadání: 12.11.2008
• Datum a čas obhajoby: 30.01.2012 10:00
• Datum odevzdání elektronické podoby: 09.12.2011
• Datum odevzdání tištěné podoby: 09.12.2011
• Datum proběhlé obhajoby: 30.01.2012
• Oponenti: Mgr. Jakub Gemrot, Ph.D.

Zásady pro vypracování

Student se nejdříve seznámí se čtyřmi typy evolučních algoritmů, velmi důležitými z hlediska aplikací: genetickými algoritmy, algoritmy založenými na odhadech rozdělení proavděpodobnosti, diferenciálními evolučními algoritmy a evolucí kovarianční matice. 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í.

Seznam odborné literatury

* 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äck. Dynamic niching in evolution strategies with covariance matrix adaptation. In Proceedings of the 2005 Congress on Evolutionary Computation, IEEE, 2584?2591.
* R. Storn, K. Price. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11 (1997), 341-359.

Předběžná náplň práce

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.