Multi-configuration automatique d'algorithmes pour l'optimisation combinatoire

Abstract

Les métaheuristiques sont des algorithmes de résolution présentant un grand nombre de paramètres qui leur permettent de s'adapter à tout type de problème d'optimisation. Afin d'obtenir les meilleures performances, les paramètres doivent être choisis scrupuleusement ce qui engendre un travail de paramétrage très fastidieux. C'est dans ce contexte qu'ont été développées dans la littérature les approches de réglage de paramètres où une phase d'apprentissage permet d'explorer différents jeux de paramètres pour sélectionner le meilleur, et de contrôle de paramètres où les valeurs changent de manière adaptative pendant l'exécution. Dans cette thèse, nous proposons d'utiliser simultanément ces deux approches de paramétrage en proposant une approche appelée multi-configuration automatique d'algorithmes. En particulier, nous explorons plusieurs stratégies basées sur des modèles séquentiels ou probabilistes et nous les comparons aux approches classiques de la configuration automatique d'algorithmes et d'algorithmes adaptatifs. Des expérimentations ont été conduites sur le problème d'ordonnancement de type flowshop de permutation et le problème de voyageur de commerce et montrent la pertinence de l'approche proposée.