Many real-world problems belong to the area of continuous black-box optimization. If the black-box function is also cost-aware, regression surrogate models are often utilized by optimization algorithms to save evaluations of the original cost-aware function. Choosing a suitable surrogate model or a suitable setting of its hyperparameters is a complex selection problem, where research into reusing knowledge represented by features of black-box function landscape is only starting. In this paper, we report the research into surrogate model selection, where knowledge from the previous experience with using the model is utilized to design a metalearing system. As a proof of concept, we provide a study investigating the influence of landscape features on the performance of various Gaussian process covariance functions as surrogate models for the state-of-the-art optimization algorithm in the cost-aware continuous black-box optimization.
Surrogate modeling is a technique for saving expensive evaluations of a black-box objective function during the run of an optimization algorithm. Given a set of observations, a surrogate model can be fitted to approximate the landscape of the objective function. However, which surrogate model should be chosen given a particular optimization task? Generally, no surrogate model improves the algorithm always better than all other surrogate model approaches (cf. [ , ]). The performance of each surrogate-assisted algorithm obviously depends on the properties of the data; therefore, investigation of the suitability of different models and their settings for different combinations of the data properties is very much needed.
c 2019 for this paper by its authors. Use permitted under CC BY 4.0.
Surrogate model selection can utilize the experience from the application of the considered models to other optimization tasks, a strategy known as metalearing [ ]. Considering the surrogate model selection problem, it is necessary to extract information about the approximated function, which can be later utilized by a learning system to make a decision about the convenience of particular surrogate models. Therefore, features characterizing properties of the landscape of the objective function should help to better distinguish the model suitability.
In recent years, many features aiming to describe the properties of objective function landscapes have been proposed (cf. the overview in [ ]). However, a majority of landscape features was utilized only for the selection of optimization algorithms and algorithm settings (a. k. a. Algorithm Selection or Algorithm Configuration problems [ ]), not for the selection of surrogate models and their settings. The discussion in [ ] suggests that landscape features can be used to this end, too. However, only little research in that direction is known so far.
In this paper, we report a research into designing a metalearing system for surrogate model selection according to past experience. We study relations between the performance of surrogate models and considered properties of objective function landscapes. As a proof of concept, we utilize results of the investigation in [ ], where the influence of Gaussian process (GP) covariance function settings on the error of GP predictions with respect to the original fitness has been studied in connection with landscape features. We employ a classification tree showing the dependence of the most suitable covariance function on landscape features to adaptively select the most promissing covariance for the GP surrogate model in the surrogate variant of the state-of-the-art black-box optimization algorithm Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [ ], the Doubly Trained Surrogate CMA-ES (DTS-CMA-ES). We evaluate the resulting algorithm performing automatical covariance function selection on the noiseless part of the COCO framework [ , ] and compare it to five DTS-CMA-ES versions without online covariance function selection.
The next section provides a brief introduction to surrogate modeling and landscape analysis. Section states the proposed research problem and our approach to adress it. Section presents a proof of concept of the proposed approach and its experimental results. The last section discusses the results and suggests directions for future research.
Replacing an expensive function f with a trained regression model has been used to speed-up black-box optimization for many years. Such regression model, a. k. a. surrogate model, is trained on the already available input–output value pairs (xi, yi), i = 1, . . . , N , where xk is a point in a search space and yk = f(xk) is an objective function value of xk for k = 1, . . . , N . The model is used instead of the original expensive objective function to evaluate some of the points needed by the optimization algorithm. The response-surface models [ low-degree polynomial models and were used as the historically first models in costly continuous optimization [ , ]. Since then, other models like multi-layer perceptron- and RBF-networks [ ], support vector machine regression [ ], random forests [ ] or Gaussian processes [ , , , ] were also used in black-box optimization.
Simpler models like polynomials are cheap to train; they are thus suitable for the applications where additional computational resources imposed by the model building would constitute a substantial part of the overall optimization cost. On the other hand, random forests and Gaussian processes provide estimation of the prediction uncertainty which can be used in selecting points for evaluation either with the expensive original function, or with the model fitness function [ , ]. classes requiring additional objective function evaluations – the level of convexity (Convexity), gradient and Hessian approximation statistics (Curvature), and features related to local searches conducted from sampled points (Local Search). It was shown [
] that these low-level features relate well the above mentioned high-level properties.
The cell-mapping approach [ ] discretizes the input space to a user-defined number of blocks (i. e., cells) per dimension. Afterwards, the corresponding features are based on the relations between the cells and points within. Three cellmapping feature classes were defined: features extracting information based on the location of the best and worst observation within a cell w.r.t. the corresponding cell center, aggregated cell-wise information on the gradients between each point of a cell and its corresponding nearest neighbor, and estimated convexity of representative observations from three successive cells in each dimension. Additionally, the Generalized Cell Mapping features are based on estimated transition probabilities of moving from one cell to one of its neighboring cells. Using those probabilities, the barrier tree [ ] can be constructed to represent the local optima by tree leaves and landscape ridges by the branching nodes. It should be noted that cell-mapping approach is less useful in higher dimensions where majority of cells is empty and feature computation can require a lot of time and memory.
Nearest better clustering (NBC ) features [ ] are based on the detection of funnel structures. The calculation of such features is based on the comparison of distances from observations to their nearest neighbors and their nearest better neighbors, which are the nearest neighbors among the set of all observations with a better objective value. In [ ], the set of dispersion features comparing the dispersion among the data points and among subsets of these points from the dataset is proposed. The information content features of a continuous landscape are derived in Information Content of Fitness Sequences approach [ ] as the adaptation of methods for calculating of the information content of discrete landscapes. In [ ], three feature sets were proposed: the features providing basic information about the data such as the number of points, boundaries or dimension (Basic), aggregated information about coefficients of linear models fitted in each cell, and information obtained from principle component analysis measuring the proportion of principle components needed to explain a user-defined percentage of variance. A comprehensive survey of landscape analysis methods can be found, e. g., in [ ].
Research into using landscape features for surrogate modeling selection has started only recently. In [ ], the fitness distance correlation was utilized for automatic selection between polynomial and RBF models and their settings as surrogates for a particle swarm optimization algorithm. In [ ], we have investigated relationships between two surrogate models (GP and RF) and a set of landscape features. In [ ], we have proposed the set of landscape features based on the state variables of the CMA-ES algorithm (CMA features) and investigated the relationships of GP covariance functions to landscape features.
The surrogate model selection problem can be formalized as follows: In an iteration i of a surrogate-assisted algorithm A, a set of surrogate models M with hyperparameters θ are trained utilizing particular choices of the training set T . The training set T is selected out of an archive A (T ⊂ A ) using some training set selection method (TSS). The archive contains all points in which the fitness f has been evaluated so far A = { (xi, f(xi))| i = 1, . . . , N } . Afterwards, the surrogate model M ∈ M is utilized to evaluate new set of points (population) P = { xk| k = 1, . . . , α } , where f(xk) can be obtained using the expensive blackbox fitness function and α ∈ N depends on the strategy for the selection of new points for evaluation by the models from M. The main question related to this problem is: How can we select the most convenient models from the set M (and possibly θ ) according to A, T , and P? .
We suggest to use the metalearing approach based on landscape features to tackle the surrogate model selection problem.
Learning phase: First, a set of datasets D = {A (l), T (l), P(l)} lL=1, L ∈ N, is created (ideally via recording the datasets from independent runs of the algorithm A). Second, for each l, each model M ∈ M with hyperparameters θ M is trained on T (l) and its performance is assessed with some error measure ε on P(l). Third, each dataset from D is characterized using a set of landscape features Φ . In this way, a mapping SM : Φ → M or Sθ : Φ → SM∈M Θ M from feature space to M or SM∈M Θ M is learned, where Θ M stands for the set of possible hyperparameters of the model M .
Application phase: In each iteration i of an algorithm A, the landscape features Φ are calculated on datasets A(i), T (i), P(i). After that, the mapping S is used to select the surrogate model M ∈ M and its hyperparameters θ M ∈ Θ M . The selected M ∈ M is trained on T (i) and then utilized for predicting fitness values of the elements of P(i).
Optimization Algorithm Considering cost-aware black-box single-objective optimization of continuous functions, the CMA-ES [ ] has been many times successfully improved using surrogate models to save fitness function evaluations [ , , , ]. The DTS-CMA-ES [ , ] has been shown a valuable representative of such surrogate-assisted versions of the CMA-ES. Therefore, we have utilized DTS-CMA-ES to play the role of the algorithm A in our concept. Surrogate Model and Hyperparameters As a surrogate model, the DTSCMA-ES uses Gaussian processes [ ] due to their ability to estimate the whole distribution of the fitness function. In the DTS-CMA-ES, the Gaussian process model setting is fixed during the whole optimization process, so is the GP covariance function. An essential GP hyperparameter is the type of covariance function. In [ ], we have proposed to select the covariance function for a GPbased surrogate model for the CMA-ES using a Bayesian approach.
Mapping The results in [ ] suggested that mapping from the space of features calculated on A, T , and P to the value set of a categorical hyperparameter can be represented by a classification tree.
Error Measure The CMA-ES state variables are adjusted according to the ordering of μ best points from the current population. Therefore, the Ranking Difference Error [ ] is a convenient measure of model error for the DTS-CMA-ES RDEμ (yˆ, y) =
Pi:(ρ (y))i≤ μ | (ρ (y))i − (ρ (yˆ))i| maxπ ∈ Permutations of (1,...,λ ) Pi:π (i)≤ μ | i − π (i)| , ( ) where (ρ (y))i is the rank of yi among the components of y.
Dataset To generate a set of datasets D, we have used independent runs of the DTS-CMA-ES on the noiseless single-objective benchmarks from the COCO framework [ , ] in dimensions , , , , and on instances – . Using each of the different covariance functions from [ ] in each of those independent runs, data from uniformly selected generations were recorded. The runs of the algorithm were terminated in cases when the limit of 250 function evaluations per dimensions was exceeded or when the target fitness value 10− 8 was reached. The details of generating the datasets can be found in [ ].
Landscape Features The following feature classes were employed to characterize all the sets A, T , and P from the datasets in D: y-Distribution, Levelset, Meta-Model, NBC, Dispersion, Information Content, and CMA features. In addition, the dimension D and the number of observations N from the Basic feature class were also utilized. The rest of features from classes described in Subsection . were excluded, mainly due to requiring additional evaluations of the objective function f.
Classification Tree for Covariance Functions The classification tree T depicted in Figure has been obtained in [ ] and represents the influence of landscape features on the most suitable covariance function. To train the tree T , all the sets described by features in the previous paragraph were divided into classes according to which of the considered GP model settings achieved the lowest RDEμ . The tree was trained using the MATLAB implementation of the CART algorithm [ ], where all features were considered as continuous variables. The fully-grown tree was pruned to depth resulting in the shown tree T . The set of training points and the respective population is denoted TP = T ∪ { (x, ◦ )| ∀ x ∈ P} , where ◦ indicates the unknown fitness value of a point from the current population P.
Source code covering all mentioned experiments is available on http://uivty.cs.cas. cz/~cma/ecml /source.zip ≥ − 1.1e8 ϕ Ls(A)
1 0.9 0.8 0.7 0.6
The features employed in the tree T represent various landscape properties: D is the dimension of the investigated function; ϕ L is the log-likelihood of the set of points X with respect to the CMA-ES sampling distribution [ ] (see Figure for the average RDEμ dependency on ϕ L(A) ); ϕ R(mean) and ϕ R(med) denote two ratios of the mean and median distances of the ’best’ objectives vs. ’all’ objectives [ ]; ϕ Ls, ϕ Qs, and ϕ Qi represent the adjusted R2 (i. e., the model fit) of linear, quadratic simple, and quadratic with interactions fitted regression models [ ]; ϕ QDA is the mean missclassification error of Quadratic Discriminant Analysis on points divided into two classes according to the fitness values with median as a threshold [ ]; ϕ denotes the argument of the maximum information content of the fitness sequence [ ].
The covariance functions located in leaves of the tree T are listed in Table . Covariance Function Selection The implementation of the selection of the covariance function for the DTS-CMA-ES based on the classification tree T is quite straightforward. We have modified the original algorithm only in the GP model training method (see Algorithm ). We have incorporated an additional step applying covariance function selection using the classification tree T between the training set transformation and fitting the GP hyperparameters θ . Covariance selection validation setup We have compared the described adaptive DTS-CMA-ES that online chooses the covariance function using the tree T (denoted as T-DTS) with five DTS-CMA-ES versions that use solely one covariance from Table . The comparison was performed on the noiseless part of the COCO framework using instances – and – of all benchmark functions in dimensions , , , , and . Each of the six DTS-CMA-ES versions had a budget of 250D fitness function evaluations to reach the target value 10− 8 from the function optimum. Except the choice of the covariance function, the DTS-CMA-ES was tested in its non-adaptive version using the overall best settings from [ ]. .
Results from the comparison of six DTS-CMA-ES versions are depicted in Table and Figures and . The graphs in Figures and show the dependence of the scaled best-achieved logarithms Δ lfog of median distances Δ fmed to the optimal fitness value on the number of cost-aware fitness evaluations divided by the dimension. Medians Δ fmed, st, and rd quartiles are calculated from independent instances for each respective algorithm, function, and dimension. The scaled logarithms of Δ fmed are calculated as Δ lfog = log Δ fmed − Δ fMIN Δ fMAX − Δ fMIN log10 1/10− 8 + log10 10− 8 , ( ) where Δ fMIN (Δ fMAX) is the minimal (maximal) distance log Δ fmed found among all the compared algorithms for the particular function f and dimension D between 0 and 250 function evaluations per D. The resulting values are scaled to interval [− 8, 0], where − 8 corresponds to Δ fMIN and 0 to Δ fMAX. More detailed results can be found on an authors’ webpage .
We have tested the statistical significance of performance differences on COCO functions in 5D using the Iman and Davenport’s improvement of the Friedman test [ ]. The test was conducted separately for two function evaluation budgets. Let #FET be the smallest number of function evaluations at which at least one DTS-CMA-ES version reached the precision Δ fmed ≤ 10− 8, or #FET = 250D if no version reached the precision within 250D evaluations. The DTS-CMA-ES versions are ranked on each COCO function with respect to Δ fmed at a given budget of function evaluations. The null hypothesis of equal performance of all versions is rejected for the higher function evaluation budget #FEs = #FET, as well as for the lower budget #FEs = #FET (in both cases, 4 p < 10− 3).
We test pairwise differences in the performance using the post-hoc Friedman test [ ] with the Bergmann-Hommel correction controlling the family-wise error. The numbers of functions at which one DTS-CMA-ES version achieved a higher rank than the other are enlisted in Table . The table also contains the pairwise statistical significances.
From the results in Table and in Figures and , we can consider the results of the T-DTS, and the DTS-CMA-ES with SE, Mat, and RQ covariances being statistically equivalent meaning that neither of them is significantly better than the other one. Looking on the detailed results on the authors’ webpage , those covariances provided the best performance on the functions f5, f8− 11, and f14. On the other hand, slightly worse results can be observed on functions f7, f13, f16, and f20. On functions f6 and f17,18 the T-DTS results more or less follow SE, Mat, and RQ performance although the best performance was provided by the Gibbs covariance. The results on multimodal functions f22− 24 show increasing T-DTS performance with growing dimension. The versions using LIN and Gibbs http://uivty.cs.cas.cz/~cma/ecml / covariance functions provide considerably lower performance in comparison with the remainder. Variability of length-scale utilized by Gibbs covariance function helps the DTS-CMA-ES to converge on hard-to-regress f6 and on multimodal Schaffer’s functionsf17,18 especially in higher dimensions, where the performance of DTS-CMA-ES using Gibbs covariance in GP model is the best of all compared versions.
A possible reason of the T-DTS results may lie in an imbalance of the input dataset for decision tree. Covariances SE, Mat, and RQ performed almost similar and, in average, provided the overall best prediction performance among tested covariances on the set of datasets D. Therefore, these three covariances were marked as best on most of datasets and the remaining two (LIN and Gibbs) were best on minority of datasets. The trained classification tree was probably not able to capture such imbalance of the input data and predicted LIN or Gibbs as the most convenient covariances more often than it was necessary.
This article investigates the surrogate model selection problem for continuous single-objective black-box optimizers in the context of reusing knowledge through landscape analysis. The proposed concept was applied to select a hyperparameter of Gaussian process models, namely the covariance function, and was utilized during the DTS-CMA-ES run to save costly fitness evaluations. The DTS-CMAES upgraded with hyperparameter selection was compared to five DTS-CMA-ES versions using different covariances on the set of noiseless benchmarks.
The presented proof of concept has shown that the methodology can be utilized for hyperparameter selection. The tree-assisted DTS-CMA-ES had a performance equivalent to DTS-CMA-ES versions with successful fixed covariance functions. On the other hand, the classification tree as a mapping of values of Knowledge-based Gaussian Process Surrogates
Zbyněk Pitra, Lukáš Bajer, and Martin Holeňa log settings of DTS-CMA-ES GP covariance function.
59 50 100
150 different settings of DTS-CMA-ES GP covariance function.
60 50 100
150 aNllumfubnecrtoiofnevsa(luf1a-t2io4n)s 2/0DD
200 50 100
150 Number of evaluations / D 200
T-DTS LIN SE Mat4ern RQ Gibbs T-DTS LIN SE Mat4ern RQ Gibbs T-DTS LIN SE Mat4ern RQ Gibbs T-DTS LIN SE Mat4ern RQ Gibbs T-DTS LIN SE Mat4ern RQ Gibbs T-DTS LIN SE Mat4ern RQ Gibbs 250 250 log landscape features to the covariance functions for the DTS-CMA-ES seems not to have learned very accurately.
Future research should be focused mostly on deeper understanding of the surrogate model selection problem and the possibilities of landscape analysis in this context. The investigation of various mappings to models and their hyperparameters capable to capture relationships between landscape features and surrogate model performance is definitely needed. Another direction is to extend the presented research also to other kinds of surrogate models. Acknowledgements The reported research was supported by the Czech Science Foundation grants Nos. - S and - S and by the Grant Agency of the Czech Technical University in Prague with its grant No. SGS / /OHK / T/ . Further, access to computing and storage facilities owned by parties and projects contributing to the National Grid Infrastructure MetaCentrum, provided under the programme "Projects of Large Research, Development, and Innovations Infrastructures" (CESNET LM ), is greatly appreciated. . Auger, A., Schoenauer, M., Vanhaecke, N.: LS-CMA-ES: A second-order algorithm for covariance matrix adaptation. In: Parallel Problem Solving from Nature - PPSN VIII. pp. – ( ) . Bajer, L., Pitra, Z., Holeňa, M.: Benchmarking Gaussian processes and random forests surrogate models on the BBOB noiseless testbed. In: Proceedings of the th GECCO Conference Companion. ACM, New York, Madrid (July ) . Bajer, L., Pitra, Z., Repický, J., Holeňa, M.: Gaussian process surrogate models for the CMA Evolution Strategy. Evolutionary Computation ( ), – ( ). https://doi.org/ . /evco_a_ , pMID: . Breiman, L.: Classification and regression trees. Chapman & Hall/CRC ( ) . Büche, D., Schraudolph, N.N., Koumoutsakos, P.: Accelerating evolutionary algorithms with Gaussian process fitness function models. IEEE Transactions on Systems, Man, and Cybernetics, Part C ( ), – ( ) . Demšar, J.: Statistical comparisons of classifiers over multiple data sets. Journal of
Machine Learning Research , – ( ) . Flamm, C., Hofacker, I.L., Stadler, P.F., Wolfinger, M.T.: Barrier Trees of Degenerate Landscapes. Zeitschrift für Physikalische Chemie International Journal of Research in Physical Chemistry and Chemical Physics ( ), – ( ) . García, S., Herrera, F.: An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. Journal of Machine Learning Research , – ( ) . Gibbs, M.N.: Bayesian Gaussian Processes for Regression and Classification. Ph.D.
thesis, Department of Physics, University of Cambridge ( ) . Hansen, N.: The CMA evolution strategy: A comparing review. In: Towards a New Evolutionary Computation, pp. – . No. in Studies in Fuzziness and Soft Computing, Springer Berlin Heidelberg (Jan ) . Hansen, N., Auger, A., Finck, S., Ros, R.: Real-parameter black-box optimization benchmarking : Experimental setup. Tech. rep., INRIA ( )