Moderní evoluční algoritmy pro hledání oblastí s vysokou fitness

• Název práce v češtině: Moderní evoluční algoritmy pro hledání oblastí s vysokou fitness
• Název v anglickém jazyce: Modern evolutionary algorithms for detecting high-fitness areas
• Klíčová slova: optimalizace, evoluční algoritmy, odhad rozdělení, fi tness funkce
• Klíčová slova anglicky: optimization, evolutionary algorithms, estimation of distribution, fitness function
• Akademický rok vypsání: 2009/2010
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: prof. RNDr. Ing. Martin Holeňa, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 23.03.2009
• Datum zadání: 23.03.2010
• Datum a čas obhajoby: 31.01.2011 11:00
• Datum odevzdání elektronické podoby: 10.12.2010
• Datum odevzdání tištěné podoby: 10.12.2010
• Datum proběhlé obhajoby: 31.01.2011
• Oponenti: Mgr. Jakub Gemrot, Ph.D.

Zásady pro vypracování

Student se nejdříve důkladně seznámí s nedůležitějšími typy evolučních algoritmů pro hledání oblastí s vysokou fitness. Na základě teoretického rozboru poznatků získaných z prostudované literatury poté zformuluje hypotézy o tom, jak v jednotlivých z nich fokusace populace ovlivňuje výsledné hodnoty fitness funkce i rychlost konvergence algoritmu k nim. Tyto hypotézy bude ověřovat jednak na specifických testovacích funkcích pro evoluční algoritmy, jednak na datech ze skutečných aplikací, poskytnutých vedoucím práce. Spolu s jednotlivými typy evolučních algoritmů pro hledání oblastí s vysokou fitness bude testovat i dva tradiční typy evolučních algoritmů, po dohodě s vedoucím práce. Všechny testované algoritmy přitom implementuje ve vývojovém prostředí Matlab, s využitím jeho toolboxu Genetic algorithm and direct search. Pokud při teoretickém rozboru či dosavadním průběhu testování dojde k názoru, že by z hlediska výsledné hodnoty fitness funkce či rychlost konvergence mohly být slibné i některé nové modifikace některého či některých z testovaných evolučních algoritmů pro hledání oblastí s vysokou fitness, implementuje a zahrne do testování i tyto modifikace.

Seznam odborné literatury

* P.A.N. Bosman. Design and Application of Iterated Density Estimation Evolutionary Algorithms. Disertace, University of Utrecht, 2003.
* P. Larranaga, J.A. Lozano. Estimation of Distribution Algorithms, Kluwer, 2002. Kapitoly 1-4, 6-8.
* C.E. Priebe. Adaptive mixtures. Journal of the American Statistical Association, 89 (1994), 796-806.
* M. Sebag, A.Ducoulombier. Extending population-based incremental learning to continuous search spaces. In Parallel Problem Solving from Nature VI, Springer, 1998, 418-427.

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

Evoluční algoritmy jsou v posledních 20 letech jednou z nejúspěšnějších metod pro řešení netradičních optimalizačních problémů, jako např. hledání nejvhodnějších dokumentů obsahujících požadované informace, hledání nových materiálů nejvhodnějších z hlediska určitých vlastností, objevování nejzajímvějších informací v dostupných datech či další typy optimalizačních úloh, při nichž lze hodnoty optimalizované funkce získat pouze empiricky. Tradiční evoluční algoritmy jsou konstruovány s cílem nalezení globálního optima, kterému v evoluční terminologii odpovídá globální maximum tzv. fitness funkce. V řadě aplikací však spíše než o jeden jediný bod s nejvyšší hodnotou fitness jde o oblast, kde je fitness dostatečně vysoká (např. vyšší než daný práh). Hledání takových oblastí pomocí tradičních evolučních algoritmů je těžkopádné a zdlouhavé. Proto se od poloviny 90. let vyvíjejí speciální evoluční algoritmy pro hledání oblastí s vysokou fitness. V podstatě jsou založeny na postupné fokusaci populace postupným zvyšováním požadované hodnoty fitness funkce a na odhadování rozdělení pravděpodobnosti, že jedinec dosáhne alespoň požadovanou hodnotu. Oba kroky však lze provést různými způsoby, a protože jde o nový typ evolučních algoritmů, jsou ještě předmětem výzkumu. Dílčím příspěvkem k výzkumu v oblasti způsobu a rychlosti fokusace by měla být i navrhovaná diplomová práce.