JANKOVIC Anja

doctorant à Sorbonne Université
Équipe : RO
https://webia.lip6.fr/~jankovic/
https://webia.lip6.fr/~jankovic/

Direction de recherche : Carola DOERR

Vers une sélection en ligne d'algorithmes tenant compte du paysage dans l'optimisation numérique de boîte noire

Les algorithmes d’optimisation de boîte noire (BBOA) sont conçus pour des environnements dans lesquels les formulations exactes de problèmes sont inexistantes ou inaccessibles, ou dans lesquels les problèmes sont trop complexes pour être résolus analytiquement, obligeant ainsi les utilisateurs à les traiter comme une boîte noire. Dans ces scénarios, les BBOA sont essentiellement le seul moyen de trouver une bonne solution à un tel problème. En raison de leur applicabilité générale, les BBOA peuvent présenter des comportements différents lors de l’optimisation de différents types de problèmes. Cela donne un problème de méta-optimisation consistant à choisir l’algorithme le mieux adapté à un problème particulier, appelé problème de sélection d’algorithmes.
En raison du biais inhérent et des connaissances limitées sur la relation complexe entre les algorithmes, les problèmes et les performances, une sélection manuelle des algorithmes n’est pas souhaitable. En conséquence, la vision d’automatiser le processus de sélection a rapidement gagné du terrain dans la communauté. Un moyen important de le faire est ce que l’on appelle la sélection d’algorithmes tenant compte du paysage, où le choix de l’algorithme est basé sur la prédiction de ses performances au moyen de représentations numériques d’instances de problèmes appelées caractéristiques. Il existe un grand nombre de travaux dans ce domaine. Cependant, un défi clé auquel la sélection d’algorithmes tenant compte du paysage est confrontée est le coût de calcul de l’extraction des caractéristiques, une étape qui précède l’optimisation, ce qui réduit le budget pouvant être alloué à l’algorithme d’optimisation.
Dans cette thèse, nous proposons une nouvelle approche de sélection d’algorithmes tenant compte du paysage basée sur la trajectoire qui intègre l’étape d’extraction de caractéristiques dans le processus d’optimisation. Nous montrons que les caractéristiques calculées à l’aide des échantillons de trajectoire de recherche peuvent conduire à des prédictions très robustes et fiables des performances des algorithmes, et par conséquent à de puissants modèles de sélection d’algorithmes construits dessus. Nous présentons également plusieurs analyses préparatoires, y compris une nouvelle perspective de combinaison de deux stratégies de régression complémentaires qui surpasse n’importe lequel des modèles classiques de régression simple, pour amplifier la qualité du sélecteur final.

Soutenance : 17/12/2021

Membres du jury :

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

Date de départ : 31/08/2023

Publications 2019-2023