Optimisation multiobjectif et problèmes d’optimisation mono-objectifs

OPTIMISATION MULTIOBJECTIF – CHAPITRE II :
I. INTRODUCTION :
II. DEFINITIONS D’UN PROBLEME :
II.1. TYPES DES PROBLEMES :
II.1.1. UN PROBLEME DE DECISION:
II.1.2. UN PROBLEME POLYNOMIAL REDUCTIBLE
II.1.3. UN PROBLEME DE LA CLASSE P:
II.1.4. UN PROBLEME DE LA CLASSE NP:
II.1.5. UN PROBLEME DE LA CLASSE NP-HARD:
II.1.6. UN PROBLEME DE LA CLASSE NP-COMPLET:
III. LES PROBLEMES D’OPTIMISATION MONO-OBJECTIFS :
III.1. CONTRAINTES
IV. PROBLEME D’OPTIMISATION MULTIOBJECTIF :
IV.1. DEFINITION :
IV.2. CLASSIFICATION DES PROBLEMES D’OPTIMISATION MULTIOBJECTIF :
IV.2.1. CLASSIFICATION « POINT DE VUE DECIDEUR » :
IV.2.2. CLASSIFICATION « POINT DE VUE CONCEPTEUR » :
V. APPROCHES DE RESOLUTION MULTIOBJECTIF :
V.1. NOTION DE DOMINANCE
V.2. APPROCHE PARETO :
V.2.1. DEFINITION 1
V.2.2. DEFINITION2
V.2.3. OPTIMALITE DE PARETO
VI. CONCLUSION

I. Introduction :

L’optimisation multiobjectif est un axe de recherche très important à cause de la nature multiobjectif de la plupart des problèmes réels. Les premiers travaux menés sur les problèmes multiobjectifs furent réalisés au 19éme siècle sur des études en économie par Edgeworth et généralisés par Pareto.
L’optimisation multiobjectif est un domaine fondamental de l’aide a la décision multicritère, auquel de nombreux milieux scientifiques et industriels se doivent faire face, la résolution d’un problème d’optimisation multiobjectif consiste a déterminer la solution correspondant au mieux aux préférences du décideur parmi les solutions de bonne compromis.
Dans la plupart des problèmes du monde réel, il ne s’agit pas d’optimiser seulement un seul critère mais plutôt d’optimiser simultanément plusieurs critères et qui sont généralement conflictuels. Dans les problèmes de conception, par exemple, il faut le plus souvent trouver un compromis entre des besoins technologiques et des objectifs de coût. L’optimisation multiobjective consiste donc à optimiser simultanément plusieurs fonctions. La notion de solution optimale unique dans l’optimisation uni-objective disparait pour les problèmes d’optimisation multiobjective au profit de la notion d’ensemble de solutions Pareto optimales.

II. Définitions d’un problème :

Un problème d’optimisation est défini par :
– un espace de recherche (de décision) : ensemble de solutions ou de configurations constitué des différentes valeurs prises par les variables de décision .
– une ou plusieurs fonction(s) dite objectif(s) , à optimiser (minimiser ou maximiser)
– un ensemble de contraintes à respecter. [8]
Dans la plupart des problèmes, l’espace d’état (décision) est fini ou dénombrable. Les variables du problème peuvent être de nature diverse (réelle, entier, booléenne, etc.) et exprimer des données qualitatives ou quantitatives. La fonction objectif représente le but à atteindre pour le décideur. L’ensemble de contrainte définit des conditions sur l’espace d’état que les variables doivent satisfaire. Ces contraintes sont souvent des contraintes d’inégalité ou d’égalité et permettent en général de limiter l’espace de recherche (solutions réalisables). La résolution optimale du problème consiste à trouver le point ou un ensemble de points de l’espace de recherche qui satisfait au mieux la fonction objectif. Le résultat est appelé valeur optimale ou optimum . Néanmoins en raison de la taille des problèmes réels, la résolution optimale s’est souvent montrée impossible dans un temps raisonnable. Cette impossibilité technique impose la résolution approchée du problème, qui consiste à trouver une solution de bonne qualité (la plus proche possible de l’optimum). Il est vital pour déterminer si une solution est meilleure qu’une autre, que le problème introduise un critère de comparaison ( une relation d’ordre ). La plupart des problèmes d’optimisations appartiennent à la classe des problèmes NP-difficile classe où il n’existe pas d’algorithme qui fournit la solution optimale en temps polynomial en fonction de la taille du problème et le nombre d’objectifs à optimiser. Dans la littérature il existe des problèmes académiques utilisés comme des benchmarks : sac à dos, les fonctions de Schäfer, voyageur de commerce, Flowshop, … et des problèmes réels (applications industrielles) : télécommunications, transport, environnement,…

