On the Utility of Probing Trajectories for Algorithm-Selection

Renau, Quentin; Hart, Emma

Abstract

Machine-learning approaches to algorithm-selection typically take data describing an instance as input. Input data can take the form of features derived from the instance description or fitness landscape , or can be a direct representation of the instance itself, i.e. an image or textual description. Regardless of the choice of input, there is an implicit assumption that instances that are similar will elicit similar performance from algorithm, and that a model is capable of learning this relationship. We argue that viewing algorithm-selection purely from an instance perspective can be misleading as it fails to account for how an algorithm 'views' similarity between instances. We propose a novel 'algorithm-centric' method for describing instances that can be used to train models for algorithm-selection: specifically, we use short probing trajectories calculated by applying a solver to an instance for a very short period of time. The approach is demonstrated to be promising , providing comparable or better results to computationally expensive landscape-based feature-based approaches. Furthermore, projecting the trajectories into a 2-dimensional space illustrates that functions that are similar from an algorithm-perspective do not necessarily correspond to the accepted categorisation of these functions from a human perspective.

Citation

Renau, Q., & Hart, E. (2024). On the Utility of Probing Trajectories for Algorithm-Selection. In Applications of Evolutionary Computation. EvoApplications 2024 (98-114). https://doi.org/10.1007/978-3-031-56852-7_7

• Conference Name: EvoStar 2024
• Conference Location: Aberystwyth, UK
• Start Date: Apr 3, 2024
• End Date: Apr 5, 2024
• Acceptance Date: Jan 10, 2024
• Online Publication Date: Mar 21, 2024
• Publication Date: 2024
• Deposit Date: Feb 7, 2024
• Publicly Available Date: Mar 22, 2025
• Publisher: Springer
• Pages: 98-114
• Series Title: Lecture Notes in Computer Science
• Series Number: vol.14634
• Series ISSN: 0302-9743
• Book Title: Applications of Evolutionary Computation. EvoApplications 2024
• ISBN: 978-3-031-56851-0
• DOI: https://doi.org/10.1007/978-3-031-56852-7_7
• Keywords: Algorithm Selection, Black-Box Optimisation, Algorithm Trajectory
• Public URL: http://researchrepository.napier.ac.uk/Output/3504017