Note ABES Algorithm Selection for Multi-Objective Optimization Sélection d’algorithme pour l’optimisation multi-objectif Sélection automatique d'algorithme Optimisation multi-Objectif Algorithmes anytime Approches exactes Heuristiques Algorithm selection Multi-Objective optimization Anytime algorithms Exact algorithms Heuristics Optimisation combinatoire Métaheuristiques Problème du sac à dos Les problèmes d'optimisation multi-objectifs, pour lesquels plusieurs objectifs doivent être optimisés, peuvent survenir dans de nombreux scénarios réels, par exemple lorsque l'on essaie de minimiser à la fois le coût et le temps nécessaires pour se déplacer entre deux emplacements. Au cours des dernières décennies, de nombreux algorithmes ont été proposés afin de résoudre des problèmes d'optimisation multi-objectifs. Ces algorithmes peuvent avoir des comportements très distincts et leurs performances sont souvent affectées de manière significative par l'instance du problème à résoudre, le budget temps disponible pour la résolution, ou encore la qualité de solution souhaitée. Ainsi, l'algorithme qui fonctionne le mieux dépend souvent du scénario envisagé.Cela donne lieu au problème de sélection d'algorithme, qui concerne la sélection automatique du meilleur algorithme pour un scénario donné. Dans cette thèse, nous étudions le cas de la sélection automatique du meilleur algorithme d'optimisation multi-objectifs pour résoudre une instance de problème non-rencontrée auparavant, en tenant compte du fait que le budget temps disponible et la qualité de solution souhaitée peuvent être incertains, et ne sont connus qu'à l'étape de la sélection de l'algorithme. Nous apportons plusieurs contributions dans cette voie.Dans un premier temps, nous proposons des modèles théoriques et empiriques pour caractériser la performance "anytime" d'un algorithme, c'est-à-dire comment la qualité de solution s'améliore au fil du temps, pour des instances de problème non-rencontrées auparavant. Ensuite, en considérant ces modèles, nous développons une méthodologie de sélection hors ligne afin de sélectionner le meilleur algorithme étant donné une fonction d'utilité qui décrit le budget temps et la qualité de solution souhaités. Nous proposons également une méthodologie de sélection en ligne qui peut basculer entre des stratégies de branch and bound multi-objectifs pour améliorer les performances "anytime". Enfin, nous proposons une technique de scalarisation et une stratégie de branch and bound pour l'optimisation multi-objectifs afin d'obtenir une meilleure performance "anytime" que les approches précédentes. Chaque contribution est étayée par une étude expérimentale sur un problème de sac à dos multi-objectifs, et les résultats mettent en évidence la qualité des modèles, des méthodologies de sélection et des algorithmes proposés. Multi-objective optimization problems, which consider multiple objective functions to be optimized, can arise in many real-life scenarios, e.g., when trying to minimize both the cost and the time needed for traveling between two locations. In the last few decades, several algorithms have been proposed to solve multi-objective optimization problems. These algorithms can have very distinct behaviors, and their performance is often significantly affected by the problem instance to be solved, the time budget available, or the desirable solution quality. As such, which algorithm performs best often depends on the scenario that is being considered.This gives rise to the algorithm selection problem, which is concerned with the automatic selection of the best algorithm for a given scenario. In this thesis, we investigate the case of automatically selecting the best multi-objective optimization algorithm to solve a previously unseen problem instance, taking into account that the available time budget and desirable solution quality may be uncertain, and are only known when selecting the algorithm. We make several contributions in this line.First, we propose theoretical and empirical models to characterize the anytime performance of an algorithm, i.e., how solution quality improves over time, for previously unseen problem instances. Then, considering these models, we develop an offline selection methodology to select the best algorithm for a previously unseen problem instance given a utility function that describes the desirable time budget and solution quality. We also propose an online selection methodology that can swap between multi-objective branch and bound strategies to improve anytime performance. Lastly, we propose a scalarization technique and a branch and bound search strategy for multi-objective optimization problems to achieve a better anytime performance than previous approaches. Each contribution is backed by an experimental study on a multi-objective knapsack problem, and the results highlight the quality of the proposed models, selection methodologies, and algorithms. Electronic Thesis or Dissertation Text en PDF 14758759 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2022/2022ULILB054.pdf https://theses.fr/2022ULILB054/abes Borges de Jesus Alexandre Daniel Borges de Jesus 1992-01-17 PT 284528552 https://theses.fr/2022ULILB054 2022ULILB054 https://doi.org/10.70675/ba4bfc9fz2cb9z4978zbd26zef9f9a893288 2022-12-09 Informatique et applications Université de Lille (2022-....) 259265152 Universidade de Coimbra (Portugal) MADS_ETABLISSEMENT_DE_COTUTELLE_1 026430339 Doctorat Docteur es non oui Derbel Bilel MADS_DIRECTEUR_DE_THESE_1 118810758 Paquete Luis MADS_DIRECTEUR_DE_THESE_2 280198779 Madeira Henrique MADS_PRESIDENT_DU_JURY 284527521 Hao Jin-Kao MADS_MEMBRE_DU_JURY_1 06152963X Semet Frédéric MADS_MEMBRE_DU_JURY_2 084649461 Lourenço Nuno MADS_MEMBRE_DU_JURY_3 258266279 Emmerich Michael MADS_RAPPORTEUR_1 166436992 Lynce Inês MADS_RAPPORTEUR_2 25487813X École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 258621362 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X ddc:004 Universidade de Coimbra (Portugal) Derbel Bilel Paquete Luis Madeira Henrique Hao Jin-Kao Semet Frédéric Lourenço Nuno Emmerich Michael Lynce Inês École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre de Recherche en Informatique, Signal et Automatique de Lille PDF 14758759