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 $X\subseteq \mathbb {R} ^{n}$ et $f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{p}$ , les $p$ fonctions objectif, le problème d'optimisation multiobjectif consiste à déterminer :

P:\min\{f(x):\,x\in X\}

.

L'ensemble des solutions admissibles $X$ est appelé région admissible. Une solution $x\in X$ est également indifféremment dénommée solution réalisable pour le problème $P$ . On note $Y$ l'image de $X$ par $f$ telle que $\forall y\in Y,\exists x\in X$ tel que $f(x)=y$ . Un élément $y\in Y$ 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 $(1,2)$ et $(2,1)$ 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 $x$ et $y$ deux solutions distinctes, l'optimalité lexicographique est définie comme suit : si $f(x)\leq f(y)$ on pose $k^{*}=\min \left\{k\;|\;f_{k}(x)\neq f_{k}(y)\right\}$ et $f(x)\leqq _{lex}f(y)$ si, et seulement si, $f(x)=f(y)$ ou $f_{k^{*}}\left(x\right)<f_{k^{*}}\left(y\right)$ . 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^[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 $x$ s'avère inefficace s'il existe une solution qui lui est préférée. Un tel $x$ 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 et résoudre un programme multiobjectif consistera à extraire l'ensemble des points dits non-dominés. Considérons un problème de minimisation : $min(f1(x),...,fp(x))$ , pour $x$ et ${\hat {x}}$ deux solutions et $f(x)$ et $f({\hat {x}})$ les points qui leur correspondent on a :

$f({\hat {x}})$ domine $f(x)$ strictement (aussi dit au sens fort) noté $f({\hat {x}})<f(x)$ si, et seulement si, $f_{i}({\hat {x}})<f_{i}(x)$ $\forall i$ ;
$f({\hat {x}})$ domine faiblement $f(x)$ noté $f({\hat {x}})\leqq f(x)$ si, et seulement si, $f_{i}({\hat {x}})\leq f_{i}(x)$ $\forall i$ ;
$f({\hat {x}})$ domine $f(x)$ noté $f({\hat {x}})\leq f(x)$ si, et seulement si, $f({\hat {x}})\leqq f(x)$ et $f({\hat {x}})\neq f(x)$ .

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 $\not \exists x\in X:f(x)<f({\hat {x}})$ on dit que ${\hat {x}}$ est faiblement efficace et ${\hat {y}}$ est faiblement non-dominée $({\hat {y}}=f({\hat {x}}))$

Si $\not \exists x\in X:f(x)\leq f({\hat {x}})$ on dit que ${\hat {x}}$ est efficace et ${\hat {y}}$ est non-dominée $({\hat {y}}=f({\hat {x}}))$

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 $Y_{N}$ l'image des solutions efficaces par $f$ d'un problème forme dans l'espace objectif une frontière de Pareto. Notons que $X_{E}$ telle que $f(X_{E})=Y_{N}$ est un sous-ensemble de l'ensemble $f(X_{wE})=Y_{wN}$ 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 :

{\begin{array}{ll}\min &g(z_{1}(x),\ldots ,z_{k}(x),\theta )\\{\text{s.t }}x\in X_{\theta },\end{array}}

où $\theta$ est un vecteur paramètre, l'ensemble $X_{\theta }\subseteq X$ est un ensemble dépendant du paramètre $\theta$ et $g:\mathbb {R} ^{k+1}\mapsto \mathbb {R}$ est une nouvelle fonction objectif.

Quelques exemples :

scalarisation linéaire

\min _{x\in X}\sum _{i=1}^{k}w_{i}z_{i}(x),

où les poids des objectifs

w_{i}

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

méthode $\epsilon$ -contrainte

{\begin{array}{ll}\min &z_{j}(x)\\{\text{s.t. }}&x\in X\\&z_{i}(x)\leq \epsilon _{j}{\text{ for }}i\in \{1,\ldots ,k\}\setminus \{j\},\end{array}}

où les bornes supérieures

\epsilon _{j}

sont les paramètres de la scalarisation et

z_{j}

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)^[2] et le «Strength Pareto Evolutionary Algorithm 2» (SPEA-2)^[3] sont devenus des approches standard. Une autre approche populaire est le «Multiobjective Evolutionary Algorithm Based on Decomposition» (MOEA/D)^[4] 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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Multi-objective_optimization » (voir la liste des auteurs).

↑ ^{a et b} (en) Matthias Ehrgott, Multicriteria Optimization, vol. 1, Springer-Verlag, Berlin, Heidelberg, 2005.
↑ K. Deb, A. Pratap, S. Agarwal et T. Meyarivan, « A fast and elitist multiobjective genetic algorithm: NSGA-II », IEEE Transactions on Evolutionary Computation, vol. 6, n^o 2,‎ 2002, p. 182 (DOI 10.1109/4235.996017, CiteSeer^x 10.1.1.17.7771)
↑ Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Performance of the Strength Pareto Evolutionary Algorithm, Technical Report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich (2001) [1]
↑ Qingfu Zhang et Hui Li, « MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition », IEEE Transactions on Evolutionary Computation, vol. 11, n^o 6,‎ décembre 2007, p. 712–731 (ISSN 1941-0026 et 1089-778X, DOI 10.1109/TEVC.2007.892759, lire en ligne, consulté le 25 avril 2022)

Portail des mathématiques

[:ehrgott-1] {a et b} (en) Matthias Ehrgott, Multicriteria Optimization, vol. 1, Springer-Verlag, Berlin, Heidelberg, 2005.

[doi10.1109/4235.996017-2] K. Deb, A. Pratap, S. Agarwal et T. Meyarivan, « A fast and elitist multiobjective genetic algorithm: NSGA-II », IEEE Transactions on Evolutionary Computation, vol. 6, n^o 2,‎ 2002, p. 182 (DOI 10.1109/4235.996017, CiteSeer^x 10.1.1.17.7771)

[3] Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Performance of the Strength Pareto Evolutionary Algorithm, Technical Report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich (2001) [1]

[4] Qingfu Zhang et Hui Li, « MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition », IEEE Transactions on Evolutionary Computation, vol. 11, n^o 6,‎ décembre 2007, p. 712–731 (ISSN 1941-0026 et 1089-778X, DOI 10.1109/TEVC.2007.892759, lire en ligne, consulté le 25 avril 2022)

[1]

[2]

[3]

[4]