Analyse de paysage multi-objectif et sélection automatique d’algorithmes

Abstract

Cette thèse porte sur l'analyse de paysage de problèmes d'optimisation combinatoires multi-objectifs. La résolution de tels problèmes est une tâche difficile, particulièrement en optimisation multi-objectif en raison de la nature contradictoire des objectifs. Ces situations apparaissent fréquemment dans de nombreux scénarios réels et constituent un véritable défi pour les algorithmes. Les approches de résolution reposent sur la découverte de solutions qui forment des compromis intéressants. Parmi ces approches, les algorithmes évolutionnaires s'avèrent particulièrement adaptés. Cependant, il existe de nombreux algorithmes évolutionnaires et leur performance varie en fonction du problème à résoudre.Dans cette thèse, nous cherchons à comprendre la raison de ces variations et à déterminer l'algorithme le plus intéressant pour un problème donné. Pour cela, nous nous intéressons particulièrement à l'étude des caractéristiques internes aux instances de problèmes. Cette étude porte sur l'analyse de paysage de problèmes d'optimisation multi-objectifs. L'analyse de paysage permet de caractériser les structures locales internes à un problème d'optimisation. L'intérêt est à la fois fondamental, pour mieux comprendre les difficultés des algorithmes. De plus, elle offre un intérêt pour l'automatisation de la sélection d'algorithmes. Cet aspect pratique est tout particulièrement important, puisqu'il permet de choisir l'algorithme le plus performant pour un problème non rencontré auparavant.Dans un premier temps, nous proposons une approche d'analyse de paysage par décomposition de problèmes multi-objectifs. Cette approche est alors étudiée sur une collection de problèmes d'optimisation aux caractéristiques connues. L'approche est ensuite appliquée expérimentalement pour sélectionner automatiquement le meilleur algorithme pour un problème donné. Dans un troisième temps, les investigations précédentes sont approfondies, notamment sur le coût de l'analyse du paysage et sa prise en compte dans le modèle de sélection. Enfin, une nouvelle collection de problèmes combinatoiresmulti-objectifs est proposée. Elle apporte un nouveau critère de difficulté pour les algorithmes : l'hétérogénéité entre les objectifs. Nous montrons que cette nouvelle propriété est observable par le biais de l'analyse de paysage par décomposition.