II.1. Types des problèmes :

Les problèmes peuvent être classes selon les propriétés de l’ensemble des solutions :

II.1.1. Un problème de décision:

C’est un problème dont la réponse est tout simplement oui ou non.

II.1.2. Un problème polynomial réductible:

On a L1 et L2 deux problèmes de décision, on dit L1 est polynomial réductible a L2 s’il existe un algorithme polynomial qui convertit chaque instance d’entrée de L1 a une autre instance de L2.

II.1.3. Un problème de la classe P:

Un problème est dit polynomial s’il existe un algorithme de complexité polynomiale permettant de répondre a la question posée dans ce problème, quelque soit la donnée de celui- ci. La classe P est l’ensemble de tous les problèmes de reconnaissances polynomiaux.

II.1.4. Un problème de la classe NP:

Un problème de reconnaissance est dans la classe NP si, pour toute instance de ce problème, on peut vérifier, en un temps polynomial par rapport a la taille de l’instance, qu’une solution proposée ou devinée permet d’affirmer que la présence est ( oui ) pour cette instance.

II.1.5. Un problème de la classe NP-hard:

On dit qu’un problème est dans la classe NP-hard si chaque autre problème dans NP est réductible d’une manière polynomiale dans ce dernier.

II.1.6. Un problème de la classe NP-complet:

S’il appartient a NP et chaque autre problème dans NP est réductible d’une manière polynomiale dans ce dernier. C’est un problème de décision et NP-hard qui cherche à trouver l’optimum.

III. Les problèmes d’optimisation mono-objectifs :

Lorsqu’un seul objectif (critère) est donné, le problème d’optimisation est mono-objectif. Dans ce cas la solution optimale est clairement définie, c’est celle qui a le coût optimal (minimal, maximal). De manière formelle, à chaque instance d’un tel problème est associé un ensemble W des solutions potentielles respectant certaines contraintes et une fonction d’objectif W ϵ Y qui associe à chaque solution admissible s de W une valeur (s). Résoudre l’instance (W) du problème d’optimisation consiste à trouver la solution optimale s* de W qui optimise (minimise ou maximise) la valeur de la fonction objective pour le cas de la minimisation : le but est de trouver s* de W tel que (s*) ϵ (s) pour tout élément s de W. Un problème de maximisation peut être défini de manière similaire. [8]

III.1. Contraintes :

Dans la plupart des problèmes d’optimisation, des restrictions sont imposées par les caractéristiques du problème. Ces restrictions doivent être satisfaites afin de considérer une Solution acceptable.
Cet ensemble de restrictions, appelées contraintes , décrit les dépendances entre les variables de décision et les paramètres du problème. On formule usuellement ces contraintes cj par un ensemble d’inégalités, ou d’égalités de la forme : cj(x1, x2, …, xn) ≥ 0.

IV. Problème d’optimisation Multiobjectif :

La plupart des problèmes d’optimisation réels sont décrits a l’aide de plusieurs objectifs ou critères souvent contradictoires devant être optimises simultanément. Alors que, pour les problèmes n’incluant qu’un seul objectif, l’optimum recherché est clairement défini, celui-ci reste à formaliser pour les problèmes d’optimisation multiobjectif. En effet, pour un problème à deux objectifs contradictoires, la solution optimale cherchée est un ensemble de points correspondant aux meilleurs compromis possibles pour résoudre notre problème.
Exemple :
Dans le cas de deux objectifs à minimiser, toute amélioration de l’un des objectifs se fait au détriment de l’autre et que la solution optimale ou proche de l’optimum est un compromis entre les deux. Dans l’achat d’une voiture d’occasion, la voiture idéale est celle qui est peu chère (critère économique) avec peu de kilomètres (critère qualitatif), il n’est pas évident de pouvoir regrouper en un seul objectif ces deux critères non commensurables.
Ainsi il n’existe plus une solution optimale unique mais un ensemble de solutions. Nous allons donc devoir identifier les meilleurs compromis possibles suivant notre budget.
Les problèmes multiobjectifs ont la particularité d’être beaucoup plus difficiles à traiter que leur équivalent mono-objectif. La difficulté réside dans l’absence d’une relation d’ordre total entre les solutions.
Une solution peut être meilleure qu’une autre sur certains objectifs et moins bonne sur les autres. Donc il n’existe généralement pas une solution unique qui procure simultanément la solution optimale pour l’ensemble des objectifs. Voilà pourquoi le concept de solution optimale devient moins pertinent en optimisation multiobjectif. Dans ce cas la solution optimale ou de bonne qualité n’est plus une solution unique mais, un ensemble de solutions compromis entre les différents objectifs à optimiser. Il est vital pour identifier ces meilleurs compromis de définir une relation d’ordre entre ces éléments. La plus célèbre et la plus utilisée est la relation de dominance au sens Pareto . L’ensemble des meilleurs compromis est appelé le front Pareto, la surface de compromis ou l’ensemble des solutions efficaces. Cet ensemble de solutions constitue un équilibre, dans le sens qu’aucune amélioration ne peut être faite sur un objectif sans dégradation d’au moins un autre objectif. La solution Pareto consiste à obtenir le front de Pareto.

