Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
   Přihlásit přes CAS
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í, fitness 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.
 
Univerzita Karlova | Informační systém UK