Detail of the student project

List
Topic:Využití metod návrhu experimentů v genetických algoritmech
Department:Katedra kybernetiky
Supervisor:
Announce as:DP
Description: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.Jiří Kubalík,Ph.D. (e:mail: kubalik@labe.felk.cvut.cz)

(Klíčová slova: GENETICKÉ ALGORITMY, EVOLUČNÍ ALGORITMY, NÁVRH EXPERIMENTŮ)

K nejmodernějším metodám globální optimalizace patří evoluční algoritmy, zejména jeden jejich typ - genetické algoritmy. Jejich charakteristickým rysem je, že způsob, kterým se metoda přibližuje k hledanému optimu, je inspirován přirozeným výběrem ve vývoji biologických druhů, v případě genetických algoritmů potom speciálně mutacemi a křížením chromozomů. Vzhledem k této biologické inspiraci je princip genetických algoritmů snadno srozumitelný i nematematikům, a právě díky tomu se v průběhu posledních let velmi rychle rozšířilo jejich používání při řešení optimalizačních úloh v nejrůznějších oborech. Z matematického hlediska jsou však evoluční a genetické algoritmy pouze dalšími zástupci stochastických optimalizačních algoritmů a vyžadují řešení podobných problémů jako další stochastické optimalizační algoritmy. Jedním z klíčových problémů je volba počátečního bodu posloupnosti, která by měla konvergovat k hledanému optimu. Protože genetické algoritmy v každé iteraci (označované v jejich případě jako generace) hledají celou množinu bodů (tzv. populaci), je nutné i v první generaci zvolit mezi přípustnými řešeními uvažované optimalizační úlohy celou množinu počátečních bodů. Volbou optimálních podmnožin přípustných množin bodů se v jiném kontextu již po desetiletí zabývá teorie návrhu experimentů. A právě využití metod návrhu experimentů při inicializaci genetických algoritmů by mělo být náplní navrhované práce.
Instruction:Student se nejdříve důkladně seznámí s principy genetických algoritmů i s hlavními metodami návrhu experimentů. Poté se seznámí s implementací genetických algoritmů v Genetic Algorithm and Direct Search Toolbox systému Matlab a přitom si rozváží, jak snadé by bylo do něj začlenit různé metody návrhu experimentů. S přihlédnutím k důležitosti jednotlivých metod i k náročnosti jejich začlenění do Genetic Algorithm and Direct Search Toolbox systému Matlab vybere 4–5 z nich, které rozpracuje do podoby implementovatelných algoritmů a naprogramuje jako matlabovské funkce použitelné pro při inicializaci genetických algoritmů.
Bibliography:•T. Bartz-Beilstein. Experimental Research in Evolutionary Computation. Springer: Berlin, 2006.
•A. Pazman. Foundations of optimum experimental design. Reidel, Dordrecht, 1986.
•C.R. Reeves, J.E. Rowe. Genetic Algorithms: Principles and Perspectives. Kluwer: Boston, 2003.
Date:15.10.2009
Responsible person: Petr Pošík