A context in which we expect adaptive learning to be promising is the choice of a suitable optimization strategy in black-box optimization. The reason why strategy adaptation is needed in such a situation is that knowledge of the blackbox objective function is obtained only gradually during the optimization. That knowledge covers two aspects: . the landscape of the black-box objective, revealed through its evaluation in previous iterations; . success or failure of the optimization strategies applied to that black-box objective in previous iterations.
To extract landscape knowledge, landscape analysis has been developed during the last decade [ , , ]. To include also the second aspect, we complement features obtained using the landscape analysis with features describing the optimization employed in previous iterations.
Our interest is in expensive black-box optimization, where the number of evaluations of the expensive objective is usually decreased using a suitable surrogate model. Therefore, the research reported in this extended abstract addresses adaptive learning of surrogate models, more precisely their learning in surrogateassisted versions of the state-of-the-art black-box optimization method, Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [ ].
Considering the results in [ , ] suggesting that the properties of landscape features in connection with surrogate model selection problem should be analysed in more detail, we contribute with this work a first essential step towards a better understanding, by analysing the robustness of feature computation. Such analysis of a large set of landscape features has already been presented only in connection with selection of the most convenient optimization algorithm for problems in fixed dimension [ ].
© 2020 for this paper by its authors. Use permitted under CC BY 4.0.
This extended abstract focuses on surrogate model selection task in multiple dimensions and discusses robustness of several classes of features against samples of points from the same distribution.
where ◦ fSeaNt∈ uNreRcNo,mDp× ut(aRtio∪{◦} n.
Landscape analysis aims at measuring characteristics of the objective function using functions that assign to each dataset a set of real numbers [ ]. Let’s consider a dataset of N pairs of observations (xi, yi) ∈ RD × R ∪ {◦} | i = 1, . . . , N , denotes missing yi value (e. g., x i was not evaluated yet). Then the dataset can be utilized to describe landscape properties using a feature ϕ : )N,1 →7
R ∪ {±∞ , }• , where • denotes impossibility of
Feature classes convenient for continuous black-box optimization field are mostly described in [ ]. From the available feature classes we mention only those convenient for problems with a high computational complexity (unlike e. g., cellmapping approach [ ]) and at the same time not requiring additional evaluations of the expensive function. Feature classes are able to measure the dissimilarity among points of a subset of the sample (Dispersion) [ ], express various information content of the landscape (Information Content) [ ], measure the relative position of each value with respect to quantiles (Levelset) [ ], extract the information from linear or quadratic regression models (Meta-Model) [ ] or from the nearest or the better observation neighbours (Nearest Better Clustering) [ ], and describe the distribution of the objective values (y-Distribution) [ ]. Moreover, in [ ] we have proposed the set of features based on the CMA-ES state variables (CMA features).
The surrogate model selection problem tackle the situation in an iteration trained using a training set T selected out of an archive A ( T ⊂ A i of a surrogate-assisted algorithm A, where a set of surrogate models M ) of all points evaluated so far using the objective function f: A = { (xi, f(xi))| i = 1, . . . , N } . Hereafter, a new set of points P = { xk| k = 1, . . . , α } is evaluated using a surrogate model M ∈ M
, where α ∈ N depends on the strategy defining the usage of surrogate model in algorithm A. The research question is: How to select are the most convenient M from
M
according to A, T , and P?
To tackle the research question connected with the surrogate model selection problem, we have proposed (see [ ]) the following metalearning approach visualised in Figure :
(l), T (l), P (l)
L } l=1, L ∈ N and its error ε is measured on P (l).
Simultaneously, a set of features Φ is computed on each dataset from D . Hereby, (l) from the set a mapping SM : Φ → M from the space of landscape features to
In the second phase, the trained mapping SM is utilized in each iteration i of the algorithm A to select the model M ∈ M predict objective function values of points from P on A (i), T (i), and P (i). The selected M is utilized to fit T
(i). according to the features Φ calculated (i) and afterwards to D
A
T
P
Φ (A, T , P)
Train model on T
S
minimizing ε S : Φ 7→ M M ∈ M
ε (M) ∈ E
performance on P
To investigate robustness of feature computation against different samples of points (in the sense of low variance), several independent archive realisations using the same distributions should be available. To gain such realisations, we have created a new set of artificial distributions by smoothing the distributions from real runs of the surrogate algorithm on the set of benchmarks.
First, we have generated a set of datasets D using independent runs of the model settings from [ ] for the DTS-CMA-ES algorithm [ , ] on the noiseless single-objective benchmark functions from the COCO framework [ , ]. All runs were performed in dimensions , , , , and on instances – . To gain comparable archives using those runs, we have generated points for new archives using the weighted sum of original archive distributions from D, where the weight vector w(i) = 91 (0, . . . , i− 03, i− 12, i− 21, 3i , i+21, i+12, i+03, . . . , 0)> provides distribution smoothing across the available iterations . Second, for all A(i), T (i), and P(i) from D we have computed all features from the following feature classes: Dispersion, Information Content, Levelset, Meta-Model, Nearest Better Clustering, y-Distribution, CMA features.
Once the features are computed, the numbers of ±∞ and • values of different samples from one iteration are summarized and the rest of feature values is normalized to [0, 1] range using feature minima and maxima over the whole D. We then compare feature means and variances for individual iterations.
Weighted sum of the original archive distributions satisfies Pinm=a0x wn(i)N m(n), C(n) ∼ N Pinm=a0x wn(i)m(n), Pinm=a0x (wn(i))2C(n) , where imax is the maximal iteration reached by particular original archive and m(n) and C(n) are mean and covariance matrix in iteration n. 6 75 numb2e1r0of observations 476 1185 1.2 1.5
2.1 3.5 density of observations 6.7 4.4 100 s e l p 50 sam f o % 100 s e l p m 50 sa f o % 220 120 43 numb7e4r of observations 117 221 1.2 1.4
1.8 2.8 density of observations
The extended abstract addressed adaptive learning of a suitable optimization setting in black-box optimization, more precisely, adaptive learning of a surrogate model in a surrogate-assisted version of the CMA-ES. Its main message is the relationship of this kind of adaptive learning to landscape analysis. A formal framework for the learning of a surrogate model based on landscape analysis is given, and considered kinds of landscape features are discussed. In the results obtained so far, attention is paid in particular to feature robustness.
This work in progress is part of a thorough investigation of the possibilities of landscape analysis in the context of surrogate modelling for black-box optimization. That investigation has already brought first results in the past [ , , ], but much still remains for further research.
Acknowledgements The reported research was supported by the Czech Science Foundation grant No. - 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. . Bajer, L., Pitra, Z., Repický, J., Holeňa, M.: Gaussian process surrogate models for the CMA Evolution Strategy. Evolutionary Computation ( ), – ( ) . Dvořák, M.: Optimization of surrogate model settings using landscape analysis.
Master’s thesis, Czech Technical University in Prague, Faculty of Information Technology, Prague, Czech Republic ( ) . 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 ( ) . Hansen, N., Finck, S., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking : Noiseless functions definitions. Tech. Rep. RR- , INRIA ( ), updated February . Kerschke, P., Preuss, M., Wessing, S., Trautmann, H.: Detecting funnel structures by means of exploratory landscape analysis. pp. – . GECCO ’ , ACM ( ) . Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated algorithm selection: Survey and perspectives. Evolutionary computation ( ), – ( ) . Kerschke, P., Preuss, M., Hernández, C., Schütze, O., Sun, J.Q., Grimme, C., Rudolph, G., Bischl, B., Trautmann, H.: Cell mapping techniques for exploratory landscape analysis. In: EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V. pp. – . Springer International Publishing ( ) . Lunacek, M., Whitley, D.: The dispersion metric and the cma evolution strategy.
pp. – . GECCO ’ , ACM ( ) . Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.:
Exploratory landscape analysis. pp. – . GECCO ’ , ACM ( ) . Muñoz, M.A., Kirley, M., Halgamuge, S.K.: Exploratory landscape analysis of continuous space optimization problems using information content. IEEE Transactions on Evolutionary Computation ( ), – ( ) . Pitra, Z., Bajer, L., Holeňa, M.: Doubly trained evolution control for the Surrogate CMA-ES. In: Proceedings of the PPSN XIV: th International Conference, Edinburgh, UK, September - . pp. – . Springer International Publishing, Cham ( )