Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
Urychlení evolučních algoritmů pomocí rozhodovacích stromů a jejich zobecnění
Thesis title in Czech: Urychlení evolučních algoritmů pomocí rozhodovacích stromů a jejich zobecnění
Thesis title in English: Accelerating evolutionary algorithms by decision trees and their generalizations
Key words: evoluční optimalizace, regresní stromy, regresní lesy, náhradní modelování
English key words: evolutionary optimization, regression trees, tree ensembles, surrogate modelling
Academic year of topic announcement: 2009/2010
Thesis type: diploma thesis
Thesis language: čeština
Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Supervisor: prof. RNDr. Ing. Martin Holeňa, CSc.
Author: hidden - assigned and confirmed by the Study Dept.
Date of registration: 05.10.2009
Date of assignment: 05.10.2009
Date and time of defence: 05.09.2011 10:00
Date of electronic submission:02.08.2011
Date of submission of printed version:05.08.2011
Date of proceeded defence: 05.09.2011
Opponents: Mgr. David Hauzar, Ph.D.
 
 
 
Guidelines
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.

References
viz http://www.cs.cas.cz/~martin/diplomka38.html
Preliminary scope of work
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.
Preliminary scope of work in English
Evolutionary algorithms are, in the last 20 years, one of the most successful methods for solving non-traditional optimization problems, such as search for the most suitable documents containing required information, discovery of the most interesting knowledge in available data, or other kinds of optimization tasks in which the values of the objective function can be obtained only empirically. Because evolutionary algorithms employ only function values of the objective function, they approach its optimum much more slowly than optimization methods for smooth functions, which make use of information about the objective function gradients as well, possibly also about its second derivatives. This property of evolutionary algorithms is particularly disadvantageous in the context of costly and time-consuming empirical way of obtaining values of the objective function. However, evolutionary algorithms can be substantially speeded up if they employ the empirical objective function only sometimes when evaluating objective function values, whereas they mostly evaluate only a sufficiently accurate regression model of that function. A simple but freequently encountered kind of regression models is based on decision trees. These regression models, referred to as regression trees, are piecewise-constant and can be easily generalized to more complicated models. Investigation into utilizability of regression trees and their generalizations for speeding up evolutionary optimization of empirical functions is, however, only at its very beginning. It should be contributed also by the proposed master thesis.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html