Model-based evolutionary optimization methods

Abstract

Statistické modely se používají pro urychlení optimalizace jak v akademické sféře, tak v průmyslu. Právě v reálných aplikacích, kde je optimalizovaná funkce často finančně nebo časově náročná, mohou statistické modely ušetřit zdroje nebo urychlit optimalizaci. Každá ze tří částí dizertační práce se zabývá jedním takovým modelem: v první části práce nahrazují kopule grafické modely v algoritmech odhadující distribuci, RBF sítě slouží jako náhradní model v genetických algoritmech pro kombinaci spojitých a diskrétních proměnných ve druhé části a třetí část práce používá gaussovské procesy jednak jako model pro vzorkování v bayesovských optimalizačních algoritmech, jednak jako náhradní model v evoluční strategii adaptující kovarianční matici (CMA-ES). Poslední kombinaci, která je popsána klíčové části práce, využívá navržený algoritmus DTS-CMA-ES---dvojitě trénovaný CMA-ES s náhradním modelem. Tento algoritmus využívá nejistotu predikovanou gaussovským procesem, aby vybral část populace CMA-ES k ohodnocení drahou originální funkcí, zatímco zbytek populace je ohodnocen modelem---predikovanou nejpravděpodobnější hodnotou. Výsledky ukázaly, že DTS-CMA-ES konverguje na několika syntetických funkcích rychleji než současné spojité optimalizační algoritmy s náhradním modelem.

Model-based black-box optimization is a topic that has been intensively studied both in academia and industry. Especially real-world optimization tasks are often characterized by expensive or time-demanding objective functions for which statistical models can save resources or speed-up the optimization. Each of three parts of the thesis concerns one such model: first, copulas are used instead of a graphical model in estimation of distribution algorithms, second, RBF networks serve as surrogate models in mixed-variable genetic algorithms, and third, Gaussian processes are employed in Bayesian optimization algorithms as a sampling model and in the Covariance matrix adaptation Evolutionary strategy (CMA-ES) as a surrogate model. The last combination, described in the core part of the thesis, resulted in the Doubly trained surrogate CMA-ES (DTS-CMA-ES). This algorithm uses the uncertainty prediction of a Gaussian process for selecting only a part of the CMA-ES population for evaluation with the expensive objective function while the mean prediction is used for the rest. The DTS-CMA-ES improves upon the state-of-the-art surrogate continuous optimizers in several benchmark tests.