Ana Nikolikj
ABSTRACT
In black-box optimization, it is essential to understand why an algorithm instance works on a set of problem instances while failing on others and provide explanations of its behavior. We propose a methodology for formulating an algorithm instance footprint that consists of a set of problem instances that are easy to be solved and a set of problem instances that are difficult to be solved, for an algorithm instance. This behavior of the algorithm instance is further linked to the landscape properties of the problem instances to provide explanations of which properties make some problem instances easy or challenging. The proposed methodology uses meta-representations that embed the landscape properties of the problem instances and the performance of the algorithm into the same vector space. These meta-representations are obtained by training a supervised machine learning regression model for algorithm performance prediction and applying model explainability techniques to assess the importance of the landscape features to the performance predictions. Next, deterministic clustering of the meta-representations demonstrates that using them captures algorithm performance across the space and detects regions of poor and good algorithm performance, together with an explanation of which landscape properties are leading to it.
- Nacim Belkhir, Johann Dréo, Pierre Savéant, and Marc Schoenauer. 2017. Per instance algorithm configuration of CMA-ES with limited budget. In GECCO. Association for Computing Machinery, New York, NY, USA, 681--688.Google Scholar
- Gérard Biau and Erwan Scornet. 2016. A random forest guided tour. Test 25, 2 (2016), 197--227.Google ScholarCross Ref
- Marcelo de Souza and Marcus Ritt. 2022. Improved regression models for algorithm configuration. In Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery, New York, NY, USA, 222--231.Google ScholarDigital Library
- Joaquín Derrac, Salvador García, Daniel Molina, and Francisco Herrera. 2011. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 1, 1 (2011), 3--18.Google ScholarCross Ref
- Tome Eftimov, Peter Korošec, and Barbara Koroušić Seljak. 2017. A novel approach to statistical comparison of meta-heuristic stochastic optimization algorithms using deep statistics. Information Sciences 417 (2017), 186--215.Google ScholarDigital Library
- Matthias Feurer, Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren. 2019. Hyperparameter Optimization. Springer International Publishing, Cham, 3--33.Google Scholar
- Steffen Finck, Nikolaus Hansen, Raymond Ros, and Anne Auger. 2010. Real-parameter black-box optimization benchmarking 2010: Presentation of the noisy functions. Technical Report. Citeseer.Google Scholar
- Nicholas G Hall and Marc E Posner. 2010. The generation of experimental data for computational testing in optimization. In Experimental methods for the analysis of optimization algorithms. Springer, Berlin, Heidelberg, 73--101.Google Scholar
- Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. 2010. Real-parameter black-box optimization benchmarking 2010: Experimental setup. Ph. D. Dissertation. INRIA.Google Scholar
- 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.Google ScholarCross Ref
- Anja Jankovic, Tome Eftimov, and Carola Doerr. 2021. Towards feature-based performance regression using trajectory data. In EvoApplications. Springer International Publishing, Cham, 601--617.Google Scholar
- Pascal Kerschke, Mike Preuss, Simon Wessing, and Heike Trautmann. 2015. Detecting funnel structures by means of exploratory landscape analysis. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, New York, NY, USA, 265--272.Google ScholarDigital Library
- Pascal Kerschke and Heike Trautmann. 2019. Automated algorithm selection on continuous black-box problems by combining exploratory landscape analysis and machine learning. Evolutionary computation 27, 1 (2019), 99--127.Google Scholar
- Pascal Kerschke and Heike Trautmann. 2019. Comprehensive feature-based landscape analysis of continuous and constrained optimization problems using the R-package flacco. In Applications in Statistical Computing. Springer International Publishing, Cham, 93--123.Google Scholar
- Ana Kostovska, Anja Jankovic, Diederick Vermetten, Jacob de Nobel, Hao Wang, Tome Eftimov, and Carola Doerr. 2022. Per-run algorithm selection with warm-starting using trajectory-based features. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part I. Springer International Publishing, Cham, 46--60.Google Scholar
- Ryan Dieter Lang and Andries Petrus Engelbrecht. 2021. An exploratory landscape analysis-based benchmark suite. Algorithms 14, 3 (2021), 78.Google ScholarCross Ref
- Monte Lunacek and Darrell Whitley. 2006. The dispersion metric and the CMA evolution strategy. In Proceedings of the 8th annual conference on Genetic and evolutionary computation. Association for Computing Machinery, New York, NY, USA, 477--484.Google ScholarDigital Library
- Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018).Google Scholar
- Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory landscape analysis. In GECCO. Association for Computing Machinery, New York, NY, USA, 829--836.Google Scholar
- Mario A Muñoz, Michael Kirley, and Saman K Halgamuge. 2014. Exploratory landscape analysis of continuous space optimization problems using information content. IEEE transactions on evolutionary computation 19, 1 (2014), 74--87.Google Scholar
- Mario A Muñoz and Kate A Smith-Miles. 2017. Performance analysis of continuous black-box optimization algorithms via footprints in instance space. Evolutionary computation 25, 4 (2017), 529--554.Google Scholar
- Ana Nikolikj. 2023. Algorithm Footprints. https://github.com/anikolik/algorithm-footprintsGoogle Scholar
- Ana Nikolikj, Ryan Lang, Peter Korošec, and Tome Eftimov. 2022. Explaining Differential Evolution Performance Through Problem Landscape Characteristics. In Bioinspired Optimization Methods and Their Applications: 10th International Conference, BIOMA 2022, Maribor, Slovenia, November 17--18, 2022, Proceedings. Springer, Cham, 99--113.Google ScholarDigital Library
- William S Noble. 2006. What is a support vector machine? Nature biotechnology 24, 12 (2006), 1565--1567.Google Scholar
- Leif E Peterson. 2009. K-nearest neighbor. Scholarpedia 4, 2 (2009), 1883.Google ScholarCross Ref
- Benedek Rozemberczki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Olivér Kiss, Sebastian Nilsson, and Rik Sarkar. 2022. The shapley value in machine learning. arXiv preprint arXiv:2202.05594 (2022).Google Scholar
- Kate Smith-Miles and Mario Andrés Muñoz. 2022. Instance Space Analysis for Algorithm Testing: Methodology and Software Tools. ACM Comput. Surv. (nov 2022). Just Accepted. Google ScholarDigital Library
- Jörg Stork, Agoston E Eiben, and Thomas Bartz-Beielstein. 2020. A new taxonomy of global optimization algorithms. Natural Computing (2020), 1--24.Google Scholar
- 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.Google ScholarCross Ref
- Risto Trajanov, Stefan Dimeski, Martin Popovski, Peter Korošec, and Tome Eftimov. 2022. Explainable Landscape Analysis in Automated Algorithm Performance Prediction. In International Conference on the Applications of Evolutionary Computation (Part of EvoStar). Springer, Cham, 207--222.Google Scholar
- Joaquin Vanschoren. 2019. Meta-learning. Automated machine learning: methods, systems, challenges (2019), 35--61.Google Scholar
Index Terms
- Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem Instances
Recommendations
BBOB Instance Analysis: Landscape Properties and Algorithm Performance Across Problem Instances
Applications of Evolutionary ComputationAbstractBenchmarking is a key aspect of research into optimization algorithms, and as such the way in which the most popular benchmark suites are designed implicitly guides some parts of algorithm design. One of these suites is the black-box optimization ...
Instance Generation via Generator Instances
Principles and Practice of Constraint ProgrammingAbstractAccess to good benchmark instances is always desirable when developing new algorithms, new constraint models, or when comparing existing ones. Hand-written instances are of limited utility and are time-consuming to produce. A common method for ...
Verifying new instances of the multidemand multidimensional knapsack problem with instance space analysis
AbstractThe optimization literature contains numerous studies defining a problem and showing a state-of-the-art implementation of a solution method. These studies may involve an empirical evaluation of the solution methods but assume the current ...
Highlights- Examine multidemand multidimensional knapsack problem with instance space analysis.
- Propose instance generation method for multidemand, multidimensional knapsack problem.
- Utilize instance space analysis to compare instance ...
Comments