PhD graduated
Team : RO
Departure date : 08/31/2023

Supervision : Carola DOERR

Towards Online Landscape-Aware Algorithm Selection in Numerical Black-Box Optimization

Black-box optimization algorithms (BBOAs) are conceived for settings in which exact problem formulations are non-existent or inaccessible, or in which problems are too complex to be solved analytically, thus requiring users to treat it as a black box. In those scenarios, BBOAs are essentially the only means of finding a good solution to such a problem. Due to their general applicability, BBOAs can exhibit different behaviors when optimizing different types of problems. This yields a meta-optimization problem of choosing the best suited algorithm for a particular problem at hand, called the algorithm selection problem.
By reason of inherent bias and limited knowledge of the complex relationship between algorithms, problems, and performance, a manual selection of the algorithms is undesirable. In consequence, the vision of automating the selection process has quickly gained traction in the evolutionary computation community. One prominent way of doing so is via so-called landscape-aware algorithm selection, where the choice of the algorithm is based on predicting its performance by means of numerical problem instance representations called features. There exists a large body of work in this very domain. However, a key challenge that landscape-aware algorithm selection faces is the computational overhead of extracting the features, a step typically designed to precede the actual optimization, which reduces the computational budget that can be allocated to the optimization algorithm.
In this thesis, we propose a novel trajectory-based landscape-aware algorithm selection approach which incorporates the feature extraction step within the optimization process. We show that the features computed using the search trajectory samples can lead to very robust and reliable predictions of algorithm performance, and consequently to powerful algorithm selection models built atop. We also present several preparatory analyses, including a novel perspective of combining two complementary regression strategies that outperforms any of the classical, single regression models, to amplify the quality of the final selector.

Defence : 12/17/2021

Jury members :

Marie-Eléonore Kessaci, Université de Lille – CRIStAL [Rapporteur]
Heike Trautmann, University of Münster – Department of Information Systems [Rapporteur]
Jamal Atif, Université Paris-Dauphine – LAMSADE
Evripidis Bampis, Sorbonne Université – LIP6
Christoph Dürr, CNRS, Sorbonne Université – LIP6
Alberto Tonda, INRAE, AgroParisTech – EKINOCS
Carola Doerr, CNRS, Sorbonne Université - LIP6

Departure date : 08/31/2023

2019-2023 Publications