Detail of the student project

List
Topic:Urychlení evolučních algoritmů pomocí neparametrické regrese
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, NEPARAMETRICKÁ REGRESE)

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. Většina regresních modelů je vybírána z rodin funkcí parametrizovaných konečným počtem předem daných parametrů, např. lineární regrese, polynomiální regrese, regrese založená na jádrových funkcích nebo na některých typech umělých neuronových sítí. Díky růstu výkonnosti počítačů však v posledních dvou desetiletích získaly značný význam i modely neparametrické. Ty jsou výpočetně náročnější, ale také flexibilnější a díky tomu univerzálnější. Jejich nejtradičnějším často používaným zástupcem jsou zobecěné aditivní modely. Výzkum využitelnosti neparametrických regresních modelů 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 neparametrickými regresními modely 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 optimalizované funkce. S využitím prostudované literatury analyzuje možnosti použití některých typů neparametrických regresních modelů k tomuto účelu. Několik nejslibnějších z nich rozpracuje až do implementovatelné podoby a zahrne je do prototypové implementace. Na závěr porovná implementovaná řešení na několika testovacích funkcích pro evoluční algoritmy, jakož i na alespoň jedné databázi hodnot empirické optimalizované funkce z reálné aplikace, kterou dostane od vedoucího práce.
Bibliography:•L. Györfi, M. Kohler, A. Krzyzak, H. Walk, A Distribution-Free Theory of Nonparametric Regression. Berlin, Springer, 2002.
•T. J. Hastie, R. J.Tibshirani, Generalized Additive Models. Boca Raton, Chapman & Hall, 1990.
•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