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ů.
· 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.