Optimisation multiobjectif

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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-difficile. Leur résolution en des temps raisonnables devient nécessaire et alimente une partie des chercheurs travaillant dans la recherche opérationnelle.


Définition[modifier | modifier le code]

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 égalemment indifféremment dénommée solution réalisable pour le problème . On note l'image de par telle que . Un élément est appelé point réalisable ou encore point faisable.

Optimalité des solutions[modifier | modifier le code]

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 incomparable. 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 quand au choix de la solution retenue.

Deux définitions de l'optimalité sont envisagés : 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[modifier | modifier le code]

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[modifier | modifier le code]

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[1]. 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[1].

Cette existence de relation d'ordre entre certaines solutions permet de définir une notion de dominance. Ainsi, pour et deux solutions, on a :

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

Une solution est dite faiblement efficace si elle 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 elle est non-dominé, (aucune autre solution ne la domine). L'ensemble des solutions efficaces d'un problème forme une frontière de Pareto. Notons 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[modifier | modifier le code]

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[modifier | modifier le code]

Scalariser un problème d'optimisation multi-objectif est une méthode qui consiste à formuler un probè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 :

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.


Voir aussi[modifier | modifier le code]


Références[modifier | modifier le code]

  1. a et b (en) Matthias Ehrgott, Multicriteria Optimization, vol. 1, Springer-Verlag, Berlin, Heidelberg, .