On the Utility of Probing Trajectories for Algorithm-Selection
Quentin Renau Emma Hart
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.