Chapitre 1: Notions de base de l’optimisation multi-objectifs PDF

Chapitre 1: Notions de base de l’optimisation multi- objectifs 1 Introduction Dans la plupart des problèmes du monde réel, il ne s’agit pas d’optimiser seulement une seule fonction objectif (critère) mais plutôt d’optimiser simultanément plusieur...

Chapitre 1: Notions de base de l’optimisation multi- objectifs 1 Introduction Dans la plupart des problèmes du monde réel, il ne s’agit pas d’optimiser seulement une seule fonction objectif (critère) mais plutôt d’optimiser simultanément plusieurs fonctions (critères) et qui sont géné- ralement conflictuelles ou contradictoires. Le résultat d’un problème d’optimisation multi-critères est généralement une variété de solutions, différenciées par différents arbitrages entre objectifs. Ces solutions sont optimales lorsque tous les objectifs sont considérés simultanément car aucune autre solution dans l’espace de recherche n’est meilleure qu’elles. Elle possède ses racines dans le 19ème siècle dans les travaux en économie de Edgeworth et Pareto. Elle a été utilisée initialement en économie et dans les sciences de management et graduellement dans les sciences pour l’ingénieur. Dans les problèmes de gestion de production, par exemple, il faut le plus souvent maximiser les bénéfices et minimiser les coûts (Achat de matières premières, salaires, économiser l’énergie, etc.). Ce chapitre présente les notions de base de l’optimisation multi-objectifs, en ce qui concerne quelques définitions qui portent sur les solutions et la classification des algorithmes de résolution. 2 Formulation générale d’un problème d’optimisation multi-objectifs Un problème multi-objectifs (PMO) peut être défini de la manière suivante :   min F (x) = f (x), f (x),... , f (x)
1 2 n (P M O)  s.c. x ∈ C où n ≥ 2 est le nombre de fonctions objectifs, x = (x1 ,... , xk ) est le vecteur représentant les variables de décision, C représente l’ensemble des solutions réalisables associé à des contraintes d’égalité, d’inégalité
et des bornes explicites (espace de décision) et F (x) = f1 (x), f2 (x),... , fn (x) est le vecteur des critères à optimiser. Dans le cadre de l’optimisation multi-objectifs, le plus souvent le décideur raisonne plutôt en termes d’évaluation d’une solution sur chaque critère et se place naturellement dans l’espace des critères. L’ensemble Y = F (C) représente les solutions réalisables dans l’espace des critères (espace objectifs), où une solution réalisable ou admissible est une solution qui satisfait toutes les contraintes, et y = (y1 ,... , yn ) avec yi = fi (x) , 1 ≤ i ≤ n est un point de l’espace des critères. La principale difficulté des problèmes multi-objectifs est qu’il n’y a pas de définition de la solution optimale. Les décideurs peuvent simplement exprimer le fait qu’une solution est meilleure qu’une autre, mais qu’aucune solution n’est meilleure que toutes les autres. Par conséquent, la résolution de problèmes multi-objectifs ne réside pas dans la recherche de la solution optimale, mais dans un ensemble de solutions satisfaisantes pour lesquelles on ne peut pas classer les opérations. Elle procède donc par la définition au préalable des critères de qualité de la solution 1 MRETCA1 Cours Optimisation multi-objectifs du problème, puis l’algorithme d’optimisation va résoudre le problème en cherchant les meilleures solutions en fonction de ces critères. Ainsi, la formulation du problème d’optimisation multi-objectifs comporte les étapes suivantes : Exprimer les critères (ou fonctions objectifs) d’optimalité. Choisir les paramètres (ou variables) d’optimisation. Définir un espace admissible pour les variables d’optimisation. Définir les contraintes associées. 3 Notions de dominance et optimalité de Pareto Dans l’optimisation mono-objectif, la solution optimale peut être unique ou multiple mais la valeur de la fonction objectif est unique. Dès que l’optimisation devient multi-objectifs, la notion de solution optimale n’a aucun sens. On parle de solution efficace ou solution optimale au sens de Pareto ou solution non dominée. 3.1 Solution optimale au sens de Pareto et relation de dominance L’optimisation multi-objectifs cherche donc à optimiser plusieurs composantes d’un vecteur fonction coût. Contrairement à l’optimisation uni-objectif, la solution d’un problème multi-objectifs (PMO) n’est pas une solution unique, mais un ensemble de solutions connu comme l’ensemble des solutions Pareto optimales (PO). Toute solution de cet ensemble est optimale dans le sens qu’aucune amélioration ne peut être faite sur une composante du vecteur sans dégradation d’au moins une autre composante. Le premier objectif dans la résolution d’un problème multi-objectifs est d’obtenir l’ensemble PO des solutions Pareto optimales. A la fin du 19ème siècle, l’économiste Vilfredo Pareto formule le concept d’optimalité qui porte son nom (optimalité au sens de Pareto), qui constitue les origines de la recherche sur l’optimisation multi-objectifs où la notion d’optimalité dans l’optimisation mono-objectif n’a aucun sens. En effet, elle n’existe aucune solution réalisable x qui fasse diminuer un objectif sans augmenter dans le même temps au moins un autre objectif. Cependant, dans la plupart des cas, l’optimum de Pareto n’est pas constitué d’une seule solution mais d’un ensemble de solutions de “meilleur compromis” appelées solutions efficaces ou solutions non-dominées. La recherche de la solution optimale pour un problème d’optimisation multi-objectifs soulève quelques réflexions par rapport à la notion même de l’optimalité. En effet, il est impossible de trouver une solution optimale unique pour un problème multi-objectif, car il n’y a aucune combinaison des variables de dé- cisions qui minimise (ou maximise) toutes les composantes du vecteur F simultanément. Les problèmes multi-objectifs ont en général un ensemble de solutions optimales dont les valeurs des fonctions sont en fait les meilleurs compromis possibles dans l’espace des fonctions objectifs. Il faut donc utiliser une autre définition de la “meilleure solution”, afin de déterminer exactement quelle solution peut être considérée meilleure par rapport à une autre. Le concept de “l’optimalité de Pareto” (Pareto, 1896) est ainsi utilisé pour établir une hiérarchie entre les solutions d’un problème multi-objectifs en vue de déterminer si une solution appartient réellement à l’ensemble des meilleurs compromis. Pour mieux comprendre le concept de l’optimalité de Pareto, on introduit d’abord la notion de “dominance de Pareto”. Soient deux vecteurs U et V dans l’espace des fonctions objectifs où un problème de minimisation est considéré. On dit que le vecteur U = (u1 , u2 ,... , um ) domine le vecteur V = (v1 , v2 ,... , vm ), si et Enseignante 2 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs seulement si toutes les composantes de U sont inférieures ou égales à celles correspondantes dans V , et au moins une composante de U est strictement inférieure à celle correspondante dans V. Une solution X = (x1 , x2 ,... , xn ) d’un problème multi-objectifs est dite “Pareto optimale” par rapport à l’espace entier des variables de décision si et seulement s’il n’existe aucune autre solution X ′ = (x′1 , x′2 ,... , x′n ) telle que la fonction F (X ′ ) = f1 (X ′ ), f2 (X ′ ),... , fm (X ′ ) domine F (X) = f1 (X), f2 (X),... , fm (X).

