Detail of the student project

List
Topic:Urychlení evolučních algoritmů pomocí rozhodovacích stromů a jejich zobecnění
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.Petr Pošík,Ph.D. (e:mail: posik@labe.felk.cvut.cz)

(Klíčová slova: OPTIMALIZACE, EVOLUČNÍ ALGORITMY, EMPIRICKÉ FUNKCE, REGRESNÍ MODELY, ROZHODOVACÍ STROMY)

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, objevování nejzajímvějších znalostí v dostupných datech, či další typy optimalizačních úloh, při nichž lze hodnoty cílové funkce získat pouze empiricky. Protože evoluční algoritmy používají pouze funkční hodnoty cílové funkce, blíží s k jejímu optimu mnohem pomaleji než optimalizační metody pro hladké funkce, které využívají rovněž informace o gradientu cílové funkce, případně i o jejích druhých derivacích. Tato vlastnost evolučních algoritmů je zvláště nevýhodná v kontextu nákladného a časově náročného empirického způsobu získávání hodnot cílové funkce. Evoluční algoritmy však lze podstatně urychlit, jestliže při vyhodnocování funkčních hodnot cílové funkce používají empirickou cílovou funkci jen občas, zatímco většinou vyhodnocují pouze dostatečně přesný regresní model této funkce. Jednoduchý, ale často používaný typ regresních modelů je založený na rozhodovacích stromech. Tyto regresní modely, tzv. regresní stromy, jsou po částech konstantní a lze je snadno zobecnit na složitější modely. Výzkum využitelnosti regresních stromů a jejich zobecnění k urychlení evoluční optimalizace empirických funkcí je však teprve na samém počátku. Přispět by k němu měla i navrhovaná diplomová práce.
Instruction:Student se nejdříve důkladně seznámí s regresními stromy a jejich zobecněními a také s principy optimalizace pomocí evolučních algoritmů. Bude přitom věnovat pozornost i urychlení evoluční optimalizace empirických funkcí pomocí regresního modelu cílové funkce. S využitím prostudované literatury navrhne algoritmy využití regresních stromů a jejich zobecnění k tomuto účelu. Algoritmy dovede až do podoby prototypové implementace ve vývojovém prostředí Matlab a porovná je na několika testovacích funkcích pro evoluční algoritmy, jakož i na alespoň jedné databázi hodnot empirické cílové funkce z reálné aplikace, kterou dostane od vedoucího práce.
Bibliography:•L. Breiman, J. Friedman, R.A. Ohlsen, C.J. Stone, Classification and Regression Trees. Wadsworth, 1984.
•T. Hastie, R. Tibishirani, J. Friedman. The Elements of Statistical Learning, kapitoly 1–3, 7–10. Berlin, Springer, 2001.
•H. Ulmer, F. Streichert, A. Zell, Model assisted evolution strategies. In Knowledge Incorporation in Evolutionary Computation. Berlin, Springer, 2005, 333–355.
•Z.Z. Zhou, Y.S. Ong, P.B. Nair, A.J. Keane, K.Y. Lum, Combining global and local surrogate models to accellerate evolutionary optimization. IEEE Transactions on Systems, Man and Cybernetics. Part C: Applications and Reviews, 37 (2007) 66–76.
Date:16.10.2009
Responsible person: Petr Pošík