| Seznam |
| Téma: | Moderní evoluční algoritmy pro hledání oblastí s vysokou fitness |
|---|---|
| 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, FITNESS FUNKCE, ODHADY ROZDĚLENÍ PRAVDĚPODOBNOSTI, FOKUSACE) 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. |
| Pokyny: | 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. |
| Literatura: | 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. •H. Mühlenbein, T. Mahnig, and A. Ochoa. Schemata, Distributions and Graphical Models in Evolutionary Optimization. Journal of Heuristics, 5 (1999), 213–247. •C.E. Priebe. Adaptive mixtures. Journal of the American Statistical Association, 89 (1994), 796–806. |
| Vypsáno dne: | 16.10.2009 |