Young Researcher and Innovator Conference Grant

Efficient Online Automated Algorithm Selection in the Face of Data-Drift in Optimisation Problem Instances

Jeroen Rook, Paderborn University, Paderborn, Germany, and University of Twente, Enschede, Netherlands
Quentin Renau, Edinburgh Napier University, Edinburgh, Scotland, United Kingdom
Heike Trautmann, Paderborn University, Paderborn, Germany, and University of Twente, Enschede, Netherlands
Emma Hart, Edinburgh Napier University, Edinburgh, Scotland, United Kingdom

18th ACM/SIGEVO Conference on Foundations of Genetic Algorithms FOGA XVIII
Leiden, Netherlands
27-29 August 2025

Grantee: Quentin Renau, Edinburgh Napier University, Edinburgh, United Kingdom
Type of publication: Full paper
Type of presentation: Poster

Start date: 2025-08-26
End date: 2025-08-29
Awarded: 2025-07-25
Report approved: 2025-10-31

Abstract

In many real-world problems, instances arrive in a stream which is likely to experience drift in the instance space over time. If a classical algorithm selector is trained offline, i.e., on an initial part of the instance stream, downstream performance is often negatively impacted due to drift in the instance data. To overcome this limitation of classical algorithm selectors, we propose a novel online automated algorithm selection framework that first uses instance features to detect drift, and then periodically retrains a selector if drift occurs, ensuring continuity of performance in face of data-drift. To further improve both the effectiveness and efficiency of retraining, we also propose a process to continuously gather new training samples on the fly. Empirical comparison using a bin-packing scenario under three different drift scenarios shows that our framework is efficient in terms of the computational effort required to train a selector while maintaining good performance with respect to accuracy compared to several baselines.