Multi-Objective Landscape Analysis and Feature-based Algorithm Selection
Analyse de paysage multi-objectif et sélection automatique d’algorithmes
Résumé
This thesis focuses on landscape analysis for multi-objectivecombinatorial optimization problems. Solving such problems is adifficult task, especially in a multi-objective setting, due to theconflicting nature of the involved objectives. Moreover, in a black-box setting,no knowledge about the problem can be assumed, and one can only probethe objective functions to evaluate the quality of solutions. In such a setting,evolutionary algorithms constitute a popular solvingapproach. However, one can find different evolutionary algorithms, with differentcomponents and parameters, leading to different performances depending on the problem being solved.Understanding the difference in performance, and determining the mostinteresting algorithm (or component) for a given problem instance requires studying itsintrinsic characteristics. In this context, fitness landscape analysis has a fundamental interestas it helps to gain a fundamental understanding of what makes a problem difficult to solve. In addition,it offers new opportunities for automated algorithm selection, when one has to decide the best algorithmto execute for an unseen problem.In this thesis, we propose a new landscape analysis methodology using thedecomposition paradigm for multi-objective problems. We study thisapproach for a set of optimization problems with knowncharacteristics. The method is subsequently investigated on morecomplex tasks, in particular for solving the algorithm selection problem. Then, we push ourexperiments further with a study on the cost of the landscape analysis it-self.Further cost reduction is achieved by modifying the sampling methodsnecessary for landscape analysis while maintaining a degree ofrobustness of the proposed landscape features. Finally, a new collection of multi-objectivecombinatorial problems is proposed, bringing a new challenge foralgorithms by including heterogeneity between objectives. We show thatthis property is observable through decomposition-based landscapeanalysis.
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.
Origine : Version validée par le jury (STAR)