Skip to main content

Research Repository

Advanced Search

On the Utility of Probing Trajectories for Algorithm-Selection

Renau, Quentin; Hart, Emma

Authors



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.

Presentation Conference Type Conference Paper (Published)
Conference Name EvoStar 2024
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

Files

This file is under embargo until Mar 22, 2025 due to copyright reasons.

Contact repository@napier.ac.uk to request a copy for personal use.






You might also like



Downloadable Citations