Optimisation multi-objectifs - Multi-objective optimization

Optimisation multi-objectifs (aussi connu comme la programmation multi-objectifs , optimisation vectorielle , optimisation multicritère , optimisation multiattributs ou optimisation Pareto ) est une zone de prise de décision multicritère qui est concerné par des problèmes d'optimisation mathématique impliquant plus d'une fonction objectif d' optimiser simultanément . L'optimisation multi-objectifs a été appliquée dans de nombreux domaines scientifiques, notamment l'ingénierie, l'économie et la logistique, où des décisions optimales doivent être prises en présence de compromis entre deux ou plusieurs objectifs contradictoires. Minimiser les coûts tout en maximisant le confort lors de l'achat d'une voiture et maximiser les performances tout en minimisant la consommation de carburant et les émissions de polluants d'un véhicule sont des exemples de problèmes d'optimisation multi-objectifs impliquant respectivement deux et trois objectifs. Dans les problèmes pratiques, il peut y avoir plus de trois objectifs.

Pour un problème d'optimisation multi-objectifs non trivial , il n'existe pas de solution unique qui optimise simultanément chaque objectif. Dans ce cas, les fonctions objectifs sont dites conflictuelles. Une solution est dite non dominée , Pareto optimale, Pareto efficace ou non inférieure, si aucune des fonctions objectifs ne peut être améliorée en valeur sans dégrader certaines des autres valeurs objectives. Sans informations de préférence subjectives supplémentaires , il peut exister un nombre (éventuellement infini) de solutions optimales de Pareto, qui sont toutes considérées comme également bonnes. Les chercheurs étudient les problèmes d'optimisation multi-objectifs sous différents points de vue et, par conséquent, il existe différentes philosophies et objectifs de solution lors de leur définition et de leur résolution. L'objectif peut être de trouver un ensemble représentatif de solutions optimales de Pareto, et/ou de quantifier les compromis pour satisfaire les différents objectifs, et/ou de trouver une solution unique qui satisfait les préférences subjectives d'un décideur humain (DM).

L'optimisation bicritère désigne le cas particulier dans lequel il existe deux fonctions objectifs.

introduction

Un problème d'optimisation multi-objectifs est un problème d'optimisation qui implique plusieurs fonctions objectifs. En termes mathématiques, un problème d'optimisation multi-objectif peut être formulé comme

{\begin{aligned}\min &\left(f_{1}({\vec {x}}),f_{2}({\vec {x}}),\ldots ,f_{k} ({\vec {x}})\right)\\{\text{st }}&{\vec {x}}\in X,\end{aligned}}

où l'entier est le nombre d'objectifs et l'ensemble est l' ensemble réalisable de vecteurs de décision, ce qui est généralement mais cela dépend du domaine d'application -dimensionnel. L'ensemble des possibles est généralement défini par certaines fonctions de contrainte. De plus, la fonction objectif à valeur vectorielle est souvent définie comme $k\geq 2$ ${\style d'affichage X}$ $X\subseteq \mathbb {R} ^{n}$ ${\style d'affichage n}$

{\vec {f}}:X\to \mathbb {R} ^{k},\ {\vec {f}}({\vec {x}})=(f_{1}({\ vec {x}}),\ldots ,f_{k}({\vec {x}}))^{\intercal }

. Si une fonction objectif doit être maximisée, cela revient à minimiser son négatif. L'image de est désignée par

