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 informací
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
pracují pouze s funkčními hodnotami optimalizované funkce, blíží
s k jejímu optimu podstatně pomaleji než optimalizační metody pro hladké
funkce, které využívají rovněž informace o gradientu optimalizované funkce,
případně o jejích druhých derivacích. Tato vlastnost evolučních algoritmů je
zvláště nepříjemná ve spojení se skutečností, že empirické získání hodnoty
optimalizované funkce bývá obvykle značně nákladné i časově náročné. Evoluční
algoritmy však lze podstatně urychlit tím, že při vyhodnocování funkční hodnoty
optimalizované funkce používají empirickou optimalizovanou funkci jen občas,
zatímco většinou vyhodnocují pouze její dostatečně přesný regresní model.
K nejslibnějším regresním modelům patří modely založené na gaussovských procesech. Není proto divu, že právě ony byly
mezi prvními, které se pro urychlení evoluční optimalizace začaly používat.
Přesto je výzkum urychlování evolučních algoritmů pomocí gaussovských
procesů teprve v začátcích. Příspěvkem k němu by měla být i navržená
diplomová práce.
Student
se nejdříve důkladně seznámí s gaussovskými
procesy 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. Dosud publikované přístupy k urychlení
evolučních algoritmů pomocí gaussovských procesů
implementuje ve vývojovém prostředí Matlab. Na
základě prostudované literatury i testování implementovaných přístupů navrhne
jejich možná zdokonalení či modifikace. Některé z nich také implementuje a
porovná je s původními přístupy 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
sped 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.
To most promising regression
models belong those based on Gaussian processes. Therefore, it is
not surprising that these models were among
the first that started to be used for
accelerating evolutionary optimization. Nevertheless, research into accelerating
evolutionary algorithms by means of Gaussian
processes is only at a beginning.
It should be contributed also by the proposed
master thesis.
·
L. Bajer, Z.
Pitra, J. Repický, M. Holeňa. Gaussian
process surrogate models for the
CMA evolution strategy. Evolutionary Computation, 27:665-697, 2019.
·
N. Hansen. The CMA Evolution Strategy: A Comparing
Review. In: Towards a New Evolutionary Computation, 2006, 75−102.
·
Z. Pitra, J.
Repický, M. Holeňa. Landscape analysis of gaussian
process surrogates for the covariance matrix adaptation evolution strategy.
In: GECCO’19, 2019, 691−699.
·
E. Rasmussen, C. Williams. Gaussian Processes for Machine Learning.
MIT Press, 2006, kapitoly 1, 2, 4.
·
A.G. Wilson, R.P. Adams. Gaussian Process Kernels for Pattern Discovery
and Extrapolation. In ICML’13, 2013, 1067−1075.