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

research-article

Open access

Large-Scale Benchmarking of Metaphor-Based Optimization Heuristics

Authors:

Diederick Vermetten,

Anna V. Kononova,

Thomas BäckAuthors Info & Claims

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

Pages 41 - 49

https://doi.org/10.1145/3638529.3654122

Published: 14 July 2024 Publication History

Abstract

The number of proposed iterative optimization heuristics is growing steadily, and with this growth, there have been many points of discussion within the wider community. One particular criticism that is raised towards many new algorithms is their focus on metaphors used to present the method, rather than emphasizing their potential algorithmic contributions. Several studies into popular metaphor-based algorithms have highlighted these problems, even showcasing algorithms that are functionally equivalent to older existing methods. Unfortunately, this detailed approach is not scalable to the whole set of metaphor-based algorithms. Because of this, we investigate ways in which benchmarking can shed light on these algorithms. To this end, we run a set of 294 algorithm implementations on the BBOB function suite. We investigate how the choice of the budget, the performance measure, or other aspects of experimental design impact the comparison of these algorithms. Our results emphasize why benchmarking is a key step in expanding our understanding of the algorithm space, and what challenges still need to be overcome to fully gauge the potential improvements to the state-of-the-art hiding behind the metaphors.

References

[1]

Claus Aranha, Christian Leonardo Camacho-Villalón, Felipe Campelo, Marco Dorigo, Rubén Ruiz, Marc Sevaux, Kenneth Sörensen, and Thomas Stützle. 2022. Metaphor-based metaheuristics, a call for action: the elephant in the room. Swarm Intell. 16, 1 (2022), 1--6.

[2]

Thomas Bäck, David B Fogel, and Zbigniew Michalewicz. 1997. Handbook of evolutionary computation. Release 97, 1 (1997), B1.

[3]

Christian Leonardo Camacho-Villalón, Marco Dorigo, and Thomas Stützle. 2019. The intelligent water drops algorithm: why it cannot be considered a novel algorithm - A brief discussion on the use of metaphors in optimization. Swarm Intell. 13, 3-4 (2019), 173--192.

[4]

Christian L Camacho-Villalón, Marco Dorigo, and Thomas Stützle. 2021. PSO-X: A component-based framework for the automatic design of particle swarm optimization algorithms. IEEE Transactions on Evolutionary Computation 26, 3 (2021), 402--416.

[5]

Christian L Camacho-Villalón, Marco Dorigo, and Thomas Stützle. 2022. An analysis of why cuckoo search does not bring any novel ideas to optimization. Computers & Operations Research 142 (2022), 105747.

Digital Library

[6]

Christian Leonardo Camacho-Villalón, Thomas Stützle, and Marco Dorigo. 2020. Grey Wolf, Firefly and Bat Algorithms: Three Widespread Algorithms that Do Not Contain Any Novelty. In Proc. of Swarm Intelligence (ANTS) (LNCS, Vol. 12421). Springer, 121--133.

[7]

Felipe Campelo and Claus Aranha. 2023. Lessons from the evolutionary computation bestiary. Artificial Life 29, 4 (2023), 421--432.

[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). ACM, 1375--1384.

Digital Library

[9]

Jacob de Nobel, Furong Ye, Diederick Vermetten, Hao Wang, Carola Doerr, and Thomas Bäck. 2023. Iohexperimenter: Benchmarking platform for iterative optimization heuristics. Evolutionary Computation (2023), 1--6.

[10]

Gustavo H de Rosa, Douglas Rodrigues, and João P Papa. 2019. Opytimizer: A nature-inspired python optimizer. arXiv preprint arXiv:1912.13002 (2019).

[11]

Javier Del Ser, Eneko Osaba, Aritz D Martinez, Miren Nekane Bilbao, Javier Poyatos, Daniel Molina, and Francisco Herrera. 2021. More is not always better: insights from a massive comparison of meta-heuristic algorithms over real-parameter optimization problems. In 2021 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 1--7.

[12]

Carola Doerr, Furong Ye, Sander van Rijn, Hao Wang, and Thomas Bäck. 2018. Towards a theory-guided benchmarking suite for discrete black-box optimization heuristics: profiling (1 + λ) EA variants on OneMax and LeadingOnes. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 951--958.