L’ensemble des solutions optimales est appelé “ensemble Pareto optimal”, et l’ensemble des valeurs des fonctions objectifs correspondantes dans l’espace des fonctions objectifs est appelé “front de Pareto”. Selon les problèmes à traiter, le front de Pareto peut avoir une configuration très complexe (e.g., continuité, discontinuité, convexité, disjonction, etc.). Dans le contexte de l’optimisation multi-objectifs, on vise en général à : trouver l’ensemble des solutions Pareto optimales, c’est-à-dire celles qui couvrent tout le front de Pareto. s’assurer que les solutions soient suffisamment différentes les unes des autres et qu’elles ne soient pas biaisées en favorisant un objectif particulier. 3.2 Solution Pareto optimale La définition de solution Pareto optimale découle directement de la notion de dominance. Elle signifie qu’il est impossible de trouver une solution qui améliore les performances sur un critère sans que cela entraîne une dégradation des performances sur au moins un autre critère. L’idée d’utiliser la dominance au sens de Pareto a été proposée par Goldberg pour résoudre les problèmes multi-objectifs. Il suggère d’utiliser le concept d’optimalité de Pareto pour respecter l’intégralité de chaque objectif car il refuse de comparer à priori les valeurs de différents objectifs. En 1896, le mathématicien italien Vilfredo Pareto a posé les bases de la solution d’un problème économique multi-objectifs : “Dans un problème multi-objectifs, il existe un équilibre tel que l’on ne peut améliorer un critère sans détériorer au moins un des autres”. Cet équilibre est appelé optimum Pareto. Donc une solution x∗ est dite Pareto optimale si elle n’est dominée par aucune autre solution appartenant à l’espace réalisable X. Cette solution est appelée solution non dominée ou non inférieure. Une solution y = (y1 ,... , yn ) domine une solution z = (z1 ,... , zn ) ssi ∀ i ∈ [1, n], yi ≤ zi et ∃ i ∈ [1, n]/yi < zi. On a rarement un vecteur x∗ qui est optimum pour tous les objectifs tel que : ∀ x ∈ C, fi (x∗ ) ≤ fi (x) , 1 ≤ i ≤ n Une solution x∗ ∈ C est Pareto optimale ssi il n’existe pas une solution x ∈ C tel que F (x) domine F (x∗ ). 3.3 Solution supportée Une solution supportée est la solution du système suivant : n   X  min F (x) =  λi fi (x) (P M Oλ ) i=1   s.c. x ∈ C  n X avec λi ≥ 0, ∀ 1 ≤ i ≤ n et λi = 1. La figure 1 montre un exemple de la répartition des solutions i=1 supportées et non supportées. Enseignante 3 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs Figure 1 – Solutions supportées et non supportées. 3.4 Solution non-dominée ou non-inférieure Une solution z dans Z est non-dominée ou non-inférieure s’il n’existe pas un autre point z ′ dans Z tel que z ′ domine z. Les solutions Pareto optimales sont aussi connues sous le nom de solutions admissibles, efficaces, non-dominées et non-inférieures. 3.5 Ensemble de Pareto optimal (PO) Pour un problème d’optimisation multi-objectifs, on considère le vecteur F à optimiser : F (x) = [f1 (x), f2 (x),... , fk (x)]T L’ensemble exact de toutes les solutions Pareto optimales ou l’ensemble de Pareto optimal (PO) est défini par : P O = {x ∈ C|¬∃x′ ∈ C : F (x′ ) ≤ F (x)} 3.6 Front de Pareto ou Frontière de Pareto (F P ) Par définition, le front de Pareto est l’ensemble généralement constitué par l’image des solutions efficaces dans l’espace des objectifs. La figure 2 montre le front de Pareto pour les différentes situations envisa- geables pour un problème à deux objectifs. On note que le front de Pareto de chaque cas est la partie rouge de l’ensemble. Pour un problème d’optimisation multi-objectifs de l’ensemble des fonctions F (x) avec P O est l’ensemble de Pareto optimal, le Front de Pareto (ou la frontière de Pareto) noté F P est défini comme suit :
F P = {F = f1 (x), f2 (x),... , fk (x) |x ∈ P O} Figure 2 – Front de Pareto d’un problème d’optimisation multi-objectifs. Enseignante 4 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs 3.7 Points caractéristiques : Point idéal et Point de Nadir Le vecteur idéal y ∗ = (y1∗ ,... , ym ∗ ) est obtenu en optimisant séparément chaque fonction objectif fi , i.e. yi∗ = fi (x∗ ), x ∈ C. Généralement, ce vecteur n’appartient pas à l’espace objectif réalisable, mais il est dans certains cas utile en tant que référence, par exemple, pour normaliser les valeurs des objectifs. A la différence du vecteur idéal qui représente les bornes inférieures de chaque objectif dans l’espace faisable, le vecteur de Nadir correspond à leurs bornes supérieures (voir Figure 3) et il sert à restreindre l’espace de recherche. Figure 3 – Représentation des solutions supportées et non supportées, point idéal et point de Nadir. 4 Classification des algorithmes d’optimisation multi-objectifs Les méthodes traditionnelles d’optimisation présentent beaucoup de lacunes en résolvant un problème multi-objectifs à cause des raisons principales suivantes : Elles sont incapables de trouver l’ensemble des solutions en une seule exécution de l’algorithme d’optimisation, qui doit alors être exécuté plusieurs fois pour trouver autant de solutions Pareto optimales recherchées. L’ensemble des solutions trouvées en suivant cette procédure ne garantit pas que les solutions trouvées soient différentes les unes des autres. Elles sont incapables de traiter des problèmes ayant plusieurs solutions optimales. Les approches utilisées pour la résolution de PMO peuvent être classées en trois catégories : Approches basées sur la transformation du problème en un problème uni-objectif : Cette classe d’approches comprend par exemple les méthodes basées sur l’agrégation qui combinent les diffé- rentes fonctions coût fi du problème en une seule fonction objectif F. Ces approches nécessitent pour le décideur d’avoir une bonne connaissance de son problème. Approches non-Pareto : Les approches non-Pareto ne transforment pas le PMO en un problème uni- objectif. Elles utilisent des opérateurs de recherche qui traitent séparément les différents objectifs. Approches Pareto : Les approches Pareto utilisent directement la notion d’optimalité Pareto dans leur processus de recherche. Le processus de sélection des solutions générées est basé sur la notion Enseignante 5 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs de non-dominance. 4.1 Méthodes à base de transformation du problème vers l’uni-objectif Dans la résolution de PMO, plusieurs méthodes traditionnelles transforment le PMO en un problème uni-objectif. Parmi ces méthodes, on trouve la méthode d’agrégation et la méthode ϵ-contrainte. 4.1.1 Méthode d’agrégation C’est l’une des premières méthodes utilisées pour la génération de solutions Pareto optimales. Elle consiste à transformer le problème (PMO) en un problème qui revient à combiner les différentes fonctions coût fi du problème en une seule fonction objectif F généralement de façon linéaire : n X F (x) = λi fi (x) i=1 n X où les poids λi ∈ [0 1] et λi = 1. i=1 4.1.2 Méthode ϵ-contrainte Dans cette approche, le problème consiste à optimiser une fonction fk sujette à des contraintes sur les autres fonctions.   min fk (x)  
 P M Ok (ϵ) s.c. fj (x) ≤ ϵj , j = 1, · · · , n, j ̸= k    x∈C  où ϵ = {ϵ1 ,... , ϵk−1 , ϵk+1 ,... , ϵn }. Ainsi, un problème uni-objectif (objectif fk ) sujet des contraintes sur les autres objectifs est résolu. 4.2 Approches non-Pareto Dans les approches non-Pareto basées sur les populations de solutions, la recherche est réalisée en trai- tant séparément les différents objectifs non commensurables. L’inconvénient majeur de ces approches est qu’elles tendent à générer des solutions qui sont largement optimisées pour certains objectifs au détriment des autres objectifs. Les solutions “compromis” sont négligées. 4.2.1 Sélection parallèle dans les algorithmes évolutionnistes Les algorithmes évolutionnistes s’inspirent de la théorie de l’évolution pour résoudre des problèmes d’op- timisation. Leur principe est de faire évoluer un ensemble de solutions à un problème donné afin de trouver les meilleurs résultats. Ces algorithmes sélectionnent les individus de la population courante sui- vant chaque objectif, indépendamment des autres (sélection parallèle). A chaque génération, la population est donc divisée en un nombre de sous-populations qui est égal au nombre d’objectifs de la fonction coût. Chaque sous-population i est sélectionnée suivant l’objectif fi. L’algorithme évolutionniste compose la po- pulation complète et applique ses opérateurs. Comme l’algorithme affecte aléatoirement les individus aux sous-populations à chaque génération, un même individu peut être evalué différemment suivant l’objectif qui lui est affecté d’une génération à l’autre. Enseignante 6 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs 4.2.2 Sélection lexicographique Dans cette approche classique, la sélection est réalisée suivant un ordre défini par le décideur. Cet ordre définit l’ordre d’importance des objectifs. 4.3 Approches Pareto Les approches Pareto utilisent directement la notion de dominance dans la sélection des solutions générées, contrairement aux autres approches qui utilisent une seule fonction coût ou traitent séparément les différents objectifs. Le principal avantage de ces approches est qu’elles sont capables de générer des solutions Pareto optimales dans les portions de la frontière Pareto. 4.3.1 Méthode de classement Cette méthode consiste à classer les solutions par rang selon leur dominance. 4.3.2 Méthodes de maintenance de la diversité Dans la résolution de PMO, il est nécessaire que les solutions trouvées soient Pareto optimales, mais aussi qu’elles soient uniformément réparties dans le sous-espace des solutions Pareto optimales. Pour maintenir une diversité dans la population, un certain nombre de techniques basées sur les algorithmes évolutionnistes ont été proposées pour la conservation de la diversité. Par exemple, dans la reproduction d’un nouvel individu, l’opérateur consiste à remplacer l’individu existant le plus semblable à l’individu généré, et non pas les parents comme dans les algorithmes génétiques standards. 5 Les méta-heuristiques 5.1 Définition et principe Le mot méta-heuristique est dérivé de deux mots grecs “méta” qui signifie au-delà dans un niveau supérieur et “heuristique” qui signifie l’art d’inventer et de faire des découvertes. La décomposition étymologique du mot permet ainsi de comprendre son sens : une heuristique qui permet de trouver d’autres heuristiques et qui favorise l’émergence. Pour rappel, les heuristiques sont des règles empiriques simples qui ne se basent pas sur des analyses scientifiques parfois complexes, mais sur l’expérience et les relations accumulées au fil des résultats. Ces règles utilisent donc simplement les résultats passés afin d’optimiser les recherches futures en examinant d’abord les cas les plus plausibles. Plus simplement, on dira que les méta-heuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficiles, souvent issus du domaine de la recherche opérationnelle, de l’ingénierie ou de l’intelligence artificielle. Elles sont apparues au début des années 1980 afin de s’attaquer aux problèmes d’optimisation difficiles pour lesquels on ne connaît pas de méthodes d’optimisation classiques plus efficaces. Elles partent en général d’une solution arbitraire, puis progressent dans la recherche jusqu’à ce qu’un critère d’arrêt spécifié soit atteint. Ces algorithmes essaient donc de trouver une approximation de la meilleure solution. La qualité de la solution obtenue résulte donc d’un compromis avec le temps de calcul. Pour améliorer l’efficacité de la recherche, des méthodes déterministes sont souvent utilisées pour générer des solutions de base servant à l’initialisation des algorithmes méta-heuristiques. Enseignante 7 Karama Koubaâ MRETCA1 Cours Optimisation multi-objectifs 5.2 Intérêt des méta-heuristiques Résoudre un problème d’optimisation multi-objectifs peut donc s’avérer long et fastidieux si des mé- thodes appropriées ne sont pas mises en oeuvre. En milieu industriel où les problèmes d’optimisation sont très complexes (e.g., multiples objectifs, plusieurs variables et contraintes, non-linéarités), le temps de recherche des solutions optimales devient également un facteur important à prendre en compte. La recherche de l’ensemble de Pareto est très coûteuse en termes de temps de calcul et même irréalisable la plupart du temps. A cause de la complexité des critères à minimiser, les méthodes exactes sont rarement applicables. C’est ainsi que les “méta-heuristiques” sont généralement utilisées pour résoudre ces types de problèmes, en recherchant, à défaut de trouver l’optimum global, à se rapprocher aussi près que pos- sible de ce dernier, en faisant un compromis avec le temps de calcul. Un des avantages bien connu des méta-heuristiques est leur capacité de résoudre les problèmes sans connaissance à priori des formulations mathématiques de ces derniers. 6 Conclusion L’optimisation multi-objectifs permet de modéliser des problèmes et offre des méthodes de résolution efficaces. Elle est un cadre formel permettent l’expression de problèmes puis leur résolution. Au cours de ce chapitre, on a présenté des notions de base de l’optimisation multi-objectifs, où on a donné une formulation générale du problème et des définitions qui portent sur la nature des solutions et l’optimalité de Pareto. On a donné aussi une classification des algorithmes d’optimisation multi-objectifs et on a expliqué l’intérêt des méta-heuristiques dans ce type de problèmes d’optimisation. Enseignante 8 Karama Koubaâ