More Web Proxy on the site http://driver.im/

research-article

The importance of landscape features for performance prediction of modular CMA-ES variants

Authors:

Diederick Vermetten,

Sašo Džeroski,

Tome EftimovAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 648 - 656

https://doi.org/10.1145/3512290.3528832

Published: 08 July 2022 Publication History

Abstract

Selecting the most suitable algorithm and determining its hyperparameters for a given optimization problem is a challenging task. Accurately predicting how well a certain algorithm could solve the problem is hence desirable. Recent studies in single-objective numerical optimization show that supervised machine learning methods can predict algorithm performance using landscape features extracted from the problem instances.

Existing approaches typically treat the algorithms as black-boxes, without consideration of their characteristics. To investigate in this work if a selection of landscape features that depends on algorithms' properties could further improve regression accuracy, we regard the modular CMA-ES framework and estimate how much each landscape feature contributes to the best algorithm performance regression models. Exploratory data analysis performed on this data indicate that the set of most relevant features does not depend on the configuration of individual modules, but the influence that these features have on regression accuracy does. In addition, we have shown that by using classifiers that take the features' relevance on the model accuracy, we are able to predict the status of individual modules in the CMA-ES configurations.

References

[1]

Anne Auger, Dimo Brockhoff, and Nikolaus Hansen. 2011. Mirrored Sampling in Evolution Strategies with Weighted Recombination. In GECCO. ACM, 861--868.

Digital Library

[2]