Digital Library

[13]

Marco Dorigo. 1992. Optimization, Learning and Natural Algorithms. Ph.D. Dissertation. Politecnico di Milano.

[14]

Hossam Faris, Ibrahim Aljarah, Seyedali Mirjalili, Pedro A Castillo, and Juan Julián Merelo Guervós. 2016. EvoloPy: An open-source nature-inspired optimization framework in python. IJCCI (ECTA) 1 (2016), 171--177.

[15]

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

[16]

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

[17]

James Kennedy and Russell Eberhart. 1995. Particle swarm optimization. In Proc. of ICNN'95 - International Conference on Neural Networks, Vol. 4. 1942--1948.

[18]

Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (2019), 3--45.

Digital Library

[19]

Anna V Kononova, Diederick Vermetten, Fabio Caraffini, Madalina-A Mitran, and Daniela Zaharie. 2023. The importance of being constrained: Dealing with in-feasible solutions in differential evolution and beyond. Evolutionary Computation (2023), 1--46.

[20]

Jakub Kudela. 2023. The Evolutionary Computation Methods No One Should Use. arXiv preprint arXiv:2301.01984 (2023).

[21]

Manuel López-Ibáñez, Juergen Branke, and Luís Paquete. 2021. Reproducibility in evolutionary computation. ACM Transactions on Evolutionary Learning and Optimization 1, 4 (2021), 1--21.

Digital Library

[22]

Manuel López-Ibáñez, Diederick Vermetten, Johann Dreo, and Carola Doerr. 2024. Using the Empirical Attainment Function for Analyzing Single-objective Black-box Optimization Algorithms. arXiv:2404.02031

[23]

Zhongqiang Ma, Guohua Wu, Ponnuthurai Nagaratnam Suganthan, Aijuan Song, and Qizhang Luo. 2023. Performance assessment and exhaustive listing of 500+ nature-inspired metaheuristic algorithms. Swarm and Evolutionary Computation 77 (2023), 101248.

[24]

Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018).

[25]

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 Conference (GECCO). ACM, 829--836.

Digital Library

[26]

Laurent Meunier, Herilalaina Rakotoarison, Pak-Kan Wong, Baptiste Rozière, Jérémy Rapin, Olivier Teytaud, Antoine Moreau, and Carola Doerr. 2022. Black-Box Optimization Revisited: Improving Algorithm Selection Wizards Through Massive Benchmarking. IEEE Trans. Evol. Comput. 26, 3 (2022), 490--500. Free version available at https://arxiv.org/abs/2010.04542.

[27]

Jérémy Rapin and Olivier Teytaud. 2018. Nevergrad - A gradient-free optimization platform. https://GitHub.com/FacebookResearch/Nevergrad.

[28]

Kenneth Sörensen. 2015. Metaheuristics - the metaphor exposed. International Transactions in Operational Research (ITOR) 22 (2015), 3--18.

[29]

Kenneth Sörensen, Marc Sevaux, and Fred W. Glover. 2018. A History of Metaheuristics. In Handbook of Heuristics, Rafael Martí, Panos M. Pardalos, and Mauricio G. C. Resende (Eds.). Springer, 791--808.

[30]

Ryoji Tanabe and Alex S Fukunaga. 2014. Improving the search performance of SHADE using linear population size reduction. In 2014 IEEE congress on evolutionary computation (CEC). IEEE, 1658--1665.

[31]

Niki van Stein, Diederick Vermetten, Anna V. Kononova, and Thomas Bäck. 2024. Explainable Benchmarking for Iterative Optimization Heuristics. arXiv:2401.17842 [cs.NE]

[32]

Nguyen Van Thieu and Seyedali Mirjalili. 2023. MEALPY: An open-source library for latest meta-heuristic algorithms in Python. Journal of Systems Architecture 139 (2023), 102871.

Digital Library

[33]

Luis Velasco, Hector Guerrero, and Antonio Hospitaler. 2023. A Literature Review and Critical Analysis of Metaheuristics Recently Developed. Archives of Computational Methods in Engineering (2023), 1784--1886.

