Méthodes et outils pour l’aide a la decision
Optimisation Multiobjectif
Mohamed HACHIMI
Université Ibn Zohr
Faculté des Sciences Juridiques Economiques et Sociales, Agadir
Mohamed Hachimi Optimisation Multiobjectif
Chapitre I
Concepts de base
de l’optimisation mutliobjectif
Mohamed Hachimi Optimisation Multiobjectif
Problème d’optimisation multiobjectif
Le problème de l’optimisation multiobjectif permet de considérer
simultanément plusieurs objectifs f1 , . . . , fk .
Etant donné un ensemble E et un partie D de E, la formulation
d’un tel problème est :
(
min f (x) = f1 (x), . . . , fk (x)
(P)
x ∈ D.
ou
min fk (x)
..
.
(P)
min fk (x)
x ∈ D.
Mohamed Hachimi Optimisation Multiobjectif
Problème d’optimisation multiobjectif
Les objectifs sont habituellement conflictuels. Par exemple :
On veut un système performant et on veut aussi que ce
système consomme peu
On veut acheter une voiture d’occasion qui est peu chère
avec peu de kilomètres
On veut fabriquer un produit peu cher et on veut aussi que
ce produit soit de meilleur qualité
Deux objectifs sont conflictuels (on dit aussi contradictoires
lorsque la diminition d’un objectif entraîne une augmentation
de l’autre objectif.
Mohamed Hachimi Optimisation Multiobjectif
Problème d’optimisation multiobjectif
Kilométrage
Prix
L’acheteur doit donc identifier les « meilleurs » compromis pos-
sibles correspondant à son budget.
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Définition
Définition :
Une solution x̄ est dite supérieure si x̄ ∈ D et pour tout
x ∈ D, on a :
fi (x̄) 6 fi (x), i = 1, . . . , k
C’est une solution qui procure simultanément la solution opti-
male pour l’ensemble des objectifs.
Comme les objectifs sont habituellement conflictuels, il est gé-
néralement impossible de trouver une solution supérieure.
Par conséquent, le concept de solution "optimale" devient moins
pertinent en optimisation multiobjectif.
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
On considère l’exemple suivant :
1
min c x = −x1
− x2
min c2 x = x1 − x2
x1 + 2x2 6 5
(P)
2x1 + x2 6 7
x2 6 2
x1 , x2 > 0
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
On considère l’exemple suivant :
1
min c x = −x1
− x2
min c2 x = x1 − x2
x1 + 2x2 6 5
(P1 )
2x1 + x2 6 7
x2 6 2
x1 , x2 > 0
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
On considère l’exemple suivant :
1
min c x = −x1
− x2
min c2 x = x1 − x2
x1 + 2x2 6 5
(P2 )
2x1 + x2 6 7
x2 6 2
x1 , x2 > 0
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Solution de (P2 )
Mohamed Hachimi Optimisation Multiobjectif
Solution supérieur : Exemple
Solution de (P2 )
Solution de (P1 )
Mohamed Hachimi Optimisation Multiobjectif
Solutions efficaces
Définition :
Le point x̄ ∈ D est dit solution efficace de (P) s’il n’existe
pas de x ∈ D tel que
f (x) ≤ f (x̄)
On note Ee l’ensemble des solutions efficaces
Définition :
x̄ ∈ D est dite solution faiblement efficace de (P) s’il
n’existe pas de x ∈ D tel que
f (x) < f (x̄)
On note Ef l’ensemble des solutions efficaces
Mohamed Hachimi Optimisation Multiobjectif
Solutions efficaces
Définition :
Le point x̄ ∈ D est dit solution efficace de (P) s’il n’existe
pas de x ∈ D tel que
f (x) ≤ f (x̄)
On note Ee l’ensemble des solutions efficaces
Définition :
x̄ ∈ D est dite solution faiblement efficace de (P) s’il
n’existe pas de x ∈ D tel que
f (x) < f (x̄)
On note Ef l’ensemble des solutions efficaces
Mohamed Hachimi Optimisation Multiobjectif
Solutions efficaces localement
Définition :
Le point x̄ ∈ D est dit solution efficace localement de
(P) si et seulement s’il existe δ > 0 tel que x̄ est efficace
pour (P) sur D ∩ B(x̄, δ)
Définition analogue pour l’efficacité faible localement.
Ici, B(x̄, δ) représente une boule de centre x̄ et de rayon δ.
x̄
Mohamed Hachimi Optimisation Multiobjectif
Formulation dans l’espace des critères
La formulation du problème de l’optimisation multiobjectif (P) se
situe dans l’espace des décisions Rn . Il est souvent plus aisé de
travailler dans l’espace des critères Rk où
chaque solution x est représentée par le vecteur z = f (x).
L’image de D dans cet espace est notée Z. On a :
Z = {z ∈ Rk | z = f (x), x ∈ D}
La formulation du problème (P) dans l’espace des critères est
(
min z = (z1 , . . . , zk )
(P)
z ∈ Z.
Mohamed Hachimi Optimisation Multiobjectif
Illustration des espaces des décisions et des critères
x2 z2
f
Z
D
x1 z1
x3
Mohamed Hachimi Optimisation Multiobjectif
Non dominance
La notion d’efficacité se réfère aux points réalisables de l’espace
des décisions tandis que celle de la non dominance se refère aux
vecteurs dans l’espace des critères Rk
Définition :
On dit qu’un vecteur z̄ ∈ Z est non dominé pour (P) si et
seulement s’il n’existe pas de z ∈ Z tel que
z ≤ z̄
Ce point est dit faiblement non dominé si et seulement
s’il n’existe pas de z ∈ Z tel que
z ≤ z̄
Mohamed Hachimi Optimisation Multiobjectif
Non dominance : Illustration
Ensemble des solutions
non dominées
Mohamed Hachimi Optimisation Multiobjectif
Non dominance : Illustration
Ensemble des solutions
faiblement non dominées
Mohamed Hachimi Optimisation Multiobjectif
Non dominance : Remarques
Toute solution efficace est faiblement efficace. D’où :
Ee ⊆ Ef
la réciproque n’est pas vraie en général ;
Par définition, on a : x efficace ⇐⇒ f (x) non dominé ;
L’ensemble des vecteurs non dominés et faiblement non domi-
nés est toujours sur la frontière de Z. On appelle cet ensemble
le front Pareto ou la surface de compromis.
Mohamed Hachimi Optimisation Multiobjectif
Point idéal et point nadir : Définitions
On observe deux points caractéristiques associés au front Pareto
Définition :
Les coordonnées du point idéal sont obtenues en optimi-
sant chaque fonction objectif séparément.
Définition :
Les coordonnées du point nadir correspondent aux pires
valeurs obtenus par chaque fonction objectif lorsqu’on res-
treint l’espace des solutions au front Pareto.
Mohamed Hachimi Optimisation Multiobjectif
Point idéal et point nadir : Illustration
z2
Z Point nadir
Point idéal
z1
Mohamed Hachimi Optimisation Multiobjectif
Non dominance local
Définition :
On dit qu’un vecteur z̄ ∈ Z est non dominé localement
pour (P) s’il existe δ > 0 tel que z̄ est non dominé dans
Z ∩ B(z̄, δ).
Définition analogue pour la non dominance faible loca-
lement.
Mohamed Hachimi Optimisation Multiobjectif
Non dominance local
z2
z1
Mohamed Hachimi Optimisation Multiobjectif
Non dominance local
z2
z1
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact
Définition :
Un cône négatif est défini dans Rk par :
Γ = {z ∈ Rk | z ≦ 0}
Son intérieur dans Rk est donné par :
◦
Γ = {z ∈ Rk | z < 0}
Théorème :
Un vecteur z̄ est non dominé pour le problème (P) si
Γ + z̄ ∩ Z = {z̄}
Un vecteur z̄ ∈ Z est faiblement non dominé pour (P) si
◦
Γ +z̄ ∩ Z = ∅
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
C − + x2
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
C − + x2
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
C − + x3
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
C − + x3
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
C − + x4
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
C − + x4 x5
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
x5
C − + x5
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
x5
x6
C − + x5
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
x1
x2 Z
x3
x4
x5
x6
C − + x6 z1
C−
Mohamed Hachimi Optimisation Multiobjectif
Théorème de contact : Illustration
z2
z1
C−
Mohamed Hachimi Optimisation Multiobjectif
La cône-dominance
A venir
Mohamed Hachimi Optimisation Multiobjectif
Le décideur
C’est « le » personnage central pour la théorie multiobjectif
puisque c’est « lui » qui prend la décision finale
Une personne unique
Un groupe de personnes
Parfois, n’est pas clairement identifié
Face à une situation de décision, le décideur a la responsa-
bilité d’évaluer les différentes alternatives possibles afin de
proposer ou de mettre en œuvre une solution.
Mohamed Hachimi Optimisation Multiobjectif
L’analyste ou L’homme d’étude
C’est « le scientifique » qui aide le décideur à rester cohérent
avec ses choix. Il a la responsabilité de :
la définition du modèle de décision
la conduite du processus de décision
la présentation des résultats au décideur
L’interaction entre l’analyste et le décideur est une caractéris-
tique intrinsèque au processus de décision.
Mohamed Hachimi Optimisation Multiobjectif
L’analyste ou L’homme d’étude
Le niveau de l’interaction entre l’analyste et le décideur dé-
pend généralement
du niveau de connaissance du décideur
de sa volonté à participer au processus
de la règle de décision à appliquer
de la nature du problème
Cette interaction devient plus élaborée et plus complexe dans
le cas de l’utilisation d’une méthode interactive qui implique
une "extraction" permanente de l’information détenu par le
décideur.
Mohamed Hachimi Optimisation Multiobjectif
