Exploratory Analysis of Fitness Landscapes
Surrogate model selection is an active-learning approach to cost-aware continuous black-box optimization in domains where the evaluation of the black-box objective function is expensive, e. g., obtained experimentally or resulting from comprehensive simulations. Active reusing of knowledge represented by landscape properties of the objective function accross different tasks can provide additional information for more reliable decisions in terms of a suitable surrogate model and a suitable setting of its hyperparameters. However, research into using metalearing [ ] and especially Exploratory Landscape Analysis (ELA) [ ] in this context is only starting [ ]. Our goal is to develop a learning system capable to recommend a surrogate model on the basis of the knowledge obtained in previous black-box optimization tasks.
In this paper, we provide a first step necessary to construct a learning system applying knowledge from previous tasks to a new one: a study of the applicability of ELA to two important kinds of surrogate models – Gaussian processes (GP) [ ] and ensembles of regression trees (random forests, RF) [ , , ]. Results using the noiseless benchmarks of the Comparing-Continuous-Optimisers (COCO) platform [ ] in the expensive scenario, where at most D evaluations are available, are analysed for statistical dependences between model performance and a broad variety of landscape features. In order to achive our goal, the relationships between data properties and surrogate model performances has to be analysed in detail first. Second, the investigated relationships will be used to design a system capable to transfer knowledge about relationships from processed tasks to new ones.
The surrogate model selection problem is analogous to the algorithm selection problem (ASP) formulated in [ ] and it aims at selecting the most suitable surrogate model for a specific optimization task. Considering ASP, ELA [ ] aims at characterizing the landscape of an investigated function and deriving rules how those characteristics influence the performance of the optimization algorithm.
We analyze relationships between the mean-squared error (MSE) of different settings of GP or RF described in Appendix A. and out of ELA features (see also Appendix A. ) which didn’t yield constant over noiseless benchmark functions from the COCO framework [ ] in dimensions D = { 2, 5, 10} and their instances for any of the tested GP or RF settings. The datasets consisting of 50D points for each instance per function were generated by a random improved Latin Hypercube design [ ] covering the input space [− 5, 5]D. The overall predictive performance of the surrogate models was tested through 5-fold cross-validation on the generated datasets.
As a first step, we performed a simple correlation analysis using the Spearman correlation coefficient between the MSE of the considered models and the investigated ELA features. However, no single ELA feature was found to be discriminative for surrogate model performance, although a few features were positively (or negatively) correlated with all considered models, which indicates the landscape to be difficult (or easy) for fitting any of them.
As a second step, a classification tree representing a multivariate statistical analysis was built using the obtained results. The resulting tree is depicted in Figure . ELA features were classified into classes according to which of the considered settings of GP and RF achieved the lowest MSE for the respective combination of dimension and function among all evaluated settings. Features describing the global structure of the objective function landscape were detected as most distinctive (f , f , f , f , f , f , and f ). Global structure of the landscape can possibly influence the performance of a particular model. Very interesting is the discovered importance of basic features such as dimension (f ) or extreme values of the objective function (f ). In addition, skewness (f ) and the kurtosis (f ) also had influence on surrogate model selection. The last mentioned observations may suggest that even a set of simple features can provide valuable information about the model suitability.
The results suggest that clear relationships between the performance of the compared settings of GP and RF models and the considered features are not easy to derive. Features describing global properties of the landscape are very useful in case of selection of the surrogate model and its settings. On the other hand, simple features can also provide important knowledge useful for future decisions.
The intended direction for our future research is to apply the obtained knowledge to select a suitable surrogate model for previously unseen data in designing a metalearning system. Another important research direction is to investigate the impact of the sampling strategy in the input space to the resulting landscape features and their relationship with the perfomance of the considered models and their various settings.
Function instances are defined by transformations (translations, rotations, and shifts) of both the search space and function values. Acknowledgements The reported research was supported by the Czech Science Foundation grant No. - , by the Grant Agency of the Czech Technical University in Prague with its grant No. SGS / /OHK / T/ , and by Specific College Research project number . Computational resources were provided by the CESNET LM under the programme "Projects of Large Research, Development, and Innovations Infrastructures". . Beachkofski, B., Grandhi, R.: Improved distributed hypercube sampling. In: Proceedings of the rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference. p. . American Institute of Aeronautics and Astronautics ( ) . Beirlant, J., Dudewicz, E.J., Györfi, L., Van der Meulen, E.C.: Nonparametric entropy estimation : an overview. International Journal of Mathematical and Statistical Sciences ( ), – ( ) . Breiman, L.: Classification and regression trees. Chapman & Hall/CRC ( ) . Breiman, L.: Bagging predictors. Machine learning ( ), – ( ) . Chaudhuri, P., Huang, M.C., Loh, W.Y., Yao, R.: Piecewise-polynomial regression trees. Statistica Sinica ( ), – ( ) . Chen, T., Guestrin, C.: XGBoost: A scalable tree boosting system. pp. – .
KDD ’ , ACM ( ) . Dobra, A., Gehrke, J.: SECRET: A scalable linear regression tree algorithm. pp.
– . KDD ’ , ACM ( ) . Duvenaud, D.K., Nickisch, H., Rasmussen, C.E.: Additive gaussian processes. In: Advances in Neural Information Processing Systems , pp. – . Curran Associates, Inc. ( ) . Hansen, N., Finck, S., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking : Noiseless functions definitions. Tech. Rep. RR- , INRIA ( ), updated February . Hinton, G.E., Revow, M.: Using pairs of data-points to define splits for decision trees. In: Advances in Neural Information Processing Systems. vol. , pp. – .
MIT Press ( ) . Kerschke, P.: Comprehensive feature-based landscape analysis of continuous and constrained optimization problems using the R-package flacco. ArXiv e-prints ( ) . Kerschke, P., Dagefoerde, J.: flacco: Feature-Based Landscape Analysis of Continuous and Constraint Optimization Problems ( ), https://cran.r-project.org/ package=flacco , R-package v. . . Lemke, C., Budka, M., Gabrys, B.: Metalearning: a survey of trends and technologies.
Artificial Intelligence Review ( ), – (Jun ) . Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.:
Exploratory landscape analysis. pp. – . GECCO ’ , ACM ( ) . Murthy, S.K., Kasif, S., Salzberg, S.: A system for induction of oblique decision trees. J. Artif. Int. Res. ( ), – ( ) . Neal, R.M.: Bayesian Learning for Neural Networks. Springer-Verlag New York,
Inc., Secaucus, NJ, USA ( ) . Pitra, Z., Repický, J., Holeňa, M.: Boosted regression forest for the doubly trained surrogate covariance matrix adaptation evolution strategy. ITAT , CreateSpace Independent Publishing Platform, North Charleston, USA ( ) . Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning.
Adaptative computation and machine learning series, MIT Press ( ) . Rice, J.R.: The algorithm selection problem. Advances in Computers, vol. , pp.
– . Elsevier ( ) . Yu, H., Tan, Y., Sun, C., Zeng, J., Jin, Y.: An adaptive model selection strategy for surrogate-assisted particle swarm optimization algorithm. pp. – . SSCI ’ ( ) A A.
Experimental setup The GP regression model in gpml implementation was employed using different covariance functions, listed in Table , and constant mean μ (x) = mean(y), where y are the outputs of the training set. The hyperparameters were optimized with MATLAB’sfmincon using optimization trials, except for the additive covariance function kADD, which was optimized with only trials due to its relatively high complexity. The rest of initial values for hyperparameters, together with their bounds are reported Table . The initial values for repeated optimization trials were sampled.
The RF models were tested using the full-factorial desing on the ensemble method, splitting method, and error gain function. In addition, the number of trees ntree, the number of points Nt, and the number of dimensions used for training the individual tree nD were sampled from the values in Table . Thus, the RF experimental part sampled RF models from different settings. MSE (errMSE), variance of predicted y-values (errvar), and nearest-neighbor entropy estimator [ ] (errNN) were employed as error gain functions (err). In bagged RF, cross-validation pruning [ ] was utilized to optimize the tree structure. In addition, the following five regression models were used in leaves: constant, linear, linear with interactions, quadratic without interactions, and full quadratic. The model providing the best fit according to the MSE loss function was always selected for the relevant leaf and appropriate data. In boosted RF, the maximum tree depth was set to 8, in accordance with [ ].
Considering decision tree settings regardless the ensemble method, the five splitting methods from the following algoritms were employed: CART [ ], SECRET [ ], OC [ ], SUPPORT [ ], and a method from [ ] (PAIR). The remaining decision tree parameters have been taken identical to settings from [ ].
The calculated landscape features were from the following ELA feature sets [ , ]: y-Distribution, Levelset, Meta-Model, CM-Angle, CM-Gradient Homogeneity, CM-Convexity, NBC, Dispersion, Information Content, Basic, and PCA. Feature sets requiring additional evaluations of the objective function (Convexity, Local Search, and Curvature) and cell-mapping feature sets with high computational or memory requirements in higher dimension (GCM, Barrier Trees, and Linear Model) were omitted. All landscape features were calculated using default settings from [ ]. distance measure P = l− 2ID, x˜p, x˜q – inputs augmented by a bias unit,k(i) xp(i), xq(i) – one-dimensionalkSE, R ⊆ { 1, . . . , D} – set of selected degrees of interactions.kSE and kRQ were used in both isotropic and automatic relevance determination (ARD) versions (kSAERD, kRAQRD).
name kernel d2 squared-exponential kSE(d; σ f , l) = σ f2 exp − 2l2 Matérn family rational quadratic additive [ ] neural network [ ] kNN(xp, xq) = σ f2 arcsin 2x˜pT P x˜q p(1+2x˜pT P x˜p)(1+2x˜qT P x˜q) kMν=at21´ern(d; σ f , l) = σ f2 exp − l
d kMν=at23´ern(d; σ f , l) = σ f2 1 + √ l3d exp − √ l3d kMν=at52´ern(d; σ f , l) = σ f2 1 + √ l5d + 53dl22 exp − √ l5d
2 − α kRQ(d; σ f , l) = σ f2 1 + 2dl2α kADD(xp, xq, R) = Pr∈ R σ f(r) P1≤ i1<i2<· <ir≤ D
Qrd=1 k(id) xp(id), xq(id) tionally to Dr . { 1, . . . , D} of interaction separately. σ f(r) and its upper bound were initialized proporGP hyperparam initial value constrains σ n l σ f 1e− 2 std(X) std(y) √ 2 [1e− 3, 1e1] [1e− 2, 1e2] [1e− 2, 1e6] f
f ≥ 0.91
RFbag SUPPORT
NN
< 7.5 ≥ 7.5