Real-time algorithm configuration

This dissertation presents a number of contributions to the field of algorithm configur- ation. In particular, we present an extension to the algorithm configuration problem, real-time algorithm configuration, where configuration occurs online on a stream of instances, without the need for prior training, and problem solutions are returned in the shortest time possible. We propose a framework for solving the real-time algorithm configuration problem, ReACT. With ReACT we demonstrate that by using the parallel computing architectures, commonplace in many systems today, and a robust aggregate ranking system, configuration can occur without any impact on performance from the perspective of the user. This is achieved by means of a racing procedure. We show two concrete instantiations of the framework, and show them to be on a par with or even exceed the state-of-the-art in offline algorithm configuration using empirical evaluations on a range of combinatorial problems from the literature. We discuss, assess, and provide justification for each of the components used in our framework instantiations. Specifically, we show that the TrueSkill ranking system commonly used to rank players’ skill in multiplayer games can be used to accurately es- timate the quality of an algorithm’s configuration using only censored results from races between algorithm configurations. We confirm that the order that problem instances arrive in influences the configuration performance and that the optimal selection of configurations to participate in races is dependent on the distribution of the incoming in- stance stream. We outline how to maintain a pool of quality configurations by removing underperforming configurations, and techniques to generate replacement configurations with minimal computational overhead. Finally, we show that the configuration space can be reduced using feature selection techniques from the machine learning literature, and that doing so can provide a boost in configuration performance.

Grantor dc:publisher

University College Cork

Year dc:date.issued

2021

Author dc:creator

• Fitzgerald, Tadhg

Advisors dc:contributor.advisor

• O'Sullivan, Barry
• Brown, Kenneth

• Optimisation
• Algorithm configuration

Statement dc:rights

• © 2021, Tadhg Fitzgerald.

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/10468/11303

OAI identifier oai:identifier

oai:cora.ucc.ie:10468/11303