{\style d'affichage X}

Y\subseteq \mathbb {R} ^{k}

Exemple de frontière de Pareto (en rouge), l'ensemble des solutions optimales de Pareto (celles qui ne sont dominées par aucune autre solution réalisable). Les points encadrés représentent des choix réalisables, et les valeurs plus petites sont préférées aux plus grandes. Le point C n'est pas sur la frontière de Pareto car il est dominé à la fois par le point A et le point B . Les points A et B ne sont strictement dominés par aucun autre et se situent donc sur la frontière.

Un élément est appelé une solution réalisable ou une décision réalisable . Un vecteur pour une solution réalisable s'appelle un vecteur objectif ou un résultat . Dans l'optimisation multi-objectifs, il n'existe généralement pas de solution réalisable qui minimise toutes les fonctions objectifs simultanément. Par conséquent, une attention est portée aux solutions optimales de Pareto ; c'est-à-dire des solutions qui ne peuvent être améliorées dans aucun des objectifs sans dégrader au moins un des autres objectifs. En termes mathématiques, une solution réalisable est dite (Pareto) dominer une autre solution , si ${\vec {x}}^{*}\in X$ ${\vec {z}}^{*}:={\vec {f}}({\vec {x}}^{*})\in \mathbb {R} ^{k}$ ${\vec {x}}^{*}$ ${\vec {x}}_{1}\in X$ ${\vec {x}}_{2}\in X$

$f_{i}({\vec {x}}_{1})\leq f_{i}({\vec {x}}_{2})$ , pour tous les indices , et $i\in \left\{{1,2,\dots ,k}\right\}$
$f_{j}({\vec {x}}_{1})<f_{j}({\vec {x}}_{2})$ , pour au moins un indice . $j\in \left\{{1,2,\dots ,k}\right\}$

Une solution (et le résultat correspondant ) est dite Pareto optimale, s'il n'existe pas d'autre solution qui la domine. L'ensemble des résultats optimaux de Pareto est souvent appelé front de Pareto , frontière de Pareto ou frontière de Pareto. ${\vec {x}}^{*}\in X$ ${\vec {f}}({\vec {x}}^{*})$

Le front de Pareto d'un problème d'optimisation multi-objectifs est délimité par un vecteur objectif dit nadir et un vecteur objectif idéal , s'ils sont finis. Le vecteur objectif nadir est défini comme ${\vec {z}}^{nad}$ ${\vec {z}}^{idéal}$

{\vec {z}}^{nad}\ni {\vec {z}}_{i}^{nad}={\underset {x\in X}{\sup }}\{f_{ i}(x)\}{\text{ pour tout }}i=1,\ldots ,k,

et le vecteur objectif idéal comme

{\vec {z}}^{ideal}\ni {\vec {z}}_{i}^{ideal}={\underset {x\in X}{\inf }}\{f_{ i}(x)\}{\text{ pour tout }}i=1,\ldots ,k.

En d'autres termes, les composantes d'un nadir et d'un vecteur objectif idéal définissent respectivement les limites supérieure et inférieure des valeurs de la fonction objectif des solutions optimales de Pareto. En pratique, le vecteur objectif nadir ne peut être qu'approché car, typiquement, l'ensemble optimal de Pareto est inconnu. De plus, un vecteur objectif utopique avec ${\vec {z}}^{utopique}$

{\vec {z}}_{i}^{utopian}={\vec {z}}_{i}^{ideal}-\epsilon {\text{ pour tous }}i=1,\ ldots ,k,

où est une petite constante, est souvent défini pour des raisons numériques. $\epsilon >0$

Exemples d'applications

Économie

En économie , de nombreux problèmes impliquent des objectifs multiples ainsi que des contraintes sur les combinaisons de ces objectifs sont réalisables. Par exemple, la demande des consommateurs pour divers biens est déterminée par le processus de maximisation des utilités dérivées de ces biens, soumise à une contrainte basée sur le revenu disponible à dépenser pour ces biens et sur les prix de ces biens. Cette contrainte ne permet d'acheter plus d'un bien qu'au prix de consommer moins d'un autre bien ; par conséquent, les différents objectifs (plus de consommation de chaque bien est préférée) sont en conflit les uns avec les autres. Une méthode courante pour analyser un tel problème consiste à utiliser un graphique de courbes d'indifférence , représentant les préférences, et une contrainte budgétaire, représentant les compromis auxquels le consommateur est confronté.

Un autre exemple concerne la frontière des possibilités de production , qui spécifie quelles combinaisons de divers types de biens peuvent être produites par une société avec certaines quantités de ressources diverses. La frontière spécifie les compromis auxquels la société est confrontée - si la société utilise pleinement ses ressources, plus d'un bien ne peut être produit qu'au détriment de la production de moins d'un autre bien. Une société doit alors utiliser un certain processus pour choisir parmi les possibilités à la frontière.

L'élaboration des politiques macroéconomiques est un contexte nécessitant une optimisation multi-objectifs. En règle générale, une banque centrale doit choisir une position de politique monétaire qui équilibre les objectifs concurrents - faible inflation , faible taux de chômage , faible déficit de la balance commerciale , etc. Pour ce faire, la banque centrale utilise un modèle de l'économie qui décrit quantitativement les divers liens de causalité. dans l'économie; il simule le modèle à plusieurs reprises sous diverses positions possibles de la politique monétaire, afin d'obtenir un menu de résultats possibles prévus pour les diverses variables d'intérêt. Ensuite, en principe, elle peut utiliser une fonction objective agrégée pour évaluer les ensembles alternatifs de résultats prévus, bien qu'en pratique les banques centrales utilisent un processus non quantitatif, basé sur le jugement, pour classer les alternatives et faire le choix politique.

La finance

En finance , un problème courant consiste à choisir un portefeuille lorsqu'il y a deux objectifs contradictoires : le désir d'avoir la valeur attendue des rendements du portefeuille aussi élevée que possible, et le désir d'avoir un risque , souvent mesuré par l' écart type des rendements du portefeuille. , être le plus bas possible. Ce problème est souvent représenté par un graphique dans lequel la frontière efficiente montre les meilleures combinaisons de risque et de rendement attendu disponibles, et dans lequel les courbes d'indifférence montrent les préférences de l'investisseur pour diverses combinaisons de risque et de rendement attendu. Le problème d'optimisation d'une fonction de la valeur attendue (premier moment ) et de l'écart type (racine carrée du deuxième moment central) du rendement du portefeuille est appelé modèle de décision à deux moments .

Contrôle optimal

En ingénierie et en économie , de nombreux problèmes impliquent des objectifs multiples qui ne peuvent être décrits comme le plus ou le moins ; au lieu de cela, il existe une valeur cible idéale pour chaque objectif, et le désir est de se rapprocher le plus possible de la valeur souhaitée de chaque objectif. Par exemple, les systèmes énergétiques ont généralement un compromis entre les performances et le coût ou l'on peut vouloir ajuster la consommation de carburant et l'orientation d'une fusée afin qu'elle arrive à la fois à un endroit spécifié et à une heure spécifiée ; ou l'on pourrait vouloir mener des opérations d'open market afin que le taux d'inflation et le taux de chômage soient aussi proches que possible de leurs valeurs souhaitées.

Souvent, de tels problèmes sont soumis à des contraintes d'égalité linéaire qui empêchent tous les objectifs d'être simultanément parfaitement atteints, en particulier lorsque le nombre de variables contrôlables est inférieur au nombre d'objectifs et lorsque la présence de chocs aléatoires génère de l'incertitude. Généralement, une fonction objectif quadratique multi-objectif est utilisée, le coût associé à un objectif augmentant quadratiquement avec la distance de l'objectif à sa valeur idéale. Etant donné que ces problèmes impliquent généralement l'ajustement des variables contrôlées à divers moments et/ou l'évaluation des objectifs à divers moments, des techniques d' optimisation intertemporelle sont utilisées.

Conception optimale

La conception des produits et des processus peut être largement améliorée à l'aide de techniques modernes de modélisation, de simulation et d'optimisation. La question clé de la conception optimale est la mesure de ce qui est bon ou souhaitable dans une conception. Avant de rechercher des conceptions optimales, il est important d'identifier les caractéristiques qui contribuent le plus à la valeur globale de la conception. Une bonne conception implique généralement de multiples critères/objectifs tels que le coût d'investissement/l'investissement, le coût d'exploitation, le profit, la qualité et/ou la récupération du produit, l'efficacité, la sécurité du processus, le temps de fonctionnement, etc. Par conséquent, dans les applications pratiques, la performance du processus et la conception du produit est souvent mesurée par rapport à des objectifs multiples. Ces objectifs sont généralement contradictoires, c'est-à-dire que la réalisation de la valeur optimale pour un objectif nécessite un compromis sur un ou plusieurs autres objectifs.

Par exemple, lors de la conception d'une papeterie, on peut chercher à diminuer le montant du capital investi dans une papeterie et à améliorer simultanément la qualité du papier. Si la conception d'une papeterie est définie par de grands volumes de stockage et que la qualité du papier est définie par des paramètres de qualité, alors le problème de la conception optimale d'une papeterie peut inclure des objectifs tels que : i) la minimisation de la variation attendue de ces paramètres de qualité par rapport à leur valeurs nominales, ii) la minimisation du temps de pause prévu et iii) la minimisation du coût d'investissement des volumes de stockage. Ici, le volume maximum des tours sont des variables de conception. Cet exemple de conception optimale d'une papeterie est une simplification du modèle utilisé. L'optimisation de la conception multi-objectifs a également été mise en œuvre dans les systèmes d'ingénierie dans des circonstances telles que l'optimisation de la disposition des armoires de commande, l'optimisation de la forme du profil aérodynamique à l'aide de flux de travail scientifiques, la conception de nano- Semi-conducteurs CMOS , conception de systèmes sur puce , conception de systèmes d'irrigation à énergie solaire, optimisation des systèmes de moules à sable, conception de moteurs, déploiement optimal de capteurs et conception optimale de contrôleurs.

Optimisation du processus

L'optimisation multi-objectifs est de plus en plus utilisée dans le génie chimique et la fabrication . En 2009, Fiandaca et Fraga ont utilisé l'algorithme génétique multi-objectifs (MOGA) pour optimiser le processus d'adsorption modulée en pression (processus de séparation cyclique). Le problème de conception impliquait la double maximisation de la récupération d'azote et de la pureté de l'azote. Les résultats ont fourni une bonne approximation de la frontière de Pareto avec des compromis acceptables entre les objectifs.

En 2010, Sendin et al. a résolu un problème multi-objectifs pour le traitement thermique des aliments. Ils ont abordé deux études de cas (problèmes bi-objectifs et triples objectifs) avec des modèles dynamiques non linéaires et ont utilisé une approche hybride consistant en l'approche pondérée de Tchebycheff et l'approche d'intersection de frontière normale. La nouvelle approche hybride a permis de construire un ensemble optimal de Pareto pour le traitement thermique des aliments.

En 2013, Ganesan et al. a réalisé l'optimisation multi-objectifs de la combinaison reformage du dioxyde de carbone et oxydation partielle du méthane. Les fonctions objectives étaient la conversion du méthane, la sélectivité en monoxyde de carbone et le rapport hydrogène/monoxyde de carbone. Ganesan a utilisé la méthode NBI (Normal Boundary Intersection) en conjonction avec deux techniques basées sur les essaims (algorithme de recherche gravitationnelle (GSA) et Particle Swarm Optimization (PSO)) pour résoudre le problème. Les applications impliquant des procédés d'extraction chimique et de production de bioéthanol ont posé des problèmes multi-objectifs similaires.

En 2013, Abakarov et al ont proposé une technique alternative pour résoudre les problèmes d'optimisation multi-objectifs liés à l'ingénierie alimentaire. L'approche des fonctions d'agrégation, l'algorithme de recherche aléatoire adaptative et l'approche des fonctions de pénalité ont été utilisées pour calculer l'ensemble initial des solutions non dominées ou Pareto-optimales. Le processus de hiérarchie analytique et la méthode tabulaire ont été utilisés simultanément pour choisir la meilleure alternative parmi le sous-ensemble calculé de solutions non dominées pour les processus de déshydratation osmotique.

En 2018, Pearce et al. a formulé l'attribution des tâches aux travailleurs humains et robotiques comme un problème d'optimisation multi-objectifs, considérant le temps de production et l'impact ergonomique sur le travailleur humain comme les deux objectifs considérés dans la formulation. Leur approche a utilisé un programme linéaire à nombres entiers mixtes pour résoudre le problème d'optimisation pour une somme pondérée des deux objectifs afin de calculer un ensemble de solutions optimales de Pareto . L'application de l'approche à plusieurs tâches de fabrication a montré des améliorations dans au moins un objectif dans la plupart des tâches et dans les deux objectifs dans certains des processus.

Gestion des ressources radio

Le but de la gestion des ressources radio est de satisfaire les débits demandés par les utilisateurs d'un réseau cellulaire. Les principales ressources sont les intervalles de temps, les blocs de fréquence et les puissances d'émission. Chaque utilisateur a sa propre fonction objective qui, par exemple, peut représenter une combinaison du débit de données, de la latence et de l'efficacité énergétique. Ces objectifs sont contradictoires car les ressources en fréquences sont très rares, il existe donc un besoin de réutilisation spatiale serrée des fréquences qui provoque d'immenses interférences inter-utilisateurs si elle n'est pas correctement contrôlée. Les techniques MIMO multi-utilisateurs sont aujourd'hui utilisées pour réduire les interférences par précodage adaptatif . L'opérateur de réseau souhaite à la fois apporter une grande couverture et des débits de données élevés. Il souhaite donc trouver une solution Pareto optimale qui équilibre le débit total de données du réseau et l'équité de l'utilisateur d'une manière subjective appropriée.

La gestion des ressources radio est souvent résolue par scalarisation ; c'est-à-dire la sélection d'une fonction utilitaire de réseau qui essaie d'équilibrer le débit et l'équité de l'utilisateur. Le choix de la fonction d'utilité a un impact important sur la complexité de calcul du problème d'optimisation à objectif unique résultant. Par exemple, l'utilité commune du taux de somme pondéré donne un problème NP-difficile avec une complexité qui évolue de manière exponentielle avec le nombre d'utilisateurs, tandis que l'utilité d'équité max-min pondérée aboutit à un problème d'optimisation quasi-convexe avec seulement une mise à l'échelle polynomiale avec le nombre d'utilisateurs.

Systèmes d'alimentation électrique

La reconfiguration, en échangeant les liens fonctionnels entre les éléments du système, représente l'une des mesures les plus importantes pouvant améliorer les performances opérationnelles d'un système de distribution. Le problème de l'optimisation par la reconfiguration d'un réseau de distribution d'électricité, dans sa définition, est un problème historique à objectif unique avec des contraintes. Depuis 1975, lorsque Merlin et Back ont introduit l'idée de la reconfiguration du système de distribution pour la réduction des pertes de puissance active, jusqu'à nos jours, de nombreux chercheurs ont proposé diverses méthodes et algorithmes pour résoudre le problème de reconfiguration en tant que problème objectif unique. Certains auteurs ont proposé des approches basées sur l'optimalité de Pareto (incluant les pertes de puissance active et les indices de fiabilité comme objectifs). Pour cela, différentes méthodes basées sur l'intelligence artificielle ont été utilisées : microgénétique, échange de branches, optimisation d'essaims de particules et algorithme génétique de tri non dominé.

Inspection des infrastructures

L'inspection autonome des infrastructures a le potentiel de réduire les coûts, les risques et les impacts environnementaux, ainsi que d'assurer un meilleur entretien périodique des actifs inspectés. En règle générale, la planification de telles missions a été considérée comme un problème d'optimisation à objectif unique, où l'on vise à minimiser l'énergie ou le temps consacré à l'inspection d'une structure cible entière. Pour les structures complexes du monde réel, cependant, il n'est pas possible de couvrir 100 % d'une cible d'inspection, et la génération d'un plan d'inspection peut être mieux considérée comme un problème d'optimisation multiobjectif, où l'on vise à la fois à maximiser la couverture d'inspection et à minimiser le temps et les coûts. Une étude récente a indiqué que la planification d'inspection multiobjectif a en effet le potentiel de surpasser les méthodes traditionnelles sur des structures complexes

Solution

Comme il existe généralement plusieurs solutions optimales de Pareto pour les problèmes d'optimisation multi-objectifs, ce que cela signifie pour résoudre un tel problème n'est pas aussi simple que pour un problème d'optimisation classique à objectif unique. Par conséquent, différents chercheurs ont défini le terme "résolution d'un problème d'optimisation multi-objectifs" de diverses manières. Cette section résume certains d'entre eux et les contextes dans lesquels ils sont utilisés. De nombreuses méthodes convertissent le problème d'origine à objectifs multiples en un problème d'optimisation à objectif unique . C'est ce qu'on appelle un problème scalarisé. Si l'optimalité de Pareto des solutions mono-objectifs obtenues peut être garantie, la scalarisation est caractérisée comme étant faite de manière ordonnée.

La résolution d'un problème d'optimisation multi-objectifs est parfois comprise comme l'approximation ou le calcul de l'ensemble ou d'un ensemble représentatif de solutions optimales de Pareto.

Lorsque l' accent est mis sur la prise de décision , l'objectif de résoudre un problème d'optimisation multi-objectifs est d'aider un décideur à trouver la solution optimale de Pareto la plus préférée en fonction de ses préférences subjectives. L'hypothèse sous-jacente est qu'une solution au problème doit être identifiée pour être mise en œuvre dans la pratique. Ici, un décideur humain (DM) joue un rôle important. Le DM est censé être un expert dans le domaine du problème.

Les résultats les plus préférés peuvent être trouvés en utilisant différentes philosophies. Les méthodes d'optimisation multi-objectifs peuvent être divisées en quatre classes.

Dans les méthodes dites sans préférence , aucun DM ne devrait être disponible, mais une solution de compromis neutre est identifiée sans information de préférence. Les autres classes sont des méthodes dites a priori, a posteriori et interactives et elles impliquent toutes des informations de préférence du DM de différentes manières.
Dans les méthodes a priori , les informations de préférence sont d'abord demandées au DM, puis une solution satisfaisant au mieux ces préférences est trouvée.
Dans les méthodes a posteriori , un ensemble représentatif de solutions optimales de Pareto est d'abord trouvé, puis le MD doit choisir l'une d'entre elles.
Dans les méthodes interactives , le décideur est autorisé à rechercher itérativement la solution la plus préférée. À chaque itération de la méthode interactive, le DM affiche la ou les solutions optimales de Pareto et décrit comment la ou les solutions pourraient être améliorées. Les informations fournies par le décideur sont ensuite prises en compte lors de la génération de nouvelles solutions optimales de Pareto que le DM étudiera à l'itération suivante. De cette façon, le DM apprend la faisabilité de ses souhaits et peut se concentrer sur les solutions qui l'intéressent. Le DM peut arrêter la recherche quand il le souhaite.

Plus d'informations et des exemples de différentes méthodes dans les quatre classes sont donnés dans les sections suivantes.

Méthodes sans préférence

Lorsqu'un décideur n'articule explicitement aucune information de préférence, la méthode d'optimisation multi-objectifs peut être classée comme méthode sans préférence. Un exemple bien connu est la méthode du critère global, dans laquelle un problème scalarisé de la forme

{\begin{aligned}\min &\|f(x)-z^{ideal}\|\\{\text{st }}&x\in X\end{aligned}}

est résolu. Dans le problème ci-dessus, peut être n'importe quelle norme , avec des choix communs comprenant , et . La méthode du critère global est sensible à la mise à l'échelle des fonctions objectifs, et ainsi, il est recommandé que les objectifs soient normalisés dans une échelle uniforme et sans dimension. ${\style d'affichage \|\cdot \|}$ ${\style d'affichage L_{p}}$ ${\style d'affichage L_{1}}$ ${\style d'affichage L_{2}}$ $L_{\infty }$

Méthodes a priori

Les méthodes a priori nécessitent que des informations de préférence suffisantes soient exprimées avant le processus de résolution. Des exemples d'une des méthodes a priori bien connues comprennent la méthode de fonction d'utilité , lexicographique méthode, et la programmation de but .

Dans la méthode de la fonction d'utilité, on suppose que la fonction d'utilité du décideur est disponible. Une application est une fonction d'utilité si pour tout si elle tient que si le décideur préfère à , et si le décideur est indifférent entre et . La fonction d'utilité spécifie un ordre des vecteurs de décision (rappelez-vous que les vecteurs peuvent être ordonnés de différentes manières). Une fois obtenu, il suffit de résoudre $u\colon Y\rightarrow \mathbb {R}$ $\mathbf {y} ^{1},\mathbf {y} ^{2}\in Y$ $u(\mathbf {y} ^{1})>u(\mathbf {y} ^{2})$ $\mathbf {y} ^{1}$ $\mathbf {y} ^{2}$ $u(\mathbf {y} ^{1})=u(\mathbf {y} ^{2})$ $\mathbf {y} ^{1}$ $\mathbf {y} ^{2}$ $u$

\max \;u(\mathbf {f} (\mathbf {x} )){\text{ soumis à }}\mathbf {x} \in X,

mais en pratique, il est très difficile de construire une fonction d'utilité qui représenterait avec précision les préférences du décideur - d'autant plus que le front de Pareto est inconnu avant le début de l'optimisation.

La méthode lexicographique suppose que les objectifs peuvent être classés par ordre d'importance. On peut supposer, sans perte de généralité, que les fonctions objectifs sont dans l'ordre d'importance de sorte que c'est la plus importante et la moins importante pour le décideur. La méthode lexicographique consiste à résoudre une séquence de problèmes d'optimisation à objectif unique de la forme ${\style d'affichage f_{1}}$ $f_{k}$

