Soutenance mémoire
Optimisation combinatoire multi-objectif
Problèmes d’optimisation multi-objectif
L’optimisation combinatoire consiste à trouver la solution optimale parmi un ensemble discret de solutions appelé espace de décision ou espace de recherche, que l’on note X. L’espace de recherche est associé à un ou plusieurs critères d’évaluation, également appelé objectif, pour former ce que l’on appelle un problème d’optimisation. Lorsque plusieurs objectifs sont à optimiser conjointement, nous nous trouvons alors face à un problème d’optimisation multi-objectif. Nous pouvons définir l’espace objectif Z comme étant l’ensemble des vecteurs objectif réalisables où chaque solution x ∈ X est associé à un vecteur objectif z ∈ Z. Les fonctions objectifs, permettent de donner une valeur qui définira la qualité des solutions présentes dans l’espace de recherche. Un problème d’optimisation multi-objectif est composé de plusieurs fonctions objectifs à optimiser de façon simultanée que l’on note F = (f1, f2,…, fm), où m représente le nombre d’objectifs. Un problème d’optimisation multi-objectif peut être formulé de la façon suivante :
min F(x) = (f1(x),…, fm(x))
tel que x ∈ X
Une fonction f (x) : X → Z est appelée fonction boite-noire lorsqu’on ne connaît pas sa forme analytique. Si les fonctions fi d’un problème multi-objectif sont de type boitenoire, alors on considère que le problème d’optimisation est un problème boite noire. On s’intéresse dans ce manuscrit aux problèmes d’optimisation combinatoire multi-objectif boite-noire. Le fait qu’un problème d’optimisation soit de type boite noire est impactant pour sa résolution, comme on le verra dans la prochaine section.
Contrairement à l’optimisation continue où chaque variable de l’espace de décision X est continue, les variables en optimisation combinatoire sont discrètes. Ces variables peuvent par exemple représenter un ordre d’éléments avec une permutation, comme pour le problème du voyageur de commerce [45]. Elles peuvent également se trouver sous une forme binaire (ou booléenne) pour définir si un élément est inclus ou non dans la solution, comme pour le problème du sac-à-dos [48]. Elles peuvent aussi représenter des valeurs quantitatives ou qualitatives grâce à des valeurs entières. Avec un espace de décision discret, il est donc possible en théorie de lister toutes les solutions possibles de l’espace de recherche si on considère avoir des ressources de calcul illimitées. En pratique, cette approche n’est pas possible car même si l’espace de décision est discret, il est de trop grande taille pour pouvoir énumérer toutes les solutions en un temps raisonnable. Nous nous intéressons dans cette thèse aux problèmes d’optimisation combinatoire considérés comme NP difficile [77]. En optimisation combinatoire, beaucoup de problèmes sont NP-difficiles, et ne permettent pas d’être résolus de façon exacte en un temps de calcul raisonnable. Si un problème est NP-difficile, alors sa contrepartie en optimisation multiobjectif sera également NP-difficile. Même si le problème mono-objectif peut être résolu en un temps polynomial, il arrive que sa contrepartie en optimisation multi-objectif soit tout de même NP-difficile [27].
Résolution de problèmes d’optimisation multi-objectif
Approches de résolution
En optimisation, le décideur est la personne qui souhaite choisir une solution pour répondre au problème auquel il est confronté. La résolution d’un problème d’optimisation multi-objectif a pour but de présenter au décideur la solution qui correspond le mieux à ses préférences. Deux questions essentielles sont à se poser pour choisir la méthode de résolution qui convient le mieux au contexte d’optimisation : Quelle est l’implication du décideur dans le processus de résolution ? Est-ce que le décideur peut se contenter d’une solution proche de la solution optimale ?
Définir le niveau d’implication du décideur
Le décideur peut être impliqué de différentes façons dans la résolution du problème d’optimisation multi-objectif. La méthode de résolution doit alors être choisie en fonction de cette implication, il existe ainsi trois niveaux d’implication :
— a priori : Dans ce cas, le décideur donne ses préférences avant le processus d’optimisation. La formulation et la modélisation des préférences du décideur peut être difficile selon la nature du problème. Il est par exemple courant d’utiliser les préférences du décideur pour modéliser un nouveau problème d’optimisation avec un objectif unique. Cette simplification permet alors d’utiliser une méthode d’optimisation mono-objectif. La difficulté dans cette approche réside dans la modélisation des préférences qui ne doit pas perdre les informations et les caractéristiques du problème multi-objectif initial.
— a posteriori : Le but de cette approche est de trouver (ou approximer) l’ensemble Pareto. Avec cette approche, le décideur intervient seulement à la fin du processus, où il doit choisir, parmi un ensemble de solutions retournées par le processus d’optimisation, la solution qui lui convient le mieux selon ses besoins et ses préférences. Le choix de la solution peut être un choix compliqué car l’ensemble de solutions non-dominées trouvées par l’algorithme peut contenir énormément de solutions, notamment pour les problèmes avec beaucoup d’objectifs.
— interactive : Avec cette approche, le décideur est impliqué durant toute la phase de résolution. Il donne ses préférences pendant l’exécution de la méthode de résolution pour diriger itérativement le processus de recherche dans une direction qu’il aura choisi. Le but de cette approche est d’utiliser toutes les connaissances acquises sur le problème pour se diriger plus rapidement vers une solution répondant aux préférences et besoin du décideur. L’inconvénient est que le décideur doit être disponible pendant tout le processus d’optimisation.
L’approche utilisée sera choisie en fonction de la difficulté du problème et de l’implication du décideur. Dans le contexte de cette thèse, on se concentrera sur les méthodes a posteriori. On considérera ici la résolution d’un problème comme étant l’identification d’une approximation de l’ensemble Pareto. L’approximation de l’ensemble Pareto fait référence aux solutions obtenues par l’algorithme d’optimisation multi-objectif. En effet, comme nous l’avons vu précédemment, il est souvent impossible de trouver toutes les solutions non-dominées d’un problème multi-objectif. Dans ce cas, le but du processus de recherche est de trouver un ensemble de solutions proche de l’ensemble Pareto. En pratique, après avoir obtenu cette approximation, une phase d’aide à la décision permet d’aider le décideur à choisir une solution parmi l’ensemble des solutions non-dominées obtenues. Dans cette thèse, nous nous concentrons uniquement sur l’obtention d’une approximation de l’ensemble Pareto.
Méthode exacte ou méthode approchée ?
Parmi les approches a posteriori, deux grandes familles de méthodes de résolution existent : les méthodes exactes et les méthodes approchées. Les méthodes de résolution exactes en optimisation multi-objectif permettent de garantir l’obtention de l’ensemble Pareto. Ces méthodes sont très coûteuses en ressource de calcul pour les problèmes difficiles. L’algorithme Branch and Bround [85] est un exemple de méthodes exactes existantes. Avec cet algorithme, on est assuré de trouver l’ensemble des solutions non-dominées sans avoir besoin d’énumérer et d’évaluer toutes les solutions de l’espace de décision. Les approches exactes ne sont cependant pas utilisables pour les problèmes boite-noire, pour lesquels on ne connaît pas la forme analytique des fonctions objectifs. Par ailleurs, en optimisation combinatoire multi-objectif, les problèmes rencontrés sont souvent NP-difficiles, ce qui rend les méthodes exactes inutilisables en pratique sur les instances de grande taille. Les méthodes de résolution approchées sont donc utilisées pour pallier les problèmes de performance des méthodes exactes. Les méthodes approchées permettent de trouver des solutions de bonne qualité en un temps de calcul raisonnable. Avec ces méthodes, nous n’avons aucune garantie sur l’obtention de l’ensemble Pareto, le but étant pour les instances les plus compliquées de trouver une approximation de cet ensemble. Les méthodes approchées doivent donc être choisies seulement si le décideur peut se contenter d’une approximation de l’ensemble Pareto.
|
Table des matières
Introduction
1 Optimisation combinatoire multi-objectif par décomposition
1.1 Optimisation combinatoire multi-objectif
1.1.1 Problèmes d’optimisation multi-objectif
1.1.2 Solutions optimales et dominance
1.2 Résolution de problèmes d’optimisation multi-objectif
1.2.1 Approches de résolution
1.2.2 Algorithmes évolutionnaires multi-objectifs
1.3 Algorithmes évolutionnaires multi-objectifs par décomposition
1.3.1 La décomposition dans MOEA/D
1.3.2 Voisinage
1.3.3 Génération des solutions enfants
1.3.4 Mise à jour de la population
1.4 Implémentation modulaire du framework MOEA/D
1.4.1 Les implémentations existantes de MOEA/D
1.4.2 Le framework modulaire : moead-framework
1.5 Analyse de performance et problèmes étudiés
1.5.1 Indicateurs de qualité
1.5.2 Analyse et validation statistique des mesures de performance
1.5.3 Empirical attainment functions
1.5.4 Problèmes étudiés
1.6 Conclusion
2 Répartition des efforts de calculs dans MOEA/D
2.1 Contexte et motivations
2.1.1 La population dans MOEA/D
2.1.2 Répartition adaptative des efforts de calcul
2.2 Étude de l’allocation des efforts de calcul dans MOEA/D
2.2.1 MOEA/D-(µ, λ, sps) : Une reformulation simple pour l’allocation des ressources dans MOEA/D
2.2.2 Discussion et résumé des variantes considérées
2.3 Analyse expérimentale de MOEA/D-(µ, λ, sps)
2.3.1 Protocole expérimental
2.3.2 Étude de la taille de population dans MOEA/D
2.3.3 Étude de l’impact des sous-problèmes situés aux extrémités
2.3.4 Étude du nombre de sous-problèmes à sélectionner
2.3.5 Étude des stratégies de sélection des sous-problèmes
2.3.6 Étude de la taille de population dans MOEA/D-(µ, λ, sps)
2.4 Conclusion
3 Mécanismes d’échappement dans MOEA/D
3.1 Contexte et motivations
3.1.1 Optima locaux en optimisation mono-objectif
3.1.2 Stratégies d’échappement en optimisation mono-objectif
3.1.3 Optima locaux en optimisation multi-objectif
3.2 Intégration d’un mécanisme d’échappement dans MOEA/D
3.2.1 Détection des optima locaux dans MOEA/D
3.2.2 Échappement aux optima locaux dans MOEA/D
3.3 Analyse expérimentale
3.3.1 Protocole
3.3.2 Étude des paramètres de détection
3.3.3 Étude des stratégies de perturbations
3.4 Conclusion
4 Optimisation coûteuse par décomposition assistée par méta-modèle
4.1 Optimisation multi-objectif coûteuse
4.1.1 Contexte et motivations
4.1.2 Méta-modèles pour l’optimisation combinatoire coûteuse
4.2 Un framework pour l’optimisation multi-objectif combinatoire coûteuse par décomposition
4.2.1 Aperçu général du framework S-MCO
4.2.2 Composant #1 : Optimiseurs du méta-modèle
4.2.3 Composant #2 : Stratégies de sélection
4.2.4 Composant #3 : Stratégies de choix pour l’ordre de Walsh
4.3 Analyse expérimentale
4.3.1 Protocole expérimental
4.3.2 Analyse de l’impact des stratégies de sélection sur les optimiseurs du méta-modèle
4.3.3 Analyse des optimiseurs du méta-modèle
4.3.4 Étude du choix de l’ordre de Walsh
4.3.5 Comparaison entre le framework S-MCO et des algorithmes nonassistés par méta-modèle
4.4 Conclusion
Conclusion générale
Télécharger le rapport complet
