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ímavě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 zobecně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 navržená diplomová práce.
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.
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.
Most of the regression models are selected from families
of functions parametrized with a finite number of
parameters given in advance, e.g., linear regression, polynomial regression, regression based on kernel functions or on some kinds of
neural networks. Due to increasing power of computers,
however, also non-parametric models have been gaining
importance during the last two decades.
They are computationally
more demanding, but also
more flexible, and therefore
more universal. Their most traditional
frequently employed representative are generalized additive models. Investigation into utilizability of non-parametric regression models 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.
· L. Györfi, M. Kohler, A. Krzyzak, H. Walk, A Distribution-Free
Theory of Nonparametric Regression. Springer, 2002.
· D.R. Jones. A taxonomy of
global optimization methods based on response surfaces. Journal of Global Optimization,
21: 345-383, 2001.
·
R.H. Myers, D.C. Montgomery, C.M. Anderson-Cook.
Response Surface
Methodology: Proces and Product
Optimization Using Designed Experiment. John Wiley
and Sons, 2009.
·
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, 37:
66-76, 2007.