Anne Auger and Nikolaus Hansen. 2005. A restart CMA evolution strategy with increasing population size. In Proc. of Congress on Evolutionary Computation (CEC'05). 1769--1776.

[3]

Amine Aziz-Alaoui, Carola Doerr, and Johann Dréo. 2021. Towards large scale automated algorithm design by integrating modular benchmarking frameworks. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'21, Companion material). ACM, 1365--1374.

Digital Library

[4]

Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel Lopez-Ibanez, et al. 2020. Benchmarking in optimization: Best practice and open issues. arXiv preprint arXiv:2007.03488 (2020).

[5]

Nacim Belkhir, Johann Dréo, Pierre Savéant, and Marc Schoenauer. 2017. Per instance algorithm configuration of CMA-ES with limited budget. In Proc. of Genetic and Evolutionary Computation (GECCO'17). ACM, 681--688.

Digital Library

[6]

Rick Boks, Hao Wang, and Thomas Bäck. 2020. A modular hybridization of particle swarm optimization and differential evolution. In GECCO '20: Genetic and Evolutionary Computation Conference, Companion Volume, Cancún, Mexico, July 8--12, 2020, Carlos Artemio Coello Coello (Ed.). ACM, 1418--1425.

Digital Library

[7]

C.L. Camacho Villalón, M. Dorigo, and T. Stützle. 2021. PSO-X: A component-based framework for the automatic design of particle swarm optimization algorithms. Technical Report TR/IRIDIA/2021-002. IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.

[8]

Jacob de Nobel, Diederick Vermetten, Hao Wang, Carola Doerr, and Thomas Bäck. 2021. Tuning as a means of assessing the benefits of new ideas in interplay with existing algorithmic modules. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'21, Companion material), Krzysztof Krawiec (Ed.). ACM, 1375--1384.

Digital Library

[9]

Jacob de Nobel, Hao Wang, and Thomas Baeck. 2021. Explorative data analysis of time series based algorithm features of CMA-ES variants. In Proceedings of the Genetic and Evolutionary Computation Conference. 510--518.

Digital Library

[10]

Alberto Franzin and Thomas Stützle. 2019. Revisiting simulated annealing: A component-based analysis. Comput. Oper. Res. 104 (2019), 191--206.

[11]

Nikolaus Hansen. 2009. Benchmarking a BI-Population CMA-ES on the BBOB-2009 Function Testbed. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (Montreal, Québec, Canada) (GECCO '09). Association for Computing Machinery, New York, NY, USA, 2389--2396.

Digital Library

[12]

Nikolaus Hansen. 2019. A global surrogate assisted CMA-ES. In Proceedings of the Genetic and Evolutionary Computation Conference. 664--672.

Digital Library

[13]

Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, and Dimo Brockhoff. 2020. COCO: A platform for comparing continuous optimizers in a black-box setting. Optimization Methods and Software (2020), 1--31.

[14]

Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829. INRIA. https://hal.inria.fr/inria-00362633

[15]

Nikolaus Hansen and Andreas Ostermeier. 1996. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In Proc. of IEEE Congress on Evolutionary Computation (CEC'96). IEEE, 312--317.

[16]

Anja Jankovic and Carola Doerr. 2020. Landscape-aware fixed-budget performance regression and algorithm selection for modular CMA-ES variants. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 841--849.

Digital Library

[17]

Anja Jankovic, Gorjan Popovski, Tome Eftimov, and Carola Doerr. 2021. The Impact of Hyper-Parameter Tuning for Landscape-Aware Performance Regression and Algorithm Selection. In Genetic and Evolutionary Computation Conference (GECCO 2021).

[18]

P. Kerschke, H.H. Hoos, F. Neumann, and H. Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (March 2019), 3--45.

Digital Library

[19]

P. Kerschke and H. Trautmann. 2016. The R-Package FLACCO for exploratory landscape analysis with applications to multi-objective optimization problems. In CEC. 5262--5269.

Digital Library

[20]

Ana Kostovska, Diederick Vermetten, Carola Doerr, Saso Dzeroski, Panče Panov, and Tome Eftimov. 2021. OPTION: OPTImization Algorithm Benchmarking ONtology. In Genetic and Evolutionary Computation Conference (GECCO 2021, Companion Material).

Digital Library

[21]

Ana Kostovska, Diederick Vermetten, Sašo Džeroski, Carola Doerr, Peter Korošec, and Tome Eftimov. 2022. Linking Problem Landscape Features with the Performance of Individual CMA-ES Modules - Data.

[22]

Ana Kostovska, Diederick Vermetten, Sašo Džeroski, Carola Doerr, Peter Korošec, and Tome Eftimov. 2022. Linking Problem Landscape Features with the Performance of Individual CMA-ES Modules - Data and Code. https://github.com/KostovskaAna/LinkingELAToPerformance

[23]

Scott M Lundberg and Su-In Lee. 2017. A unified approach to interpreting model predictions. Advances in neural information processing systems 30 (2017).

[24]

Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In Proc. of Genetic and Evolutionary Computation (GECCO'11). ACM, 829--836.

Digital Library

[25]

O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs, and G. Rudolph. 2011. Exploratory Landscape Analysis. In Genetic and Evolutionary Computation Conference (GECCO). ACM, 829--836.

[26]

Christoph Molnar. 2020. Interpretable machine learning. Lulu. com.

[27]

Mario A Muñoz, Michael Kirley, and Saman K Halgamuge. 2012. A meta-learning prediction model of algorithm performance for continuous optimization problems. In International Conference on Parallel Problem Solving from Nature. Springer, 226--235.

[28]

Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. 2011. Scikit-learn: Machine learning in Python. the Journal of machine Learning research 12 (2011), 2825--2830.

[29]

Raphael Patrick Prager, Heike Trautmann, Hao Wang, Thomas HW Bäck, and Pascal Kerschke. 2020. Per-Instance Configuration of the Modularized CMA-ES by Means of Classifier Chains and Exploratory Landscape Analysis. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 996--1003.

[30]

Quentin Renau, Carola Doerr, Johann Dreo, and Benjamin Doerr. 2020. Experimental Data Set for the study "Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy".

[31]

Risto Trajanov, Stefan Dimeski, Martin Popovski, Peter Korošec, and Tome Eftimov. 2021. Explainable Landscape-Aware Optimization Performance Prediction. In 2021 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 01--08.

[32]

Sander Van Rijn, Carola Doerr, and Thomas Bäck. 2018. Towards an adaptive CMA-ES configurator. In International Conference on Parallel Problem Solving from Nature. Springer, 54--65.

[33]

Sander van Rijn, Hao Wang, Matthijs van Leeuwen, and Thomas Bäck. 2016. Evolving the structure of Evolution Strategies. In Proc. of IEEE Symposium Series on Computational Intelligence (SSCI'16). IEEE, 1--8.

[34]

Sander van Rijn, Hao Wang, Bas van Stein, and Thomas Bäck. 2017. Algorithm Configuration Data Mining for CMA Evolution Strategies. In GECCO. ACM, 737--744.

Digital Library

[35]

Diederick Vermetten, Sander van Rijn, Thomas Bäck, and Carola Doerr. 2019. Online selection of CMA-ES variants. In Proceedings of the Genetic and Evolutionary Computation Conference. 951--959.

Digital Library

[36]

Diederick Vermetten, Hao Wang, Carola Doerr, and Thomas Back. 2020. Integrated vs. sequential approaches for selecting and tuning CMA-ES variants. In ACM Genetic and Evolutionary Computation Conference (GECCO'20).

Digital Library

[37]

Hao Wang, Michael Emmerich, and Thomas Bäck. 2014. Mirrored Orthogonal Sampling with Pairwise Selection in Evolution Strategies. In SAC. ACM, 154--156.

Digital Library

[38]

Furong Ye, Hao Wang, Carola Doerr, and Thomas Bäck. 2020. Benchmarking a (μ + λ) Genetic Algorithm with Configurable Crossover Probability. In Parallel Problem Solving from Nature - PPSN XVI - 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 12270), Thomas Bäck, Mike Preuss, André H. Deutz, Hao Wang, Carola Doerr, Michael T. M. Emmerich, and Heike Trautmann (Eds.). Springer, 699--713.

Digital Library

Cited By

Bäck TKononova Avan Stein BWang HAntonov KKalkreuth Rde Nobel JVermetten Dde Winter RYe F(2023)Evolutionary Algorithms for Parameter Optimization—Thirty Years LaterEvolutionary Computation10.1162/evco_a_0032531:2(81-122)Online publication date: 1-Jun-2023
https://doi.org/10.1162/evco_a_00325
Prager RDietrich KSchneider LSchäpermeier LBischl BKerschke PTrautmann HMersmann O(2023)Neural Networks as Black-Box Benchmark Functions Optimized for Exploratory Landscape FeaturesProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607136(129-139)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607136
Kerschke PPreuss MSilva SPaquete L(2023)Exploratory Landscape AnalysisProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595058(990-1007)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595058
Show More Cited By

Index Terms

The importance of landscape features for performance prediction of modular CMA-ES variants
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by regression
    2. Machine learning approaches
      1. Learning latent representations
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Explainable Landscape Analysis in Automated Algorithm Performance Prediction
Applications of Evolutionary Computation
Abstract
Predicting the performance of an optimization algorithm on a new problem instance is crucial in order to select the most appropriate algorithm for solving that problem instance. For this purpose, recent studies learn a supervised machine learning (...
Limitations of benchmark sets and landscape features for algorithm selection and performance prediction
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Benchmark sets and landscape features are used to test algorithms and to train models to perform algorithm selection or configuration. These approaches are based on the assumption that algorithms have similar performances on problems with similar ...
Benchmarking a BI-population CMA-ES on the BBOB-2009 function testbed
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

We propose a multistart CMA-ES with equal budgets for two interlaced restart strategies, one with an increasing population size and one with varying small population sizes. This BI-population CMA-ES is benchmarked on the BBOB-2009 noiseless function ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Slovenian Research Agency
Paris Ile-de-France region
European Commission

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
105
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bäck TKononova Avan Stein BWang HAntonov KKalkreuth Rde Nobel JVermetten Dde Winter RYe F(2023)Evolutionary Algorithms for Parameter Optimization—Thirty Years LaterEvolutionary Computation10.1162/evco_a_0032531:2(81-122)Online publication date: 1-Jun-2023
https://doi.org/10.1162/evco_a_00325
Prager RDietrich KSchneider LSchäpermeier LBischl BKerschke PTrautmann HMersmann O(2023)Neural Networks as Black-Box Benchmark Functions Optimized for Exploratory Landscape FeaturesProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607136(129-139)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607136
Kerschke PPreuss MSilva SPaquete L(2023)Exploratory Landscape AnalysisProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595058(990-1007)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595058
Herzog JBrest JBošković B(2022)Performance Analysis of Selected Evolutionary Algorithms on Different Benchmark FunctionsBioinspired Optimization Methods and Their Applications10.1007/978-3-031-21094-5_13(170-184)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21094-5_13

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten