Optimisation multiobjectif

L'optimisation multiobjectif (appelée aussi Programmation multi-objective ou optimisation multi-critère) est une branche de l'optimisation mathématique traitant spécifiquement des problèmes d'optimisation ayant plusieurs fonctions objectifs. Elle se distingue de l'optimisation multidisciplinaire par le fait que les objectifs à optimiser portent ici sur un seul problème.

Les problèmes multiobjectifs ont un intérêt grandissant dans l'industrie où les responsables sont contraints de tenter d'optimiser des objectifs contradictoires. Ces problèmes peuvent être NP-difficiles. Leur résolution en des temps raisonnables devient nécessaire et alimente une partie des chercheurs travaillant dans la recherche opérationnelle.

Définition 

Dans sa forme la plus générale, un problème d'optimisation multiobjectif consiste à trouver dans un ensemble de solutions admissibles, un sous-ensemble de solutions minimisant ses objectifs. Le cas de la maximisation peut être traité comme une minimisation après inversion des signes de l'expression à maximiser.

Formellement, étant donnés un ensemble de solutions admissibles  et , les  fonctions objectif, le problème d'optimisation multiobjectif consiste à déterminer :
.

L'ensemble des solutions admissibles  est appelé région admissible. Une solution  est également indifféremment dénommée solution réalisable pour le problème . On note  l'image de  par  telle que  tel que . Un élément  est appelé point réalisable ou encore point faisable.

Optimalité des solutions 

Pour un problème monobjectif, la comparaison de deux solutions lors de la recherche de l'optimum est triviale. La définition d'optimalité est à redéfinir dans un contexte multiobjectif ; en effet deux solutions peuvent être incomparables. Par exemple, un problème bi-objectifs ne proposant que deux points réalisables  et  d'antécédents distincts ne permet pas d'extraire une solution optimale unique. Il est ainsi nécessaire de laisser à un décideur le verdict final quant au choix de la solution retenue.

Deux définitions de l'optimalité sont envisagées : l'optimalité lexicographique, où un ordre sur les objectifs est fixé et l'optimalité de Pareto, basée sur les notions d'efficacité et de non-dominance, où aucun objectif n'est plus important qu'un autre.

Optimalité lexicographique 

Lorsqu'un ordre de priorité ou de préférences est connu sur les objectifs, le problème est résolu d'une scalarisation par somme pondéré ou en optimisant un à un les objectifs dans l'ordre donné. L'idée est alors d'améliorer l'objectif envisagé sans perdre en qualité sur les objectifs préalablement minimisés.

Soient  et  deux solutions distinctes, l'optimalité lexicographique est définie comme suit : si  on pose  et  si, et seulement si,  ou . Cette optimalité lexicographique dépend d'une permutation arbitraire des objectifs. Plusieurs solutions peuvent donc être optimales au sens lexicographique pour le même problème multiobjectifs.

Optimalité de Pareto 

S'il est impossible de connaître a priori un ordre préférence sur les objectifs, de nombreuses solutions deviennent incomparables entre elles. La première référence à traiter d'objectifs conflictuels est fréquemment attribuée à Vilfredo Pareto en 1896. Il définit l'efficacité comme l'impossibilité d'améliorer un objectif de la solution sans dégrader l'intérêt d'un autre objectif. L'importance fondamentale de l'efficacité est basée sur ce constat qu'une solution  s'avère inefficace s'il existe une solution qui lui est préférée. Un tel  ne peut pas représenter une alternative valide pour un décideur.

Cette existence de relation d'ordre entre certaines solutions permet de définir une notion de dominance et résoudre un programme multiobjectif consistera à extraire l'ensemble des points dits non-dominés. 
Considérons un problème de minimisation : , pour  et  deux solutions et  et  les points qui leur correspondent on a :

  domine  strictement (aussi dit au sens fort) noté  si, et seulement si,   ;
  domine faiblement  noté  si, et seulement si,   ;
  domine  noté  si, et seulement si,  et .

On parle de dominance dans l'espace des objectifs mais cette notion est aussi étendue à la notion d'efficacité dans l'espace de décision:

 Si  on dit que  est faiblement efficace et  est faiblement non-dominée   

 Si  on dit que  est efficace et  est non-dominée   