{\begin{aligned}\min &f_{l}(\mathbf {x} )\\{\text{st }}&f_{j}(\mathbf {x} )\leq \mathbf {y} _ {j}^{*},\;j=1,\dotsc ,l-1,\\&\mathbf {x} \in X,\end{aligned}}

où est la valeur optimale du problème ci-dessus avec . Ainsi, et chaque nouveau problème de la forme du problème ci-dessus dans la séquence ajoute une nouvelle contrainte au fur et à mesure que va de à . Notez qu'un objectif ou une valeur cible n'est spécifié pour aucun objectif ici, ce qui le rend différent de la méthode de programmation d'objectifs lexicographiques . $\mathbf {y} _{j}^{*}$ ${\style d'affichage l=j}$ $\mathbf {y} _{1}^{*}:=\min\{f_{1}(\mathbf {x} )\mid \mathbf {x} \in X\}$ ${\style d'affichage l}$ ${\style d'affichage 1}$ ${\style d'affichage k}$

Scalarisation

Scalariser un problème d'optimisation multi-objectifs est une méthode a priori, ce qui signifie formuler un problème d'optimisation mono-objectif tel que les solutions optimales au problème d'optimisation mono-objectif soient des solutions Pareto optimales au problème d'optimisation multi-objectif. De plus, il est souvent nécessaire que chaque solution optimale de Pareto puisse être atteinte avec certains paramètres de la scalarisation. Avec différents paramètres pour la scalarisation, différentes solutions optimales de Pareto sont produites. Une formulation générale pour une scalarisation d'une optimisation multiobjectif est donc

{\begin{array}{ll}\min &g(f_{1}(x),\ldots ,f_{k}(x),\theta )\\{\text{st }}x\in X_{\theta },\end{array}}

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

Des exemples très connus sont les soi-disant

scalarisation linéaire

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

où les poids des objectifs sont les paramètres de la scalarisation, et le

{\style d'affichage w_{i}>0}

${\style d'affichage \epsilon }$ -méthode de contrainte (voir, par exemple)

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

où les limites supérieures sont des paramètres comme ci-dessus et sont l'objectif à minimiser.

\epsilon _{j}

{\style d'affichage f_{j}}

Des exemples un peu plus avancés sont les suivants :

réalisation des problèmes de scalarisation de Wierzbicki . Un exemple des problèmes de scalarisation des réalisations peut être formulé comme suit :

{\begin{array}{ll}\min &\max _{i=1,\ldots ,k}\left[{\frac {f_{i}(x)-{\bar {z}} _{i}}{z_{i}^{\text{nad}}-z_{i}^{\text{utopian}}}}\right]+\rho \sum _{i=1}^{k }{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopian}}}}\\{\text{subject to }}&x\in S,\end{tableau}}

où le terme est appelé terme d'augmentation, est une petite constante, et et sont respectivement les vecteurs nadir et utopique . Dans le problème ci-dessus, le paramètre est ce que l'on appelle le point de référence qui représente les valeurs de fonction objectif préférées par le décideur.

\rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopian} }}}

