Zadání diplomové práce

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

(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í proavdě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. Navržená diplomová práce by proto měla být příspěvkem právě do této oblasti výzkumu.

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é testovací funkci, jakož i na jedné funkci 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ů.

 

Doporučená 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ä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.