Une solution est dite faiblement efficace si le point correspondant est faiblement non-dominé, c'est-à-dire s'il n'existe aucune autre solution qui la domine au sens fort. Elle est dite efficace si le point correspondant est non-dominé, (aucune autre solution ne la domine). L'ensemble  l'image des solutions efficaces par  d'un problème forme dans l'espace objectif une frontière de Pareto. Notons que  telle que  est un sous-ensemble de l'ensemble  des solutions faiblement efficaces. 
Les solutions optimales au sens lexicographiques sont des solutions efficaces.

Ensembles de solutions 

L'ensemble des solutions efficaces peut être partitionné en deux ensembles. Le premier contient les solutions dites supportées dont le point image se situe sur la fermeture convexe de la région admissible ; on peut les trouver en résolvant des combinaisons linéaires des objectifs. Le second ensemble contient les solutions non supportées plus complexes à trouver. Elles ne sont pas sur la fermeture convexe, mais ne sont pas dominées pour autant.

Deux solutions admissibles peuvent correspondre à un même point réalisable efficace. Il convient alors de définir l'ensemble de solutions complet minimal qui ne contient qu'une seule solution pour chaque point non dominé dans l'espace des objectifs et l'ensemble des solutions complet maximal contenant toutes les solutions équivalentes pour chaque point non dominé dans l'espace des objectifs. L'interêt du premier est de restreindre l'ensemble construit et donc le coût de recherche tout en atteignant tous les points efficaces. L'ensemble maximal permettra à une chaîne de production par exemple de disposer de plusieurs solutions de secours pour un plan de production validé.

Scalarisation  
Scalariser un problème d'optimisation multi-objectif est une méthode qui consiste à formuler un problème d'optimisation mono-objectif et de le résoudre à plusieurs reprises en faisant varier ses paramètres. Les méthodes de scalarisation cherchent à vérifier les propriétés de justesse et de complétude. La justesse assure que les solutions optimales du problème mono-objectif soient des solutions (faiblement) efficaces pour le problème multi-objectif considéré. La complétude garantie d'atteindre toutes les solutions efficaces du problème multi-objectif en ajustant les valeurs des paramètres appropriés.  

Par alors, une formulation générale des méthodes de scalarisation est :
 
où  est un vecteur paramètre, l'ensemble  est un ensemble dépendant du paramètre  et  est une nouvelle fonction objectif.

Quelques exemples :

 scalarisation linéaire 

où les poids des objectifs  sont positifs et non tous nuls. Ces poids sont les paramètres de la scalarisation ;

 méthode -contrainte

où les bornes supérieures  sont les paramètres de la scalarisation et  l'objectif à minimiser.

Algorithmes évolutionnaires multi-objectifs 
Les Algorithmes évolutionnistes permettent d'obtenir le front de Pareto ou une approximation du front de Pareto. Le principal avantage des algorithmes évolutionnaires appliqués à la résolution de problèmes d'optimisation multi-objectifs, est le fait qu'ils génèrent généralement des ensembles de solutions, permettant le calcul d'une approximation de l'ensemble du front de Pareto. Le principal inconvénient des algorithmes évolutifs est leur vitesse inférieure et surtout que l'optimalité de Pareto des solutions ne peut être garantie. L'algorithme détermine uniquement le front de Pareto de l'ensemble des solutions évalués au cours de l’exécution. Les algorithmes évolutionnaires tels que le «Non-dominated Sorting Genetic Algorithm-II» (NSGA-II) et le «Strength Pareto Evolutionary Algorithm 2» (SPEA-2) sont devenus des approches standard. Une autre approche populaire est le «Multiobjective Evolutionary Algorithm Based on Decomposition» (MOEA/D) qui décompose un problème multi-objectif en un ensemble de problèmes mono-objectifs étant donné un ensemble de vecteurs et d'une fonction d’agrégation. Les problèmes mono-objectifs sont ensuite résolu en parallèle et s'entraide les uns les autres.

Voir aussi 
 Comparaisons par paires
 ELECTRE : méthode non compensatoire, ELimination Et Choix Traduisant la REalité
 Matrice de compatibilité
 Optimisation discrète
 PROMETHEE : "Preference Ranking Organisation METHod for Enrichment Evaluations".
 Théorie de la décision : mathématiques pour l'aide à la prise de décisions

Références 

Multiobjectif
Combinatoire
Recherche opérationnelle