{\style d'affichage \rho >0}

z^{\text{nad}}

z^{\text{utopian}}

{\bar {z}}

Programmation multi-objectifs de Sen

{\begin{array}{ll}\max &{\frac {\sum _{j=1}^{r}Z_{j}}{W_{j}}}-{\frac {\sum _{j=r+1}^{s}Z_{j}}{W_{r+1}}}\\{\text{st }}&AX=b\\&X\geq 0,\end{array} }

où est l'optimum individuel (Absolu) pour les objectifs de maximisation et de minimisation à .

{\style d'affichage W_{j}}

{\style d'affichage r}

{\style d'affichage r+1}

{\style d'affichage s}

Par exemple, l' optimisation de portefeuille est souvent menée en termes d' analyse moyenne-variance . Dans ce contexte, l'ensemble efficace est un sous-ensemble des portefeuilles paramétré par le rendement moyen du portefeuille dans le problème du choix des parts du portefeuille de manière à minimiser la variance du rendement du portefeuille sous réserve d'une valeur donnée de ; voir Théorème de séparation des fonds communs de placement pour plus de détails. Alternativement, l'ensemble efficace peut être spécifié en choisissant les parts du portefeuille de manière à maximiser la fonction ; l'ensemble des portefeuilles efficients est constitué des solutions car b va de zéro à l'infini. $\mu _{P}$ $\sigma _{P}$ $\mu _{P}$ $\mu _{P}-b\sigma _{P}$

Méthodes a posteriori

Les méthodes a posteriori visent à produire toutes les solutions optimales de Pareto ou un sous-ensemble représentatif des solutions optimales de Pareto. La plupart des méthodes a posteriori appartiennent à l'une des deux classes suivantes :

Programmation mathématique - méthodes a posteriori, où un algorithme est répété et chaque exécution de l'algorithme produit une solution optimale de Pareto ;
Algorithmes évolutionnaires où une exécution de l'algorithme produit un ensemble de solutions optimales de Pareto.

Des exemples bien connus de méthodes a posteriori basées sur la programmation mathématique sont les méthodes d'intersection de frontière normale (NBI), d'intersection de frontière normale modifiée (NBIm), de contrainte normale (NC), d'optimisation de Pareto successif (SPO) et de domaine de recherche dirigée (DSD) qui résolvent le problème d'optimisation multi-objectif en construisant plusieurs scalarisations. La solution de chaque scalarisation donne une solution optimale de Pareto, que ce soit localement ou globalement. Les scalarisations des méthodes NBI, NBIm, NC et DSD sont construites dans le but d'obtenir des points de Pareto uniformément répartis qui donnent une bonne approximation uniformément répartie de l'ensemble réel de points de Pareto.

Les algorithmes évolutionnaires sont des approches populaires pour générer des solutions optimales de Pareto à un problème d'optimisation multi-objectifs. Actuellement, la plupart des algorithmes d'optimisation multi-objectifs (EMO) évolutifs appliquent des schémas de classement basés sur Pareto. Les algorithmes évolutionnaires tels que l'algorithme de tri génétique non dominé-II (NSGA-II) et l'algorithme évolutionnaire de force Pareto 2 (SPEA-2) sont devenus des approches standard, bien que certains schémas basés sur l'optimisation d'un essaim de particules et le recuit simulé soient importants. Le principal avantage des algorithmes évolutionnaires, lorsqu'ils sont appliqués pour résoudre des 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 évolutionnaires est leur vitesse plus faible et l'optimalité de Pareto des solutions ne peut être garantie. On sait seulement qu'aucune des solutions générées ne domine les autres.

Un autre paradigme d'optimisation multi-objectifs basé sur la nouveauté utilisant des algorithmes évolutionnaires a été récemment amélioré. Ce paradigme recherche de nouvelles solutions dans l'espace objectif (c'est-à-dire une recherche de nouveauté dans l'espace objectif) en plus de la recherche de solutions non dominées. La recherche de nouveauté est comme un tremplin guidant la recherche vers des endroits auparavant inexplorés. Il est particulièrement utile pour surmonter les biais et les plateaux ainsi que pour guider la recherche dans les problèmes d'optimisation à objectifs multiples.

Les méthodes a posteriori communément connues sont listées ci-dessous :

Méthode des ε-contraintes
Branch-and-Bound à objectifs multiples
Intersection de frontière normale (NBI)
Intersection de frontière normale modifiée (NBIm) Contrainte normale (NC),
Optimisation de Pareto successive (SPO)
Domaine de recherche dirigée (DSD)
NSGA-II
PGEN (génération de surface de Pareto pour les instances multi-objectifs convexes)
IOSO (Optimisation Indirecte sur la Base de l'Auto-Organisation)
SMS-EMOA (algorithme multi-objectif évolutif de sélection S-métrique)
Approximation-Guided Evolution (premier algorithme à implémenter et optimiser directement le concept formel d' approximation issu de l'informatique théorique)
Optimisation de la recherche réactive (utilisant l'apprentissage automatique pour adapter les stratégies et les objectifs), implémentée dans LIONsolver
Algorithme de Benson pour les programmes linéaires à objectifs multiples et pour les programmes convexes à objectifs multiples
Optimisation d'essaims de particules multi-objectifs
Algorithme de sous-population basé sur la nouveauté

Méthodes interactives

Dans les méthodes interactives d'optimisation de problèmes à objectifs multiples, le processus de résolution est itératif et le décideur interagit en permanence avec la méthode lors de la recherche de la solution la plus préférée (voir par exemple Miettinen 1999, Miettinen 2008). En d'autres termes, le décideur est censé exprimer ses préférences à chaque itération afin d'obtenir des solutions Pareto optimales qui l'intéressent et d'apprendre quel type de solutions est réalisable.

Les étapes suivantes sont couramment présentes dans les méthodes interactives d'optimisation :

initialiser (par exemple, calculer les vecteurs objectifs nadir idéaux et approximatifs et les montrer au décideur)
générer un point de départ optimal de Pareto (en utilisant par exemple une méthode ou une solution sans préférence donnée par le décideur)
demander des informations de préférence au décideur (par exemple, niveaux d'aspiration ou nombre de nouvelles solutions à générer)
générer de nouvelles solutions optimales de Pareto en fonction des préférences et les montrer et éventuellement d'autres informations sur le problème au décideur
si plusieurs solutions ont été générées, demandez au décideur de sélectionner la meilleure solution à ce jour
arrêter (si le décideur le souhaite ; sinon, passez à l'étape 3).

Les niveaux d'aspiration ci-dessus se réfèrent à des valeurs de fonction objectif souhaitables formant un point de référence. Au lieu de la convergence mathématique qui est souvent utilisée comme critère d'arrêt dans les méthodes d' optimisation mathématique , une convergence psychologique est souvent mise en évidence dans les méthodes interactives. D'une manière générale, une méthode prend fin lorsque le décideur est convaincu d'avoir trouvé la solution la plus préférée disponible .

Types d'informations de préférence

Il existe différentes méthodes interactives impliquant différents types d'informations de préférence. Trois de ces types peuvent être identifiés en fonction de

informations sur les échanges,
points de référence et
classification des fonctions objectives.

D'autre part, un quatrième type de génération d'un petit échantillon de solutions est inclus : un exemple de méthode interactive utilisant des informations de compromis est la méthode Zionts-Wallenius , où le décideur se voit montrer plusieurs compromis objectifs à chaque itération, et (s) il est censé dire s'il aime, n'aime pas ou est indifférent à chaque compromis. Dans les méthodes basées sur les points de référence (voir par exemple), le décideur doit à chaque itération spécifier un point de référence composé des valeurs souhaitées pour chaque objectif et une ou plusieurs solutions optimales de Pareto correspondantes sont ensuite calculées et présentées pour analyse. . Dans les méthodes interactives basées sur la classification, le décideur est supposé donner des préférences sous la forme de classer les objectifs à la solution optimale de Pareto actuelle en différentes classes indiquant comment les valeurs des objectifs doivent être modifiées pour obtenir une solution plus préférée. Ensuite, les informations de classification fournies sont prises en compte lorsque de nouvelles solutions optimales de Pareto (plus préférées) sont calculées. Dans la méthode du compromis satisfaisant (STOM), trois classes sont utilisées : les objectifs dont les valeurs 1) doivent être améliorées, 2) peuvent être assouplies et 3) sont acceptables en tant que telles. Dans la méthode NIMBUS, deux classes supplémentaires sont également utilisées : les objectifs dont les valeurs 4) doivent être améliorées jusqu'à une borne donnée et 5) peuvent être relâchées jusqu'à une borne donnée.

Méthodes hybrides

Différentes méthodes hybrides existent, mais nous envisageons ici d'hybrider MCDM ( prise de décision multicritères ) et EMO (optimisation multi-objectifs évolutive). Un algorithme hybride dans le contexte de l'optimisation multi-objectifs est une combinaison d'algorithmes/d'approches de ces deux domaines (voir par exemple). Les algorithmes hybrides EMO et MCDM sont principalement utilisés pour surmonter les lacunes en utilisant les forces. Plusieurs types d'algorithmes hybrides ont été proposés dans la littérature, par exemple en incorporant des approches MCDM dans les algorithmes EMO en tant qu'opérateur de recherche local et pour diriger un DM vers la ou les solutions les plus préférées, etc. de convergence des algorithmes EMO.

Les racines de l'optimisation hybride multi-objectifs remontent au premier séminaire Dagstuhl organisé en novembre 2004 (voir, ici ). Ici, certains des meilleurs esprits d'EMO (Professeur Kalyanmoy Deb, Professeur Jürgen Branke, etc.) et MCDM (Professeur Kaisa Miettinen, Professeur Ralph E. Steuer, etc.) ont réalisé le potentiel de combiner les idées et les approches des domaines MCDM et EMO pour préparer des hybrides. d'eux. Par la suite, de nombreux autres séminaires Dagstuhl ont été organisés pour favoriser la collaboration. Récemment, l'optimisation hybride multi-objectifs est devenue un thème important dans plusieurs conférences internationales dans le domaine de l'EMO et du MCDM (voir par exemple)

Visualisation du front de Pareto

La visualisation du front de Pareto est l'une des techniques de préférence a posteriori de l'optimisation multi-objectifs. Les techniques de préférence a posteriori fournissent une classe importante de techniques d'optimisation multi-objectifs. Habituellement, les techniques de préférence a posteriori comprennent quatre étapes : (1) l'ordinateur se rapproche du front de Pareto, c'est-à-dire l'ensemble optimal de Pareto dans l'espace objectif ; (2) le décideur étudie l'approximation du front de Pareto ; (3) le décideur identifie le point préféré sur le front de Pareto ; (4) l'ordinateur fournit la décision optimale de Pareto, dont la sortie coïncide avec le point objectif identifié par le décideur. Du point de vue du décideur, la deuxième étape des techniques de préférence a posteriori est la plus compliquée. Il existe deux approches principales pour informer le décideur. Premièrement, un certain nombre de points du front de Pareto peuvent être fournis sous forme de liste (une discussion et des références intéressantes y sont données) ou à l'aide de cartes thermiques.

Visualisation dans les problèmes bi-objectifs : courbe de compromis

Dans le cas de problèmes bi-objectifs, l'information du décideur concernant le front de Pareto se fait généralement par sa visualisation : le front de Pareto, souvent nommé courbe de compromis dans ce cas, peut être tracé au niveau du plan objectif. La courbe de compromis donne des informations complètes sur les valeurs des objectifs et sur les compromis objectifs, qui indiquent comment l'amélioration d'un objectif est liée à la détérioration du second tout en se déplaçant le long de la courbe de compromis. Le décideur prend cette information en compte tout en spécifiant le point objectif optimal de Pareto préféré. L'idée d'approximer et de visualiser le front de Pareto a été introduite pour les problèmes de décision bi-objectif linéaire par S.Gass et T.Saaty. Cette idée a été développée et appliquée aux problèmes environnementaux par JL Cohon. Une revue des méthodes d'approximation du front de Pareto pour divers problèmes de décision avec un petit nombre d'objectifs (principalement deux) est fournie dans.

Visualisation dans les problèmes d'optimisation multi-objectifs d'ordre élevé

Il existe deux idées génériques sur la façon de visualiser le front de Pareto dans les problèmes de décision multi-objectifs d'ordre élevé (problèmes avec plus de deux objectifs). L'une d'elles, applicable dans le cas d'un nombre relativement faible de points objectifs qui représentent le front de Pareto, repose sur l'utilisation des techniques de visualisation développées en statistique (diagrammes divers, etc. – voir la sous-section correspondante ci-dessous). La deuxième idée propose l'affichage de sections transversales bi-objectifs (tranches) du front de Pareto. Il a été introduit par WS Meisel en 1973 qui a fait valoir que de telles tranches informent le décideur sur les compromis objectifs. Les figures qui affichent une série de tranches bi-objectifs du front de Pareto pour des problèmes à trois objectifs sont appelées cartes de décision. Ils donnent une image claire des compromis entre trois critères. Les inconvénients d'une telle approche sont liés aux deux faits suivants. Premièrement, les procédures de calcul pour construire les tranches bi-objectifs du front de Pareto ne sont pas stables puisque le front de Pareto n'est généralement pas stable. Deuxièmement, elle n'est applicable que dans le cas de trois objectifs seulement. Dans les années 1980, l'idée de WS Meisel a été mise en œuvre sous une forme différente - sous la forme de la technique des cartes de décision interactives (IDM). Plus récemment, N. Wesner a proposé d'utiliser une combinaison d'un diagramme de Venn et de plusieurs points de vue de l'espace objectif pour l'exploration de la frontière de Pareto et la sélection de solutions optimales.

Languages

In other projects