Model-based Methods for Continuous and Discrete Global Optimization

CIplus Band 8/2016 Model-based Methods for Continuous and Discrete Global Optimization Thomas Bartz-Beielstein, Martin Zaefferer Model-based Methods for Continuous and Discrete Global OptimizationI Thomas Bartz-Beielstein∗, Martin Zaefferer TH K¨oln, Faculty of Computer Science and Engineering Science, Steinm¨ullerallee 1, 51643 Gummersbach, Germany Abstract The use of surrogate models is a standard method to deal with complex, realworld optimization problems. The first surrogate models were applied to continuous optimization problems. In recent years, surrogate models gained importance for discrete optimization problems. This article, which consists of three parts, takes care of this development. The first part presents a survey of modelbased methods, focusing on continuous optimization. It introduces a taxonomy, which is useful as a guideline for selecting adequate model-based optimization tools. The second part provides details for the case of discrete optimization problems. Here, six strategies for dealing with discrete data structures are introduced. A new approach for combining surrogate information via stacking is proposed in the third part. The implementation of this approach will be available in the open source R package SPOT2. The article concludes with a discussion of recent developments and challenges in both application domains. Keywords: Surrogate, Discrete Optimization, Combinatorial Optimization, Metamodels, Machine learning, Expensive optimization problems, Model management, Evolutionary computation IThis is an extended version of the contribution [1] ∗Corresponding author. Phone: +49 2261 8196 6391 Email addresses: [email protected] (Thomas Bartz-Beielstein), [email protected] (Martin Zaefferer) Preprint submitted to Applied Soft Computing November 13, 2016 1. Introduction Model-based optimization (MBO) plays a prominent role in today’s modeling, simulation, and optimization processes. It can be considered as the most efficient technique for expensive and time-demanding real-world optimization problems. Evaluating a cheaper surrogate model instead of the expensive objective func-5 tion may significantly reduce time, space, and computing costs. Especially in the engineering domain, MBO is an important practice. Recent advances in computer science, statistics, and engineering in combination with progress in high-performance computing provide tools for handling problems, which were considered unsolvable only a few decades ago.10 The first part of this article presents a survey of MBO for continuous and discrete global optimization problems. Our goal is to show connections and conceptual differences between these two domains and to discuss properties of state-of-the art MBO algorithms. Despite its growing relevance, contributions to the discrete domain have been largely disregarded and were listed as open15 challenges. For example, Simpson et al. [2] present an interesting history of development in the field. Another survey of metamodeling techniques, which focuses on the practitioners perspective, is given by Wang and Shan [3]. Both of these surveys mention problems from the discrete domain, but do not discuss them in depth.20 The term global optimization (GO) will be used for algorithms and problems where the goal is to find and explore global optimal solutions with complex, multimodal objective functions [4]. Furthermore, we will focus on GO problems which belong to the class of difficult (expensive) black-box functions, i.e., functions for which the analytic form is unknown. Thus, nearly no structural25 information (e.g., number of local extrema, derivate information) is available. This setting arises in many real-world systems when the explicit form of the objective function fis not readily available, e.g., if the user has no access to the source code of a simulator. Surrogates are a popular choice, because the time required for building the surrogate is negligible compared to the evaluation of30 2 the real-world function f. The remainder of this article is structured as follows. Section 2 introduces a taxonomy of search algorithms and presents basic definitions. After introducing instance-based stochastic search algorithms, Section 3 describes modeling approaches for stochastic algorithms. We differentiate between models that use35 a distribution and models that use an explicit surrogate model. Section 4 introduces model-based optimization, which is the first choice for many optimization problems in industry. Problems and algorithms from the discrete, combinatorial domain are then introduced in Section 5. Using two MBO algorithms, namely EvoLS and SPO, recent trends and new developments in MBO are described in40 Section 6. Finally, a summary and an outlook are given in Section 7, including important challenges in continuous and discrete MBO. 2. Taxonomy and Definitions We consider the continuous optimization problem given by Minimize: f(~x) subject to ~a ≤~x ≤~ b, where f:Rn→Ris referred to as the objective function and ~a and ~ bdenote the lower and upper bounds of the search space, respectively. The objective45 function fis assumed to be an expensive-to-evaluate black-box. In the discrete case, ~x ∈Rnis not true anymore. Rather, a candidate solution is some discrete data structure, or object. Typical discrete data structures include, e.g., ordinal integers, categorical variables, binary variables, permutations, strings, trees or graphs in general. In most of these discrete cases, bounds50 ~a and ~ bare also not required anymore. From the algorithmic perspective, this survey focuses on search heuristics, which are mostly implemented using stochastic or random procedures. Deterministic, exact GO algorithms, i.e., algorithms providing theoretical guarantees that the attained solution is the global one within some pre-specified tolerance,55 are not further discussed [5]. The terms “random” and “stochastic” will be used synonymously in the remainder of this article. 3 Global optimization [I] Deterministic [II] Stochastic [II.1] Instance [II.2] Model [II.2.1] Distribution [II.2.2] Surrogate model [II.2.2.2] Multi-fidelity [II.2.2.3] Ensemble surrogate [II.2.2.1] Single surrogate Figure 1: An essential taxonomy of model-based approaches in GO. This taxonomy is applicable for continuous and discrete GO problems. Stochastic search algorithms can further be categorized as instance-based or model-based algorithms [6]. Furthermore, there are basically two modelbased approaches: (a) distribution-based models and (b) surrogate models. We60 consider three important representatives of surrogate model based optimization: (i) Single surrogate based optimization uses one model for accelerating the search process, (ii) multi-fidelity metamodeling uses several models of the same real system and plays an important role in computational fluid dynamics (CFD) and finite element modeling (FEM) based simulation and optimization, and (iii)65 ensemble surrogate based optimization combines two or more different surrogate models. This categorization (or taxonomy) of GO algorithms is summarized in Figure 1. Typical situations, which may occur in MBO, are illustrated in Figure 2. 4 Real process CFD model Real process Optimization Optimization Real process CFD model Optimization Kriging model Real process CFD model Optimization Coarse grained CFD model Real process Kriging model Optimization A B C D E Figure 2: Surrogate model based optimization. Dotted lines denote the data flow, which is used for the model building. Solid lines represent the optimization loop. Situation A illustrates an optimization loop without any model. In situation B, a CFD model is used to accelerate the evaluation of the complex real-world function. Kriging is used as a surrogate to accelerate this evaluation in situation C. In addition to a fine grained CFD model, a coarse grained model is used in the multi-fidelity approach (situation D). Models can be stacked as shown in situation E, where a Kriging model (surrogate) is used to accelerate the CFD simulations. Kriging is a frequently employed type of surrogate model [7]. Figure 2 shows70 (in situation C) that the Kriging model can be constructed as a surrogate model of a complex real-world process. Furthermore, a Kriging model can be used as a surrogate model of the relatively complex CFD simulation model (as illustrated in situation E). Some authors define a model as a direct abstraction of realworld processes and a surrogate as a second abstraction, which highlights the75 properties of the model itself. Following these definitions, the Kriging model in situation C is a model, whereas the Kriging model in situation E is a surrogate. As this has the potential of confusion, we will not use this categorization. Instead, we will use the term “model” for a simplified abstraction of a complex object, whereas the term “surrogate” will be used for the subset of models,80 which can be represented by an explicit functional relationship [8, 9]. Usually, a data-driven process, which comprehends the following two steps, is used for constructing a surrogate: (i) generation of data through sampling and (ii) mathematical function fitting. The terms “surrogate”, “surrogate model”, and 5 “metamodel” will be used synonymously in the following.85 3. Stochastic Search Algorithms An iterative search algorithm that uses a stochastic procedure to generate the next iterate is referred to as a stochastic search algorithm. The next iterate can be a candidate solution to the GO or a probabilistic model, where solutions can be drawn from. Stochastic search algorithms are considered robust and easy90 to implement, because they do not depend on any structural information of the objective function, such as gradient information or convexity. This feature is one of the main reasons for the popularity of stochastic search in the domain of GO. Instance-based algorithms ([II.1]) maintain a single solution,~x, or popula-95 tion,P(t), of candidate solutions. The iteration or time step is denoted as t. The construction of new candidate solutions depends explicitly on the previously generated solutions. Simulated annealing [10], evolutionary algorithms (EAs) [11, 12], and tabu search [13] are prominent representatives of this category. The key elements of instance-based algorithms are shown in Algorithm 1.100 This pseudo code focuses on the fundamental structure of the algorithm and skips some implementation details, e.g., P(t) represents the population at time step tand the corresponding function values. Algorithm 1 Instance-based algorithm 1: t= 0. P(t) = SetInitialPopulation(). 2: Evaluate(P(t)) on f. 3: while not TerminationCriterion() do 4: Generate new solutions P0(t) according to random mechanism. 5: Evaluate(P0(t)) on f. 6: Select the next population P(t+ 1) from P(t)∪P0(t). 7: t=t+ 1. 8: end while 6 4. MBO: Model-based Algorithms Model-based optimization algorithms ([II.2]) generate a population of new105 candidate solutions P0(t) by exploiting a model (surrogate or distribution). The model reflects structural properties of the underlying true function f. Modelbased optimization algorithms are based on the idea that by adapting the model, the search is directed into regions with improved solutions. One of the key ideas in MBO is the replacement of expensive, high fidelity,110 fine grained function evaluations, f(~x), with evaluations, ˆ f(~x), of an adequate cheap, low fidelity, coarse grained model, M. An additional benefit can seen in the smoothening property of the cheap model, because it uses an approximation of the possibly noisy data [2]. This section describes two different MBO approaches: (i) distribution based115 ([II.2.1]) and (ii) surrogate-model based optimization ([II.2.2.]). 4.1. Distribution-based Approaches If the metamodel is a distribution, the most basic form of an MBO can be implemented as shown in Algorithm 2: Algorithm 2 Distribution-based algorithm 1: t= 0. Let p(t) be a probability distribution. 2: while not TerminationCriterion() do 3: Randomly generate a population of candidate solutions P(t) from p(t). 4: Evaluate(P(t)) on f. 5: Generate updated distribution p(t+ 1) with population (samples) P(t). 6: t=t+ 1. 7: end while Distribution-based algorithms generate a sequence of iterates (probability distributions) {p(t)}with the hope that p(t)→p∗as t→ ∞, 7 ally, surrogate models are assessed and chosen according to their estimated true error [54, 55, 2]. Generally, attaining a surrogate model that has minimal error is290 the desired feature. The mean absolute error (L1 norm), the mean square error (MSE) (or its pendant the root mean square error (RMSE)) are commonly used as performance metrics. Methods from statistics, statistical learning [56], and machine learning [57], such as the simple holdout approach, cross-validation, and the bootstrap are also important in this context.295 Several selection and combination mechanisms for surrogates were developed in the last years. A simple approach determines the best model, i.e., the model with the smallest prediction error, and determines the next candidate solution based on that model. Alternatively, candidate solutions from several models can be combined. Zerpa et al. [58] use multiple surrogate models and build an300 adaptive weighted average model of the individual surrogates. Goel at al. [59] explore the possibility of using the best surrogate model or a weighted average surrogate model instead of one single model. Model quality, i.e., the errors in surrogates, is used to determine the weights assigned to each model. Sanchez et al. [60] present a weighted-sum approach for the selection of model ensembles.305 The models for the ensemble are chosen based on their performance and the weights are adaptive and inversely proportional to the local modeling errors. Tenne and Armfield [61] propose a surrogate-assisted memetic algorithm which generates accurate surrogates using multiple cross-validation tests. Huang et al. [62] use several simulation models for a semiconductor manu-310 facturing system. They propose an ordinal transformation to utilize the results from several cheap models. The function values of all solution candidates is evaluated on every cheap model and the individuals are ranked. The authors observe that despite the big bias in the results from the cheap models, the relative order among solutions is actually quite accurate. This order can be used315 to accelerate the selection process in EAs significantly. To reduce variability and bias in the results from the cheap models, the authors apply an optimal computing budget allocation scheme. Multiple models can also be used to partition the search space. The treed 14 Gaussian process approach uses regression trees to partition the search space320 into separate regions and to fit local GP surrogates in each region [63]. Nelson et al. [64] propose an algorithm, which creates a tree-based partitioning of an aerodynamic design space and employs independent Kriging surfaces in each partition. Couckuyt et al. [65] propose to combine an evolutionary model selection (EMS) algorithm with the EI criterion in order to dynamically select the325 best performing surrogate model type at each iteration of the EI algorithm. 5. Surrogate Models in Discrete Optimization Compared to their frequent use for real-valued problem domains, surrogate model driven approaches are relatively scarce in combinatorial or mixed optimization [28]. Discrete problems deal, e.g., with ordinal integers, categorical330 (qualitative) variables, permutations, strings, trees, or other graph based data structures. They may be mixed among themselves, or mixed with continuous variables. Ordinal integer variables can often be handled quite similarly to real valued variables. Others, like trees, are too complex to be easily represented by numeric vectors.335 Few expensive, real-world combinatorial optimization problems have been published, e.g., in the engineering domain [66, 67, 68, 69], bioinformatics [70], or data science [71]. Not all of them make use of surrogate models. This scarcity is unlikely due to a lack of problems in this field. Rather, the availability of suitable methods (i.e., surrogate models, category [II.2.2]) is not well known or these340 methods are not easily accessible to experts in potential application domains. Thus, we provide a survey of surrogate modeling methods for combinatorial, discrete problems. The general taxonomy for these methods is the same as for the continuous case, which was illustrated in Figure 1. 5.1. Strategies for Dealing with Discrete Structures345 Table 1 presents a tabulated overview of the literature on discrete, surrogate model-based optimization. This overview presents important stepping stones 15 Table 1: Overview of surrogate models in combinatorial optimization. Column data lists data type: Mixed (mix), ordinal (ord), categorical (cat), binary (bin), permutation (per), signed permutation (-per), trees (tre), other (oth). Column slists the strategy, see Section 5.1. Column dim lists the dimensionality of the problem, where applicable. Abbreviations introduced in the table: genetic algorithm (GA), non-dominated sorting genetic algorithm II (NSGA2), simulated annealing (SA), artificial neural networks (ANN), ant colony optimization (ACO), multi-start local search (MLS). This table is continued on page 17. data STR model optimizer cost budget dim topics ref. mix, cat, ord 1,3 Kriging, Tree visual, statistical analysis high ≤100 2, 9 parameter tuning [72] mix, ord, cat 6 RBFN ES low / ∼high 560 / 280 15 / 23 benchmark, medical image analysis [73] mix, ord, cat 3,6 Random Forest, Kriging MLS ∼high - 4-76 algorithm tuning [74] mix bin, cat 6RBFN + cluster GA low 2,000 12 benchmark, chemical industry [75] mix, ord, cat 4 SVM NSGA2 ? 2,000 10 FEM, multi criteria [76] and interesting applications in the field, thus showcasing the development. For a more extensive table we refer to the tabular overview in the supplemental material of this article1. In Table 1, the employed modeling strategies, model types,350 optimizers, and problem-related details are specified. The table lists works on (mixed) integer problems, binary representations, permutation problems, tree structures, and other representations. To deal with modeling in combinatorial search spaces, a set of six strategies (STR) can be identified in the literature, which are referenced in column “STR”355 of Table 1: 1The tabular overview will be kept up-to-date on the second author’s home page https: //martinzaefferer.de/?page_id=134 16 Table 1: continued data STR model optimizer cost budget dim. topics ref. bin 1/3 ANN SA high ? 16 real world, pump positioning [77] bin 6 RBFN GA low dim210–25 NK-Landscape [78] -per 2 custom brute force high 28 6 real world: weld sequence [66] per 6 RBFN GA low 100 30–32 benchmark [79] per 6 Kriging GA low 100 12–32 benchmark [80] per 6 Kriging ACO low 100 - 1,000 50–100 benchmark, tuning [81] tre 6 RBFN GA low 100 symbolic regression [82] tre 5,6 k-NN GA high 30,000 phenotypic similarity, genetic programming [83] tre 5 Random Forest GA low 15,000 benchmark, genetic programming [84] STR-1 The naive approach: As long as the data can still be represented as a vector (binary variables, integers, categorical data, permutations) the modeling technique may simply ignore the discrete structure, and work as usual. A potential drawback of this approach is, that the model’s360 input space may have large areas of redundancy. Or else, this approach may create large areas of infeasible solutions. Depending on the optimizer, this may deteriorate performance compared to more sophisticated approaches. STR-2 Custom modeling: A specific modeling solution is tailored to fit the365 needs of a certain application. On the one hand, this procedure can be very efficient, because it integrates significant prior knowledge into the model. On the other hand, it may introduce bias and may be hard to transfer to other applications or data structures. This approach is not applicable for true black-box problems.370 17 STR-3 Inherently discrete models: Some models already are discrete in their own design. One example are tree-based models, like regression trees or random forests. On the one hand, these models are easy to use, because no or only minor adaptations are necessary. On the other hand, this strategy may fail if the discrete structures become more complex375 (e.g., trees or other graph structures). Also, such models may not always provide desired features, e.g., the nice properties derived from the uncertainty estimates of a Kriging model. STR-4 Mapping: Often, discrete variables or structures may be mapped to a more easily handleable representation. Examples for this approach380 are the random key mapping for permutations or dummy variables for categorical variables. Similarly to strategy STR-1, this approach may introduce redundancy or infeasibility into the data structure. Establishing reasonable mappings becomes harder for data structures with increasing complexities.385 STR-5 Feature extraction: Instead of directly modeling the relation between an object (or its representation) and its quality, it is possible to calculate real-valued features of the objects. For example, some features of a tree or graph can be extracted (path lengths, tree depths, etc.). These numeric features can then be modeled with standard techniques.390 STR-6 Similarity-based modeling: Where available, measures of (dis)similarity may be used to replace continuous measures that are, e.g., employed in similarity-based models like k-nearest neighbor (k-NN), support vector machines (SVM), radial basis function networks (RBFN), or Kriging. While this approach is potentially very powerful, a drawback is395 the requirement of proper measures. This may be problematic if these measures have to fulfill further requirements, like definiteness. The presented six strategies are not necessarily mutually exclusive. Depending on the point of view, a mapping approach can be interpreted as similarity18 based approach, or vice versa. Or else, features may be extracted and used for400 modeling, while at the same time applying some inherently discrete approach to the data. Thus, some methods may either combine several strategies, or else, can be classified as belonging to several strategies. None of the six strategies can be broadly preferred to the others. Even the naive approach may be adequate, if the problem is sufficiently simple. Problem405 type and application restrictions will govern the selection of a suitable approach. The subsequent sections present key characteristics of strategies considered by the authors to be most relevant. 5.2. Custom Models One way of using surrogate-models for combinatorial problems is to employ410 customized, application specific solutions (STR-2). An example is the work by Voutchkov et al. [66]. They optimize a weld sequence, which is represented as a signed permutation, and find a near-optimal welding sequence by evaluating only 28 out of 46,080 possible sequences. The surrogate model replaces an expensive FEM by estimating the influence of each individual element in the415 weld sequence, based on the observations made in previously tested sequences. In addition to the function values, the surrogate also exploits intermediate results that reflect the impact of individual sequence-elements, depending on their position in the weld sequence. Exploiting these intermediate results is a clear advantage over more simple, function-value driven approaches. On the other420 hand, the applicability of this model is restricted to this specific setup and cannot be easily transferred to completely different application areas. The surrogate modeling approach in [66] has since been adapted and applied to a girth weld path optimization problem by Asadi and Goldak [67]. Due to the nature of their problem (number of weld sub-passes, rotational symmetry) only 48 se-425 quences are possible. They evaluated 15 of these 48 sequences to find an optimal solution. Nguyen et al. [85] propose to use simplifications of the target function (a simulation model for job shop scheduling) as a surrogate model in genetic programming. These applications show that custom models are beneficial, if 19 domain knowledge is available.430 5.3. Mapping As stated in Section 5.1, a frequently chosen approach is mapping from the more complex, discrete space to another more easy to handle space (STR-4). Classical regression provides an establishes mapping approach for dealing with discrete, categorical parameters, which is based on dummy variables and con-435 trasts. A categorical variable can be mapped to a set of dummy variables, where each dummy represents a single level of the original variable. This is the same as the one-hot encoding, i.e., only one of several bits can be 1. The nlevels of the categorical variable are mapped to nbinary variables. The binary variables are still discrete, but can be handled by standard regression approaches. Else, one440 can map to (n−1) binaries: The one missing level is represented by all dummy variables being zero. This is essentially a contrast. Contrast variables represent a comparison between different levels. Clearly, both approaches increase the number of model parameters. Dummy variables or contrasts are probably among the most frequently applied methods to deal with categorical variables,445 e.g., in the context of the response surface methodology [86]. Another example of a mapping approach is the random key mapping developed by Bean [87]. Random keys are vectors of real numbers from a fixed interval, e.g., the interval [0,1]. To map from this real parameter space to permutation representations, the random key values are simply sorted. Random450 keys were originally developed to enable the application of continuous, modelfree genetic algorithms to permutation problems. They have since been used in probabilistic models which are part of EDAs, see also Section 4.1 and 5.6. Notable drawbacks are redundancy in the real valued parameter space as well as the non-bijection character of the mapping.455 5.4. Feature Extraction Of the few approaches that deal with modeling for tree-representations (symbolic regression, genetic programming), many use feature extraction for modeling. Hildebrandt and Branke [83] extract features of the phenotypic behavior 20 of evolved dispatching rules for job shop scheduling. Here, these features are460 based on the rule decisions for a small set of reference situations. The Euclidean distance is computed on these features and is then employed in a k-NN surrogate model. From a different point of view, this process can as well be seen as a part of the (dis-)similarity calculation, and hence part of strategy STR-6, rather than STR-5. Hildebrandt and Branke compare the phenotypic approach465 to a genotypic distance measure: the structural Hamming distance. The phenotypic feature extraction approach has since also been investigated by Nguyen et al. [88], who improved handling of replications and the selection scheme. Pilat and Neruda [84] take a slightly different approach. They extract features from the genotype of candidate solutions, e.g., the depth of the tree,470 summarizing statistics of numeric constants in the tree, or the cardinality of certain arguments in the tree. Some of these recent approaches use a rather simple surrogate model, i.e., k-NN [83, 88]. This is tightly linked to the comparatively high evaluation budgets (tens of thousands). More complex models might become too expensive475 when data-sizes grow to these dimensions. On the other hand, using such large budgets may be necessary due to the extremely large search spaces that genetic programming is typically dealing with. Compared to the more common, modelfree genetic programming approaches, few tens of thousands of evaluations are in fact a small budget.480 5.5. (Dis)similarity based models A promising approach that recently gained more traction is similarity-based modeling (STR-6). Fonseca et al. [89] defined similarity-based models as models that keep a memory of solutions and estimate the performance of new samples by comparing them to that memory. Fonseca et al. list fitness inheritance [90],485 fitness imitation [91, 27] and k-NN [92] as examples. They test a genetic algorithm supported by a k-NN model on a set of numerical, continuous test functions. Bernardino et al. [93] perform similar tests with artificial immune systems. In both cases Hamming and Euclidean distances are used as mea21 sures of dissimilarity, showing that this approach does not depend on a specific490 measure. However, the k-NN model is not able to predict whether or not a candidate solution will provide improvement over existing solutions. For that purpose, another set of similarity or distance based models is of interest: RBFN, SVM, and Kriging (Gaussian process regression). Hemker [94] describes in his Ph.D.495 thesis an approach to deal with continuous and ordinal integer variables, applied to electrical engineering and water resource management problems. Their approach is based on Kriging, essentially treating all parameters with the same distance function, hence not directly applicable to categorical parameters or more complex representations. Li et al. [73] proposed an adaptation of RBFNs.500 These adaptations are based on a weighted distance measure, replacing the usual distance measure employed in RBFN. Their distance-based RBFN model was tested with mixed integer optimization problems. It has since been applied to a multi objective building design optimization problem by Brownlee and Wright [95]. Mixed optimization problems also arise in algorithm tuning.505 In this context, Hutter [74] also used a Kriging model with a Hamming distance based correlation function to handle categorical variables. A combination of Kriging and tree-based models called treed Gaussian processes has been used by Swiler et al. [96]. They applied a treed Gaussian process model, a Kriging model, and a smoothing spline technique to build surrogate models for mixed510 integer problems. Coelho et al. [97] and Herrera et al. [76] applied a kernelbased regression method to mixed-variable optimization problems. A different approach with RBFs for the case of a mixed (discrete and continuous) optimization problem is taken by Bajer and Holena [75]. Instead of creating one RBFN based on a weighted distance between candidate solutions they use Hamming515 distance to cluster the discrete variables, then fit a standard RBFN with the continuous variables for each cluster. Moraglio and Kattan [78] adapted an RBFN to arbitrary distance measures to model arbitrary combinatorial optimization problems. Their approach has also been applied to quadratic assignment problems [79]. A similar conceptual520 22 extension for Kriging was investigated by Zaefferer et al. [80]. Here, Krigingbased EGO [30] showed positive results when applied to combinatorial problems. Zaefferer et al .[98] also showed that maximum likelihood estimation (MLE) can be used to efficiently choose one measure from a set of distance measures. An investigation by C´aceres et al. [81] reports negative results for the ap-525 plication of EGO to permutation problems. There, an ant colony optimization algorithm was not outperformed by the Kriging-based variant of the same algorithm. Smith et al [71] describe a study on extremely high-dimensional test instances, employing RBFN models. While the employed models showed some promise, a proposed ensemble of models performed poorly.530 The above modeling approaches use distances and kernels in a standard, straight-forward way. However, it is often important to consider if either the employed distances are conditionally negative semi-definite (CNSD) or positive semi-definite (PSD). Definiteness is a frequent requirement for modeling methods based on distances or kernels. Dealing with the possible indefiniteness of a535 function is hence of utmost concern. In fact, lack of definiteness is one possible source of some previously observed numerical problems, e.g., in [80, 98]. A recent study by Zaefferer and Bartz-Beielstein [99] dealt with the issue of definiteness in the context of Kriging based optimization. They transfer and extend methods from the field of SVMs, which were previously used for machine learning with540 structured data, c.f., the survey by Schleif and Tino [100]. While, to the best of our knowledge, SVMs have rarely been used as surrogates in combinatorial optimization, they have been applied to learning problems with combinatorial data (see e.g., [101, 102, 103]). Hence, they are a promising choice. Most of the above references make use of distance measures in genotype545 space. For the case of genetic programming, Hildebrandt and Branke [83] show, that a distance in phenotype space may be an excellent choice, see also the preceding section. 23 Summarizing, the contribution of this article can be described as follows: A comprehensible taxonomy of MBO algorithms for global optimization problems (Figure 1) is proposed. A survey of SBO algorithms, which includes the most recent publications from continuous and the combinatorial problem domains, is given. Six strategies for dealing with modeling in combinatorial search spaces680 are developed. Working principles of two state-of-the-art SBO algorithms were shown: (i) EvoLS, which constructs a local metamodel for every new candidate solution, and (ii) SPOT2, which uses a global ensemble engine to combine a broad variety of surrogate models. The survey presented in the first sections of this article as well as the examples in Section 6 emphasize the trend to685 ensemble based metamodels. Due to the emerging-field nature of SBO, and especially combinatorial SBO, several challenges remain to be solved. This article concludes with a (subjective) selection of the most challenging problems. 7.1. Model Selection The selection of an adequate surrogate plays a crucial role in the SBO pro-690 cess. The surrogate should reflect the underlying complex process as exact as possible and should be as simple as possible. The estimation of the model quality is an open research question. For example, the definition of the corresponding training sets for the holdout or cross-validation approaches represents a critical issue for the accuracy and efficiency of the surrogates. Viana and Haftka [118]695 report that is is beneficial to run EGO with multiple surrogates. Interestingly, they also observe that an improved global accuracy of the surrogate is not necessary for obtaining the best result. The number of potential surrogate model types and selection strategies is huge. The earlier mentioned stacking approach (cf. Section 6.2) can prove to be700 a helpful starting point. Building stacked ensembles of surrogate models may help to understand how different approaches perform, and how they can interact. Besides providing more accurate predictions, stacking may enable researchers to design more promising modeling approaches for complex data structures. Model selection is still a challenging research topic with many open questions,705 30 which is is especially true in the combinatorial domain. There, little guidelines are available, due to the relative scarcity of publications. 7.2. Definiteness In case of similarity-based models (strategy STR-6, see Section 5.5), definiteness is a crucial issue. While first results are available for Kriging models [99],710 some important details require further attention. First, more extensive experiments are of interest. Secondly, more efficient handling of prediction for new data samples would be beneficial for performance in practice. And finally, a theoretical analysis could provide a more sound foundation for the existing approaches.715 7.3. Dimensionality The question of dimensionality, i.e., the number of variables, is an important issue. For continuous problems, it is often stated that distance-based models like Kriging perform poorly for larger dimensional problems. A rough threshold of approximately 20 dimensions is frequently specified for Kriging, e.g., see [7].720 This is closely linked to the specific distance function [130]. For instance, Manhattan distance will be less affected by such issues, compared to Euclidean distance [130]. For the general, discrete case with an arbitrary distance function such knowledge is often not available. At the same time, feature selection or other dimensionality reduction methods may not be instantly available for725 problems with complex, discrete data representations. Thus, further research on dimensionality issues is recommendable. This is especially of interest for high dimensional real-world problems as, e.g., investigated by Smith et al. [71]. Simpson et al. [2] list some recent approaches to tackle this “curse of dimensionality” and problems related to generate adequate surrogates in high-dimensional730 and complex non-linear search spaces. Dimensionality can also be interpreted as the number of samples, which leads to additional challenges. Nowadays, an increasing number of applications generate large data sets. Instead of very expensive and small data sets, huge data sets 31 have to be processed in this situation. Several applications from bioinformatics,735 social media, or climate science rely on the modeling of massive data sets with up to billions of data samples. Recently developed methods rely on special matrix structures (Kronecker or Toeplitz). For example, Wilson et al. [131] present early results for massively scalable Gaussian processes, which enables the use of Gaussian processes on billions of data points. The development of multi-fidelity740 surrogates, which use coarse grained models to obtain similar results as the exact model might be very interesting. Furthermore, methods for data sets that do not satisfy special matrix structures are of great interest. 7.4. Benchmarking An important issue is the set of benchmark or test functions, used to evaluate745 algorithm and modeling performance. Previous approaches try to compose a set of test functions with many different features, e.g., by using step, linear, convex, and sinusoidal functions. A more recent approach [132] uses an infinite number of test problem instances to prevent an over fitting (or better: over learning) of the competing algorithms. The test problems are based on real-world problem750 instances, which are systematically modified. While benchmarking is still not resolved for continuous model-based optimization, the situation is even less settled in the discrete domain. Of the few published, real-world, expensive, combinatorial problems, most are not openly accessible. Even in case of availability, the benchmark set would be rather small755 and the expense of computation would hinder broader experimental studies. Thus, most of the benchmark problems are well known cheap-to-compute problems, e.g., the traveling salesperson problem (see the overview in Table 1). It is questionable whether performances estimated for these problems are actually representative for real-world expensive problems. In fact, the simple problem760 structure may be unable to give proper credit to complex models like Kriging. This may be one reason for results as, e.g., observed by Caceres et al. [81]. 32 7.5. Multiple Objectives Last, but not least, the problems discussed so far for single objective SBO exist also for model-based multi-objective optimization algorithms. The question765 of using global or local models is discussed in several publications, e.g., Isaacs et al. [133] present a local approach, which maintains an external archive, whereas Pilat and Neruda [134] present an approach by aggregating metamodels for evolutionary multiobjective and many-objective optimization. Horn et al. [135] present a taxonomy for model-based multi-objective optimization algorithms,770 which can be recommended as a starting point. Acknowledgements This work has been supported by the Bundesministerium f¨ur Wirtschaft und Energie under the grants KF3145101WM3 and KF3145103WM4. This work is part of a project that has received funding from the European Unions Horizon775 2020 research and innovation program under grant agreement No 692286. References [1] T. Bartz-Beielstein, A Survey of Model-Based Methods for Global Optimization, in: G. Papa, M. Mernik (Eds.), Bioinspired Optimization Methods and their Applications, 2016, pp. 1–18.780 [2] T. Simpson, V. Toropov, V. Balabanov, F. Viana, Design and Analysis of Computer Experiments in Multidisciplinary Design Optimization: A Review of How Far We Have Come - Or Not, in: 12th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, American Institute of Aeronautics and Astronautics, Reston, Virigina, 2012, pp. 1–22.785 doi:10.2514/6.2008-5802. [3] G. G. Wang, S. Shan, Review of Metamodeling Techniques in Support of Engineering Design Optimization, Journal of Mechanical Design 129 (4) (2007) 370–380. doi:10.1115/1.2429697. 33 [4] M. Preuss, Multimodal Optimization by Means of Evolutionary Algo-790 rithms, Natural Computing Series, Springer International Publishing, Cham, 2015. doi:10.1007/978-3-319-07407-8. [5] A. Neumaier, Complete search in continuous global optimization and constraint satisfaction, Acta Numerica 13 (2004) 271–369. [6] M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo, Model-Based Search795 for Combinatorial Optimization: A Critical Survey, Annals of Operations Research 131 (1-4) (2004) 373–395. doi:10.1023/B:ANOR.0000039526. 52305.af. [7] A. Forrester, A. S´obester, A. Keane, Engineering Design via Surrogate Modelling, Wiley, 2008.800 [8] J. P. C. Kleijnen, A comment on blanning’s metamodel for sensitivity analysis: The regression metamodel in simulation, Interfaces 5 (3) (1975) 21–23. [9] O. Garitselov, S. P. Mohanty, E. Kougianos, A comparative study of metamodels for fast and accurate simulation of nano-cmos circuits, IEEE805 Transactions on Semiconductor Manufacturing 25 (1) (2012) 26–36. doi: 10.1109/TSM.2011.2173957. [10] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing, science 220 (4598) (1983) 671–680. doi:10.1126/science. 220.4598.671.810 [11] A. E. Eiben, J. E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, Heidelberg, New York, 2003. [12] T. Bartz-Beielstein, J. Branke, J. Mehnen, O. Mersmann, Evolutionary Algorithms, WIREs Data Mining and Knowledge Discovery 4 (2014) 178– 195.815 34 [13] F. Glover, M. Laguna, Tabu search, in: C. R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Inc., New York, NY, USA, 1993, Ch. Tabu Search, pp. 70–150. [14] P. Larraaga, J. A. Lozano, Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation, Kluwer, Boston MA, 2002.820 [15] M. Hauschild, M. Pelikan, An introduction and survey of estimation of distribution algorithms, Swarm and Evolutionary Computation 1 (3) (2011) 111–128. doi:10.1016/j.swevo.2011.08.003. [16] J. Hu, Y. Wang, E. Zhou, M. C. Fu, S. I. Marcus, A Survey of Some ModelBased Methods for Global Optimization, in: D. Hern´andez-Hern´andez,825 J. A. Minj´arez-Sosa (Eds.), Optimization, Control, and Applications of Stochastic Systems, Birkh¨auser Boston, Boston, 2012, pp. 157–179. doi: 10.1007/978-0-8176-8337-5_10. [17] J. Sacks, W. J. Welch, T. J. Mitchell, H. P. Wynn, Design and analysis of computer experiments, Statistical Science 4 (4) (1989) 409–435.830 [18] K. B. W. G E P Box, On the Experimental Attainment of Optimum Conditions, Journal of the Royal Statistical Society. Series B (Methodological) 13 (1) (1951) 1–45. [19] V. N. Vapnik, Statistical learning theory, Wiley (1998). [20] J. M. Zurada, Analog implementation of neural networks, IEEE Circuits835 and Devices Magazine 8 (5) (1992) 36–41. doi:10.1109/101.158511. [21] M. J. D. Powell, Radial basis functions for multivariable interpolation: A review, in: J. C. Mason, M. G. Cox (Eds.), Algorithms for Approximation, Clarendon Press, New York, NY, USA, 1987, pp. 143–167. [22] M. Schonlau, Computer Experiments and Global Optimization, Ph.D.840 thesis, University of Waterloo, Ontario, Canada (1997). 35 [23] D. B¨uche, N. N. Schraudolph, P. Koumoutsakos, Accelerating Evolutionary Algorithms With Gaussian Process Fitness Function Models, IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 35 (2) (2005) 183–194. doi:10.1109/TSMCC.2004.841917.845 [24] A. B. Antognini, M. Zagoraiou, Exact optimal designs for computer experiments via Kriging metamodelling, Journal of Statistical Planning and Inference 140 (9) (2010) 2607–2617. doi:10.1016/j.jspi.2010.03.027. [25] J. P. C. Kleijnen, Kriging metamodeling in simulation: A review, European Journal of Operational Research 192 (3) (2009) 707–716. doi:850 10.1016/j.ejor.2007.10.013. [26] T. J. Santner, B. J. Williams, W. I. Notz, The Design and Analysis of Computer Experiments, Springer, Berlin, Heidelberg, New York, 2003. [27] Y. Jin, A comprehensive survey of fitness approximation in evolutionary computation, Soft Computing 9 (1) (2005) 3–12.855 [28] Y. Jin, Surrogate-assisted evolutionary computation: Recent advances and future challenges, Swarm and Evolutionary Computation 1 (2) (2011) 61–70. doi:http://dx.doi.org/10.1016/j.swevo.2011.05.001. [29] J. Moˇckus, On Bayesian Methods for Seeking the Extremum, in: Optimization Techniques IFIP Technical Conference, 1974, pp. 400–404.860 [30] D. R. Jones, M. Schonlau, W. J. Welch, Efficient Global Optimization of Expensive Black-Box Functions, Journal of Global Optimization 13 (1998) 455–492. [31] D. R. Jones, A Taxonomy of Global Optimization Methods Based on Response Surfaces, Journal of Global Optimization 21 (2001) 345–383.865 [32] A. I. J. Forrester, A. J. Keane, Recent advances in surrogate-based optimization, Progress in Aerospace Sciences 45 (1-3) (2009) 50–79. doi: 10.1016/j.paerosci.2008.11.001. 36 [33] P. Hajela, E. Lee, Topological optimization of rotorcraft subfloor structures for crashworthiness considerations, Computers & Structures 64 (1-4)870 (1997) 65–76. doi:10.1016/S0045-7949(96)00143-5. [34] A. J. Booker, J. E. Dennis Jr, P. D. Frank, D. B. Serafini, V. Torczon, Optimization Using Surrogate Objectives on a Helicopter Test Example, in: Computational Methods for Optimal Design and Control, Birkh¨auser Boston, Boston, MA, 1998, pp. 49–58. doi:10.1007/875 978-1-4612-1780-0_3. [35] A. J. Booker, J. E. Dennis Jr, P. D. Frank, D. B. Serafini, V. Torczon, M. W. Trosset, A rigorous framework for optimization of expensive functions by surrogates, Structural Optimization 17 (1) (1999) 1–13. doi:10.1007/BF01197708.880 [36] K. C. Giannakoglou, Design of optimal aerodynamic shapes using stochastic optimization methods and computational intelligence, Progress in Aerospace Sciences 38 (1) (2002) 43–76. doi:10.1016/S0376-0421(01) 00019-7. [37] Z. Zhou, Y. S. Ong, P. B. Nair, A. J. Keane, K. Y. Lum, Combining885 Global and Local Surrogate Models to Accelerate Evolutionary Optimization, IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 37 (1) (2007) 66–76. doi:10.1109/TSMCC.2005. 855506. [38] A. Ratle, Accelerating the convergence of evolutionary algorithms by fit-890 ness landscape approximation, in: A. E. Eiben, T. B¨ack, M. Schoenauer, H.-P. Schwefel (Eds.), Parallel Problem Solving from Nature — PPSN V: 5th International Conference Amsterdam, The Netherlands, Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 1998, pp. 87–96. doi:10.1007/BFb0056852.895 [39] Y. Jin, M. Olhofer, B. Sendhoff, On Evolutionary Optimization with Approximate Fitness Functions., in: D. W. et al. (Ed.), Proceedings of the 37 Genetic and Evolutionary Computation Conference GECCO, San Francisco, CA, USA, 2000, pp. 786–793. [40] M. Emmerich, A. Giotis, M. ¨ Ozdemir, T. B¨ack, K. Giannakoglou,900 Metamodel-assisted evolution strategies, in: J. J. M. Guerv´os, P. Adamidis, H. G. Beyer, J. L. Fern´andez-Villaca˜nas, H. P. Schwefel (Eds.), Parallel Problem Solving from Nature—PPSN VII, Proceedings Seventh International Conference, Granada, Springer, Berlin, Heidelberg, New York, 2002, pp. 361–370.905 [41] Y. Jin, B. Sendhoff, Reducing Fitness Evaluations Using Clustering Techniques and Neural Network Ensembles, in: Parallel Problem Solving from Nature - PPSN XIII - 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 688–699. doi:10.1007/978-3-540-24854-5_71.910 [42] J. Branke, C. Schmidt, Faster convergence by means of fitness estimation, Soft 9 (1) (2005) 13–20. doi:10.1007/s00500-003-0329-4. [43] G. Sun, G. Li, S. Zhou, W. Xu, X. Yang, Q. Li, Multi-fidelity optimization for sheet metal forming process, Structural and Multidisciplinary Optimization 44 (1) (2011) 111–124. doi:10.1007/s00158-010-0596-5.915 [44] S. Ulaganathan, I. Couckuyt, F. Ferranti, E. Laermans, T. Dhaene, Performance study of multi-fidelity gradient enhanced kriging, Structural and Multidisciplinary Optimization 51 (5) (2014) 1017–1033. doi: 10.1007/s00158-014-1192-x. [45] S. Koziel, A. Bekasiewicz, I. Couckuyt, T. Dhaene, Efficient Multi-920 Objective Simulation-Driven Antenna Design Using Co-Kriging, IEEE Transactions on Antennas and Propagation 62 (11) (2014) 5900–5905. doi:10.1109/TAP.2014.2354673. [46] M. Kennedy, Predicting the output from a complex computer code when 38 fast approximations are available, Biometrika 87 (1) (2000) 1–13. doi:925 10.1093/biomet/87.1.1. [47] A. Forrester, A. S´obester, A. Keane, Multi-fidelity optimization via surrogate modelling, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 463 (2088) (2007) 3251–3269. doi: 10.1098/rspa.2007.1900.930 [48] L. Le Gratiet, C. Cannamela, Kriging-based sequential design strategies using fast cross-validation techniques with extensions to multi-fidelity computer codes, arXiv.orgarXiv:1210.6187v2. [49] S. Razavi, B. A. Tolson, D. H. Burn, Review of surrogate modeling in water resources, Water Resources Research 48 (7) (2012) 1–32. doi:10.935 1029/2011WR011527. [50] R. Tuo, C. F. J. Wu, D. Yu, Surrogate Modeling of Computer Experiments With Different Mesh Densities, Technometrics 56 (3) (2014) 372–380. doi: 10.1080/00401706.2013.842935. [51] J. P. C. Kleijnen, Design and Analysis of Simulation Experiments, Inter-940 national Series in Operations Research and Management Science, Springer International Publishing, 2015. [52] J. M¨uller, C. A. Shoemaker, Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems, Journal of Global945 Optimization 60 (2) (2014) 123–144. doi:10.1007/s10898-014-0184-0. [53] R. T. Haftka, D. Villanueva, A. Chaudhuri, Parallel surrogate-assisted global optimization with expensive functions – a survey, Structural and Multidisciplinary Optimization 54 (1) (2016) 3–13. doi:10.1007/ s00158-016-1432-3.950 [54] R. Jin, W. Chen, T. W. Simpson, Comparative studies of metamodelling techniques under multiple modelling criteria, Structural and 39 [100] F.-M. Schleif, P. Tino, Indefinite proximity learning: A review, Neural Computation 27 (10) (2015) 2039–2096. [101] T. G¨artner, A survey of kernels for structured data, SIGKDD Explor. Newsl. 5 (1) (2003) 49–58. [102] T. G¨artner, J. Lloyd, P. Flach, Kernels and distances for structured data,1125 Machine Learning 57 (3) (2004) 205–232. [103] D. Haussler, Convolution kernels on discrete structures, Tech. Rep. UCSCCRL-99-10, Department of Computer Science, University of California at Santa Cruz (1999). [104] S. Shakya, Deum: A framework for an estimation of distribution algorithm1130 based on markov random fields, Ph.D. thesis, School of Computing, Faculty of Design and Technology, The Robert Gordon University, Aberdeen, UK (2006). [105] A. Brownlee, J. McCall, Q. Zhang, Fitness modeling with markov networks, IEEE Transactions on Evolutionary Computation 17 (6) (2013)1135 862–879. [106] A. E. Brownlee, Mining Markov network surrogates for value-added optimisation, in: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion - GECCO 16 Companion, Association for Computing Machinery (ACM), 2016, pp. 1267–1274. doi:1140 10.1145/2908961.2931711. [107] S. Jiang, A. Ziver, J. Carter, C. Pain, A. Goddard, S. Franklin, H. Phillips, Estimation of distribution algorithms for nuclear reactor fuel management optimisation, Annals of Nuclear Energy 33 (11–12) (2006) 1039–1057. doi:http://dx.doi.org/10.1016/j.anucene.2006.03.012.1145 [108] J. Ceberio, E. Irurozki, A. Mendiburu, J. A. Lozano, A review on estimation of distribution algorithms in permutation-based combinatorial opti46 mization problems, Progress in Artificial Intelligence 1 (1) (2012) 103–117. doi:10.1007/s13748-011-0005-3. [109] C. L. Mallows, Non-null ranking models, Biometrika 44 (1–2) (1957) 114–1150 130. [110] J. Ceberio, A. Mendiburu, J. A. Lozano, Introducing the mallows model on estimation of distribution algorithms, in: Neural Information Processing - 18th International Conference, ICONIP 2011, Springer Berlin Heidelberg, 2011, pp. 461–470. doi:10.1007/978-3-642-24958-7_54.1155 [111] J. Ceberio, E. Irurozki, A. Mendiburu, J. A. Lozano, A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem, IEEE Transactions on Evolutionary Computation 18 (2) (2014) 286–300. doi:10.1109/TEVC.2013.2260548. [112] R. Allmendinger, C. A. C. Coello, M. T. M. Emmerich, J. Hakanen, Y. Jin,1160 E. Rigoni, Surrogate-assisted multicriteria optimization (wg6), Tech. Rep. 1, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2015). [113] M. Pelikan, D. E. Goldberg, E. Cantu-Paz, BOA: The bayesian optimization algorithm, in: W. Banzhaf, et al. (Eds.), Proceedings of the Genetic1165 and Evolutionary Computation Conference (GECCO’99), Morgan Kaufmann, 1999, pp. 525–532. [114] P. Larra˜naga, R. Etxeberria, J. A. Lozano, J. M. Pe˜na, Combinatorial optimization by learning and simulation of bayesian networks, in: Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intel-1170 ligence, UAI’00, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2000, pp. 343–352. [115] M. N. Le, Y. S. Ong, S. Menzel, Y. Jin, B. Sendhoff, Evolution by adapting surrogates, Evolutionary Computation 21 (2) (2013) 313–340. doi:10. 1162/evco_a_00079.1175 47 [116] M. Kryszkiewicz, J. F. Peters, H. Rybinski, A. Skowron (Eds.), Rough Sets and Intelligent Systems Paradigms, Vol. 4585 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. doi:10.1007/978-3-540-73451-2. [117] T. Bartz-Beielstein, Stacked Generalization of Surrogate Models - A Prac-1180 tical Approach, Tech. Rep. 5/2016, TH K¨oln, K¨oln (2016). [118] F. A. Viana, R. T. Haftka, L. T. Watson, Why not run the efficient global optimization algorithm with multiple surrogates?, in: 51st AIAAASMEASCEAHSASC Structures Structural Dynamics and Materials Conference, no. April, AIAA, 2010, pp. AIAA–2010.1185 [119] N. M. Alexandrov, J. E. Dennis Jr, R. M. Lewis, V. Torczon, A trustregion framework for managing the use of approximation models in optimization, Structural Optimization 15 (1) (1998) 16–23. doi:10.1007/ BF01197433. [120] Y. S. Ong, P. B. Nair, A. J. Keane, Evolutionary Optimization of Com-1190 putationally Expensive Problems via Surrogate Modeling, AIAA Journal 41 (4) (2003) 687–696. doi:10.2514/2.1999. [121] T. Bartz-Beielstein, Experimental Analysis of Evolution Strategies— Overview and Comprehensive Introduction, Reihe CI. SFB 531 157/03, University Dortmund (Nov. 2003).1195 [122] T. Bartz-Beielstein, K. E. Parsopoulos, M. N. Vrahatis, Design and analysis of optimization algorithms using computational statistics, Applied Numerical Analysis and Computational Mathematics (ANACM) 1 (2) (2004) 413–433. [123] T. Bartz-Beielstein, C. Lasarczyk, M. Preuss, Sequential Parameter Op-1200 timization, in: B. McKay, et al. (Eds.), Proceedings 2005 Congress on Evolutionary Computation (CEC’05), Edinburgh, Scotland, IEEE Press, Piscataway NJ, 2005, pp. 773–780. doi:10.1109/CEC.2005.1554761. 48 [124] F. Hutter, H. H. Hoos, K. Leyton-Brown, An Evaluation of Sequential Model-based Optimization for Expensive Blackbox Functions, in: Pro-1205 ceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, ACM, New York, NY, USA, 2013, pp. 1209–1216. doi:10.1145/2464576.2501592. [125] N. Hansen, S. Finck, R. Ros, A. Auger, Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions, Research1210 Report RR-6829, INRIA (2009). [126] M. J. van der Laan, S. Dudoit, Unified cross-validation methodology for selection among estimators and a general cross-validated adaptive epsilonnet estimator: Finite sample oracle inequalities and examples, Working paper 130, University of California, Berkeley, Division of Biostatistics,1215 School of Public Health, University of California, Berkeley (2003). [127] D. H. Wolpert, Stacked generalization, Neural Networks 5 (2) (1992) 241– 259. doi:10.1016/S0893-6080(05)80023-1. [128] M. A. Rebolledo Coy, S. Krey, T. Bartz-Beielstein, O. Flasch, A. Fischbach, J. Stork, Modeling and optimization of a robust gas sensor,1220 Cologne Open Science 03/2016, TH K¨oln, Cologne (2016). [129] D. Douguet, e-lea3d: a computational-aided drug design web server, Nucleic Acids ResearcharXiv:http://nar.oxfordjournals. org/content/early/2010/05/05/nar.gkq322.full.pdf+html, doi:10.1093/nar/gkq322.1225 [130] C. C. Aggarwal, A. Hinneburg, D. A. Keim, On the surprising behavior of distance metrics in high dimensional space, in: Database Theory — ICDT 2001, Vol. 3, Springer Science + Business Media, Munich, 2001, pp. 420–434. [131] A. G. Wilson, C. Dann, H. Nickisch, Thoughts on Massively Scalable1230 Gaussian Processes, arXiv.orgarXiv:1511.01870v1. 49 [132] T. Bartz-Beielstein, How to Create Generalizable Results, in: J. Kacprzyk, W. Pedrycz (Eds.), Springer Handbook of Computational Intelligence, Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 1127–1142. doi: 10.1007/978-3-662-43505-2_56.1235 [133] A. Isaacs, T. Ray, W. Smith, An evolutionary algorithm with spatially distributed surrogates for multiobjective optimization, in: M. Randall, H. A. Abbass, J. Wiles (Eds.), Progress in Artificial Life: Third Australian Conference; ACAL 2007 Gold Coast, Australia, December 4-6, 2007 Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007,1240 pp. 257–268. doi:10.1007/978-3-540-76931-6_23. [134] M. Pil´at, R. Neruda, Aggregate meta-models for evolutionary multiobjective and many-objective optimization, Neurocomputing 116 (2013) 392– 402, advanced Theory and Methodology in Intelligent Computing – Selected Papers from the Seventh International Conference on Intelligent1245 Computing (ICIC 2011). doi:http://dx.doi.org/10.1016/j.neucom. 2012.06.043. [135] D. Horn, T. Wagner, D. Biermann, C. Weihs, B. Bischl, Model-based multi-objective optimization: Taxonomy, multi-point proposal, toolbox and benchmark, in: A. Gaspar-Cunha, C. Henggeler Antunes, C. C.1250 Coello (Eds.), Evolutionary Multi-Criterion Optimization: 8th International Conference, EMO 2015, Guimar˜aes, Portugal, March 29 –April 1, 2015. Proceedings, Part I, Springer International Publishing, Cham, 2015, pp. 64–78. doi:10.1007/978-3-319-15934-8_5. 50 Kontakt/Impressum Diese Veröffentlichungen erscheinen im Rahmen der Schriftenreihe "CIplus". Alle Veröffentlichungen dieser Reihe können unter https://cos.bibl.th-koeln.de/home abgerufen werden. Köln, Januar 2012 Die Verantwortung für den Inhalt dieser Veröffentlichung liegt beim Autor. Datum der Veröffentlichung: 14.11.2016 Herausgeber / Editorship Prof. Dr. Thomas Bartz-Beielstein, Prof. Dr. Wolfgang Konen, Prof. Dr. Boris Naujoks, Prof. Dr. Horst Stenzel Institute of Computer Science, Faculty of Computer Science and Engineering Science, TH Köln, Steinmüllerallee 1, 51643 Gummersbach url: www.ciplus-research.de Schriftleitung und Ansprechpartner/ Contact editor’s office Prof. Dr. Thomas Bartz-Beielstein, Institute of Computer Science, Faculty of Computer Science and Engineering Science, TH Köln, Steinmüllerallee 1, 51643 Gummersbach phone: +49 2261 8196 6391 url: http://www.spotseven.de eMail: [email protected] ISSN (online) 2194-2870 Grant No. KF3145101WM3 and KF3145103WM4 This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 692286.