IV.1. Définition :

Un problème d’optimisation multiobjectif MOP (multiobjective optimization problem) peut être défini comme suit :

Où n est le nombre d’objectifs (n≥ 2), X est l’ensemble des solutions réalisable dans l’espace décisionnel, et x =(x1, x2, ……,xk) ∈ X est un vecteur representant les variables de décision, dans le cas combinatoire x est un ensemble discret, a chaque solution x ∈ X est associé un vecteur objectif z ∈ Z sur la base d’un vecteur de fonction f : X→ Z tel que z = (z1, z2, …zn) = f(x) = (f1(x), f2(x), …. fn(x)), ou Z = f(X) représente l’ensemble des points réalisable. [9]

Fig.1 : espace décisionnel et espace objectif d’un problème d’optimisation Multiobjectif (exemple avec deux variables de décision et de fonction objectif).

IV.2. Classification des problèmes d’optimisation multiobjectif :

Dans notre recherche, nous rencontrons deux classifications différentes des approches de résolution de problèmes multiobjectifs. Le premier classement adopte
un point de vue décideur , les approches sont classées en fonction de l’usage que l’on désire en faire. Le deuxième classement adopte un point de vue concepteur , les approches sont triées de leur façon de traiter les fonctions objectifs. Ainsi avant de se lancer dans la résolution d’un problème multiobjectif, il faut se poser la question du type d’approche de résolution à utiliser.

IV.2.1. Classification « point de vue décideur » :

On distingue à cet égard trois schémas possibles. Soit le décideur intervient des le début de la définition du problème, en exprimant ses préférences, afin de transformer un problème multiobjectif en un problème simple objectif. Soit le décideur effectue son choix dans l’ensemble des solutions proposées par le solveur multiobjectif :

IV.2.1.1. Les approche a priori :

Le décideur intervient en aval du processus d’optimisation, pour définir la fonction d’agrégation modélisant le compromis que l’on désire faire entre les différents objectifs. Dans ce cas le décideur est supposé connaître a priori le poids de chaque objectif afin de les mélanger dans une fonction unique. Cela revient à résoudre un problème mono-objectif. Cependant dans la plupart des cas, le décideur ne peut pas exprimer clairement sa fonction d’utilité, parce que les différents objectifs sont non commensurables (exprimés dans des unités différentes).

IV.2.1.2. Les approches interactives :

Combinent de manière cyclique et incrémentale les processus de décision et d’optimisation, le décideur intervient de manière à modifier certaines variables ou contraintes afin de diriger le processus d’optimisation. Le décideur modifie ainsi interactivement le compromis entre ses préférences et les résultats. Cette approche permet donc de bien prendre en compte les préférences du décideur, mais nécessite sa présence tout au long du processus de recherche.

IV.2.1.3. Les approches a posteriori :

Cherche à fournir au décideur un ensemble de bonnes solutions bien réparties. Il peut ensuite, au regard de l’ensemble des solutions, sélectionner celle qui lui semble la plus appropriée. Ainsi, il n’est plus nécessaire de modéliser les préférences du décideur (ce qui peut s’avérer être très difficile), mais il faut en contrepartie fournir un ensemble de solutions bien réparties, ce qui peut également être difficile et requérir un temps de calcul important (mais ne nécessite pas la présence du décideur).
Nous nous placerons dans le cadre de cette troisième famille de méthodes où la modélisation des préférences n’est pas requise et où le procédé d’optimisation doit être puissant afin de fournir une très bonne approximation de la frontière Pareto.