[34]

Diederick Vermetten, Fabio Caraffini, Anna V. Kononova, and Thomas Bäck. 2023. Modular Differential Evolution. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, Lisbon, Portugal, July 15-19, 2023, Sara Silva and Luís Paquete (Eds.). ACM, 864--872.

Digital Library

[35]

Diederick Vermetten, Carola Doerr, Hao Wang, Anna V Kononova, and Thomas Bäck. 2024. Reproducibility files and additional figures. (2024). Code and data repository (Zenodo) Figure repository (Figshare): doi.org/10.6084/m9.figshare.25060151.

[36]

Diederick Vermetten, Sander van Rijn, Thomas Bäck, and Carola Doerr. 2019. Online selection of CMA-ES variants. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 951--959. Free version available at https://arxiv.org/abs/1904.07801.

Digital Library

[37]

Diederick Vermetten, Hao Wang, Thomas Bäck, and Carola Doerr. 2020. Towards dynamic algorithm selection for numerical black-box optimization: investigating BBOB as a use case. In Proc. of Genetic and Evolutionary Computation Conference (GECCO). ACM, 654--662. Free version available at https://arxiv.org/abs/2006.06586.

Digital Library

[38]

Grega Vrbančič, Lucija Brezočnik, Uroš Mlakar, Dušan Fister, and Iztok Fister. 2018. NiaPy: Python micro framework for building nature-inspired algorithms. Journal of Open Source Software 3, 23 (2018), 613.

[39]

Hao Wang, Diederick Vermetten, Furong Ye, Carola Doerr, and Thomas Bäck. 2022. IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics. ACM Trans. Evol. Learn. Optim. 2, Article 3 (2022). Free version available at https://arxiv.org/abs/2007.03953.

Digital Library

[40]

Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. 2008. SATzilla: portfolio-based algorithm selection for SAT. Journal of artificial intelligence research 32 (2008), 565--606.

Cited By

Halsema MVermetten DBäck TVan Stein NLi XHandl J(2024)A Critical Analysis of Raven Roost OptimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664124(1993-2001)Online publication date: Aug-2024
https://doi.org/10.1145/3638530.3664124
van Stein NThomson SKononova A(2024)A Deep Dive Into Effects of Structural Bias on CMA-ES Performance Along Affine TrajectoriesParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_3(36-50)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_3
Vermetten DLengler JRusin DBäck TDoerr C(2024)Empirical Analysis of the Dynamic Binary Value Problem with IOHprofilerParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_2(20-35)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_2
Show More Cited By

Index Terms

Large-Scale Benchmarking of Metaphor-Based Optimization Heuristics
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Bio-inspired optimization

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2024

1657 pages

ISBN:9798400704949

DOI:10.1145/3638529

Chair:
Xiaodong Li,
Program Chair:
Julia Handl

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 July 2024

Check for updates

Qualifiers

Research-article

Funding Sources

CNRS Sciences informatiques

Conference

GECCO '24

Sponsor:

SIGEVO

GECCO '24: Genetic and Evolutionary Computation Conference

July 14 - 18, 2024

VIC, Melbourne, Australia

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
207
Total Downloads

Downloads (Last 12 months)207
Downloads (Last 6 weeks)38

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Halsema MVermetten DBäck TVan Stein NLi XHandl J(2024)A Critical Analysis of Raven Roost OptimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664124(1993-2001)Online publication date: Aug-2024
https://doi.org/10.1145/3638530.3664124
van Stein NThomson SKononova A(2024)A Deep Dive Into Effects of Structural Bias on CMA-ES Performance Along Affine TrajectoriesParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_3(36-50)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_3
Vermetten DLengler JRusin DBäck TDoerr C(2024)Empirical Analysis of the Dynamic Binary Value Problem with IOHprofilerParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_2(20-35)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70068-2_2
Thomson SOchoa Gvan den Berg DLiang TWeise T(2024)Entropy, Search Trajectories, and Explainability for Frequency Fitness AssignmentParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_23(377-392)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_23

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents