Black-box optimization of mixed discrete-continuous optimization problems
Loading...
Date
2016
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In numerous applications in industry it is becoming standard practice to study complex, real-world processes with the help of computer experiments - simulations. With increasing computing capabilities it has become customary to perform simulation studies beforehand, where the desired process characteristics can be optimized. Computer experiments which have only continuous inputs have been studied and applied with great success in the past in a large variety of different fields. However, many experiments in practice have mixed quantitative and qualitative inputs. Such mixed-input experiments have only recently begun to receive more attention, but the field of research is still very new.
Computer experiments very often take a long time to run, ranging from hours to days, making it impossible to perform direct optimization on the computer code. Instead, the simulator can be considered as a black-box function and a (meta-)model, which is cheaper to evaluate, is used to interpolate the simulation. In this thesis we develop models and optimization methods for experiments, which have purely continuous outputs, as well as for experiments with mixed qualitative-quantitative inputs.
The optimization of expensive to evaluate black-box functions is often performed with the help of model-based sequential strategies. A popular choice is the efficient global optimization (EGO) algorithm, which is based on the prominent Kriging metamodel and the expected improvement (EI) search criterion. Kriging allows for a great flexibility and can be used to approximate highly non-linear functions. It also provides a local uncertainty estimator at unknown locations, which, together with the EI criterion, can be used to guide the EGO algorithm to less explored regions of the search space. EGO based strategies have been successfully applied in numerous simulation studies. However, there are a few drawbacks of the EGO algorithm – for example both the Kriging model and the EI criterion operate under the normality assumption, and the classical Kriging model assumes stationarity – both of these assumptions are fairly restrictive and can lead to a substantial loss of inaccuracy, when they are violated. One further drawback of EGO is its inability to make adequate use of parallel computing. Moreover, the classical version of the EGO algorithm is only suitable for use in computer experiments with purely continuous inputs. The Kriging model uses the Euclidean distances in order to interpolate the unknown black-box function – making interpolation of mixed-input functions difficult.
In this work we address all of the drawbacks of the classical Kriging model and the powerful EGO described in the previous paragraph. We develop an assumption robust version of the EGO algorithm – called keiEGO, which does not rely on the Kriging model and the EI criterion. Instead, the robust alternatives – the kernel interpolation (KI) metamodel and the statistical lower bound (SLB) criterion are implemented. The KI and the SLB criterion are less sophisticated than Kriging and the EI criterion, but they are completely free of the normality and stationarity assumptions. The keiEGO algorithm is compared to the classical Kriging model based on a few synthetic function examples and also on a simulation case study of a sheet metal forming process developed by the IUL institute of the TU Dortmund University in the course of the collaborative research center 708. Furthermore, we develop a method for parallel optimization – called ParOF, based on a technique from the field of sensitivity analysis, called FANOVA graph. This method makes possible the use of parallel computations in the optimization with EGO but also manages to achieve a dimensionality reduction of the original problem. This makes modeling and optimization much easier, because of the (reverse) curse of dimensionality. The ParOF algorithm is also compared to the classical EGO algorithm based on synthetic functions and also on the same sheet metal forming case study mentioned before. The last part of this thesis is dedicated to EGO-like optimization of experiments with mixed inputs – thus we are addressing the last issue mentioned in the previous paragraph. We start by assessing different state of the art metamodels suitable for modeling and predicting mixed inputs. We then present a new class of Kriging models capable of modeling mixed inputs – called the Gower Kriging and developed in the course of this work. The Gower Kriging is also distance-based – it uses the Gower similarity measure, which constitutes a viable distance on the space of mixed quantitative-qualitative elements. With the help of the Gower Kriging we are able to produce a generalized EGO algorithm capable of optimization in this mixed space. We then perform a small benchmarking study, based on several synthetic examples of mixed-input functions of variable complexity. In this benchmark study we compare the Gower-Kriging-based EGO method to EGO variations implemented with other state of the art models for mixed data, based on their optimization capabilities.
Description
Table of contents
Keywords
Kriging, EGO, Diskrete Optimierung, Simulationen