IV.2.2. Classification « point de vue concepteur » :

Ce classement adopte un point de vue plus théorique articulé autour des notions d’agrégation et d’optimum Pareto. Les approches utilisées pour la résolution de problèmes multiobjctifs peuvent être classées en deux catégories : les approches non Pareto et les approches Pareto.

IV.2.2.1. Les approche non Pareto :

Ne traitent pas le problème comme un véritable problème multiobjectif. Elles cherchent à ramener le problème initial à un ou plusieurs problèmes mono-objectifs.

IV.2.2.2. Les approche Pareto :

Ne transforment pas les objectifs du problème, ceux-ci sont traités sans aucune distinction pendant la résolution.

V. Approches de résolution Multiobjectif :

La résolution de problèmes multiobjectifs relève de deux disciplines assez différentes, en effet résoudre un problème multiobjectif peut être divisé en deux phases :
– La recherche des solutions de meilleur compromis : C’est la phase d’optimisation Multiobjectif.
– Le choix de la solution à retenir : C’est la tâche du décideur qui, parmi l’ensemble des solutions de compromis, doit extraire celle(s) qu’il utilisera. On parle alors ici de décision multiobjectif et cela fait appel à la théorie de la décision.
Les problèmes multiobjectifs ont la particularité d’être beaucoup plus difficiles à traiter que leur équivalent mono-objectif. La difficulté réside dans l’absence d’une relation d’ordre total entre les solutions. Une solution peut être meilleure qu’une autre sur certains objectifs et moins bonne sur les autres. Donc il n’existe généralement pas une solution unique qui procure simultanément la solution optimale pour l’ensemble des objectifs. Voilà pourquoi le concept de solution optimale devient moins pertinent en optimisation multiobjectif. Dans ce cas la solution optimale ou de bonne qualité n’est plus une solution unique mais, un ensemble de solutions compromis entre les différents objectifs à optimiser. Il est vital pour identifier ces meilleurs compromis de définir une relation d’ordre entre ces éléments. La plus célèbre et la plus utilisée est la relation de dominance au sens Pareto . L’ensemble des meilleurs compromis est appelé le front Pareto, la surface de compromis ou l’ensemble des solutions efficaces.

V.1. Notion de dominance :

Lorsque l’on cherche à obtenir une solution optimale à un problème d’optimisation Multiobjectif donné, on s’attend souvent à trouver une solution et une seule. En effet, on rencontre rarement ce cas de figure. La plupart de temps, on trouve une multitude de solutions, du fait que certaines des objectifs sont contradictoires
Le décideur évalue généralement une solution par rapport a chacun des critères, et se positionne donc naturellement dans l’espace objectif, par contre au cas monoobjectif ou il existe un ordre total parmi les solutions réalisables il n’existe généralement pas de solution qui serait a la fois optimale pour chaque objectif, étant donnée la nature conflictuelle de ces derniers, ainsi une relation de dominance d’ordre partiel est généralement définie. [1]

V.2. Approche Pareto :

Au 19éme Siècle, Vilfredo Pareto, un mathématicien Italien, formule le concept suivant : dans un problème multiobjectif, il existe un équilibre tel que l’on ne peut pas améliorer un objectif sans détériorer au moins un des autres objectifs. Les approches Pareto utilisent directement la notion de dominance dans la sélection des solutions générées. Le principal avantage de ces approches, c’est l’optimisation simultanée d’objectifs contradictoires.

V.2.1. Définition 1:

Une solution y = (y1, .., ym) domine faiblement une solution z = (z1, .., zm)
Ssi 8i 2 1, .., m fi(y) _ fi(z). Si la solution y domine faiblement la solution z nous allons noter y _ z.

V.2.2. Définition2 :

Une solution y = (y1, .., ym) domine une solution z = (z1, .., zm).
Ssi 8i 2 1, .., m fi(y) _ fi(z) et 9j 2 1, .., m tq fj(y) < fj(z)
Si la solution y domine la solution z nous notons alors y _ z Notons que pour toute paire de solutions y et z un et un seul des cas suivants peuvent se présenter :
_ y domine z
_ y est dominé par z
_ y et z sont équivalentes au sens de la dominance.
Les solutions équivalentes au sens de la dominance sont appelées dans ce qui suit, solutions équivalentes au sens de Pareto ou solutions Pareto équivalentes ou, encore, solutions non-dominées.

V.2.3. Optimalité de Pareto :

Soit P un ensemble de solutions candidates d’un problème d’optimisation multiobjectif.
L’ensemble P′P, composé de tous les éléments de P qui ne sont dominés par aucun élément de P est dit sous-ensemble non dominé de l’ensemble P.

V.2.3.1. Optimalité locale au sens de Pareto :

Une solution y est optimale localement au sens de Pareto s’il existe un réel δ > 0 tel qu’il n’y ait pas une solution z dominant y et vérifiant ‖z y‖ ≤ δ.

V.2.3.2. Optimalité globale au sens de Pareto :

Une solution y est optimale globalement au sens de Pareto, ou optimale au sens de Pareto, ou encore Pareto-optimale s’il n’existe aucun point de l’espace faisable D qui la domine. L’ensemble des solutions Pareto optimale est appelé l’ensemble de Pareto ou également l’ensemble des compromis optimaux. L’image de l’ensemble de Pareto dans l’espace des critères est appelé la surface de Pareto (ou le front de Pareto pour le cas bi- objectif) ou encore la surface des compromis optimaux.

V.2.3.2.1. Front de Pareto :

Le front de Pareto est l’ensemble des solutions de compromis. Sur la figure 1, les points A et B sont deux points du front de Pareto : A ne domine pas B, B ne domine pas A, mais tous les deux dominent le point C, Le but de l’optimisation Multiobjectif est de déterminer le front de Pareto pour un problème donné. [10]

Fig.2 : Exemple de front de Pareto

V.2.3.2.2. Point idéal :

Les coordonnées du point idéal (pi) correspondent aux meilleurs valeurs de chaque objectif des points du front Pareto. Les coordonnées de ce point correspondent aussi aux valeurs obtenues en optimisant chaque fonction objectif séparément
[10]

Fig.3 : Représentation des solutions supportées et non supportées, Point idéal et point de nadir.

V.2.3.2.3. Point de nadir :

Les coordonnées du point Nadir (pn) correspondent aux pires valeurs de chaque objectif des points du front Pareto
[11]
Nous indique aussi que le front Pareto peut avoir des propriétés particulières quant à sa forme. La principale caractéristique utilisée pour comparer les formes de ces courbes est la convexité. Nous rappelons donc la définition de la convexité.

V.2.3.2.4. Convexité :

Un ensemble A est convexe, si et seulement si l’équivalence suivante est vérifiée :
[11]
La convexité est le premier indicateur de la difficulté du problème. En effet, certaines méthodes sont dans l’incapacité de résoudre des problèmes non convexes de manière optimale. Mais il existe d’autres indicateurs tout aussi importants, notamment la continuité, la multi-modalité, la nature des variables de décision (entières ou réelles).

VI. Conclusion :

Les approches de résolution multiobjectif consistaient principalement à les transformer en problèmes mono-objectifs. La transformation du problème multiobjectif en un problème mono-objectif nécessite des connaissances a priori sur le problème traité. De plus, ces approches modifient la structure du problème combinatoire qui perd ainsi ses éventuelles propriétés remarquables. L’optimisation du problème mono-objectif peut garantir l’optimalité de la solution trouvée, mais n’en trouve qu’une seule, dans les situations réelles, les décideurs ont généralement besoin de plusieurs alternatives.
La connaissance de plusieurs solutions optimales est utile aussi pour une utilisation future, particulièrement quand la situation change et qu’une nouvelle solution est requise. Le décideur peut ainsi choisir une solution suivant la situation courante. Ces approches sont aussi sensibles au paysage de la frontière Pareto (convexité, discontinuité, etc.). Les méthodes d’agrégation linéaire, par exemple, ne trouvent que les solutions supportées (solution appartenant à l’enveloppe convexe des solutions réalisables).
Notre travail basé sur les approches non Pareto qui ne traitent pas le problème comme un véritable problème Multiobjectif. Elles cherchent à ramener le problème initial à un ou plusieurs problèmes mono-objectifs.
La Résolution du Problème de Voyageurs de Commerce Bi-Objectifs par La Métaheuristique d’Optimisation par Colonie de Fourmis Artificielles
Présenté pour l’obtention du diplôme de MASTER Option Réseaux et Multimédia
Département de Mathématique et d’Informatique