See discussions, stats, and author profiles for this publication at: [Link]

net/publication/2440337

Métaheuristiques pour l'optimisation combinatoire multi-objectif:

Etat de l'art

Article · December 2000

Source: CiteSeer

CITATIONS READS

42 4,189

1 author:

El-Ghazali Talbi
University of Lille Nord de France
561 PUBLICATIONS 15,802 CITATIONS

SEE PROFILE

All content following this page was uploaded by El-Ghazali Talbi on 08 February 2016.

The user has requested enhancement of the downloaded file.

 Métaheuristiques pour
l ’Optimisation Combinatoire
Multi-objectifs : Etat de l’art

El-Ghazali TALBI
Equipe OPAC (Optimisation PArallèle Coopérative)
Laboratoire d’Informatique Fondamentale de Lille
Université de Lille 1, France
[Link]
Optimisation multi-objectifs
ƒ Nombreux secteurs de l’industrie concernés
(Télécommunications, Transport, Environnement,
Mécanique, Aéronautique, ...).

ƒ Racines dans le 19ième siècle dans les travaux en

économie de Edgeworth et Pareto (Sciences de l ’ingénieur,
Management).

ƒ Optimisation multi-critères linéaire ou non-linéaire en

variables continues [Steuer 86, White 90].
Optimisation combinatoire multi-critères.
Plan de la présentation

ƒ Optimisation multi-objectifs : Définitions, Problèmes

ƒ Classification des méthodes de résolution (métaheuristiques
associées)

ƒ Evaluation des performances et paysages

ƒ Conclusions
ƒ Travaux en cours : Algorithmes parallèles et hybrides, ...
 Optimisation multi-objectifs

(PMO)
{ min F ( x ) =

s.c. x ∈C

Variables de décision
(f 1
( x ), f 2

x = ( x1 , x 2 ,..., x k )
( x ),..., f n
( x) ) n≥2

Espace objectifs ou espace des critères : Y=F(C)

f 1

x
1 Espace de décision F

C f 2

f 3

x 2
 Définitions
• Dominance
y domine z ssi ∀ i ∈ [ 1 .. n ] y i ≤ z i et ∃i ∈ [ 1 .. n ] / y i < z i
• Pareto optimalité
Une solution x *∈ C est Pareto optimale ssi il n ’existe pas une solution
x∈C tel que F ( x ) domine F (x*)

f 2
Solution Pareto optimale
(admissible, efficace, non
inférieure, non dominée)
z
Solution réalisable dominée
y

f 1

PO : ensemble exact des solutions Pareto optimales

Définitions
ƒ Solutions supportées et ƒ Pareto localement optimale
non supportées
Voisinage N : opérateur de recherche locale
ƒ Vecteur idéal y* et vecteur
N : C → P (C )
de référence z*
*
y * / y i = min (f i
( x) ) 1, 8, 9 : Pareto optimale
4, 10 : Pareto localement optimale
voisinage
Solution Pareto supportée
f 2 Solution Pareto non supportée f 2
2

Enveloppe convexe 5
4

10 3

9
6
8 7
f 1 1 f 1
Difficultés des PMO

ƒ Définition de l ’optimalité : relation d ’ordre partiel, choix

final dépend du décideur, environnement dynamique, …

ƒ Nombre de solutions Pareto croît en fonction de la taille

des problèmes et le nombre de critères utilisés.

ƒ Pour les PMO non convexes, les solutions Pareto sont

localisées dans les frontières et à l ’intérieur de
l ’enveloppe convexe de C.
Coopération solveur-décideur
• A priori : Préférences Recherche (fonction d ’utilité)

Connaissances a priori du problème.

• A posteriori : Recherche Préférences

Cardinalité de l ’ensemble PO réduite.

• Interactive : Recherche Préférences

Aspect aide à la décision n ’est pas adressé.

Connaissances Décideur Préférences Solveur Résultats

a priori

Connaissances acquises
 Algorithmes de recherche
Algorithmes de résolution

Heuristiques
Algorithmes exacts
Heuristiques M étaheuristiques
spécifiques
Branch Programmation A*
and bound dynamique
Recuit Algorithmes Recherche
[Ulungu 95] [Carraway 90] [Stewart 91] simulé génétiques tabou

Algorithmes exacts : problèmes bi-critères de petites tailles

Métaheuristiques :
ƒ solution unique : recuit simulé, recherche tabou, ...
ƒ population : algorithmes génétiques, recherche dispersée,
colonies de fourmis, ...

PO* : Approximation de PO
 PMO académiques

ƒ Ordonnancement [Sayin et al. 99]

ƒ Cheminement [Warburton 87], Arbre recouvrant [Zhou et Gen 99]
ƒ Voyageur de commerce [Serafini 92], Affectation [Teghem 95]
ƒ Routage de véhicules [Park et Koelling 89], ...

{
Sac à dos multi-critères [Teghem et al. 97]
(f ) ∑c x
{
m
(x) =
i
Max i
j =1
j j
x j=
1 si l ’élément j est dans le sac

(i = 1 ,..., n ), x ∈ C
0 sinon

m
C=x ∑w x j j
<W w j : poids de l ’élément j
i
j =1
c : utilité de l ’élément j / critère i
∈ {0 ,1}, ∀ j = 1,.., m
j

x j
 Flow-shop multi-objectifs

• N jobs à ordonnancer sur M machines.

• Flow Shop de permutation.
• Critères optimisés:
• Cmax :Date de fin d’ordonnancement.
• T :Somme des retards.
• Problème d ’ordonnancement de type F/perm, di/(Cmax,T)
[Graham 79].

M1

M2
M3
 VRP multi-objectifs

I = (G, D, q, Q)
Depôt
Vk’ Vk’ G : graphe orienté (S, E)
C1 D : coût des arcs
q : demande des clients
C3
C2
Q : capacité des véhicules

C7
C4 Trouver X = (xijk) | xijk = 1 si le
véhicule k va du client i au client j,
C6 C5 0 sinon
N M

Ci : Client i
C8
Minimiser ∑d ∑ x
i, j =1
ij
k =1
ijk

Contraintes
: vehicule k
 VRP multi-objectifs
ƒ Un problème naturellement
multi-critère
ƒ Modélisation bi-critère du
problème :
ƒ Premier critère :
ƒ Minimiser
ƒ Deuxième critère :
ƒ Equilibrer la longueur des
sous-routes
N M
∑d ∑ x
i, j =1
ij
k =1
ijk

ƒ Minimiser
N N

max ∑ d x
k i , j =1
ij ijk
− min ∑ d x
k' i , j =1
ij ijk '
PMO industriels
ƒ Télécommunications : Design d ’antennes [Sandlin et al. 97], affectation
de fréquences [Dahl et al. 95], ...
ƒ Aéronautique : ailes d ’avions [Obayashi 98], moteurs [Fujita 98], ...
ƒ Environnement : gestion de la qualité de l ’air [Loughlin 98], distribution
de l ’eau, …
ƒ Transport : tracé autoroutier, gestion de containers [Tamaki 96], …
ƒ Finances, Productique, Robotique, Mécanique...

Design de réseaux de radiocommunications mobiles

[Thèse H. Meunier, OPAC/FT R&D]
Objectifs et/ou contraintes :
ƒ Min (Nombre de sites candidats utilisés)
ƒ Min (Interférence)
ƒ Min (Overhead)
ƒ Max (Trafic)
ƒ Couverture, Handover, Connectivité, ...
Classification des méthodes

ƒ Transformation de PMO en uni-objectif

ƒ Méthode d’agrégation
ƒ Méthode E-contrainte
ƒ Programmation par but

ƒ Approches non Pareto

ƒ Traitent séparément les différents objectifs

ƒ Approches Pareto
Utilisent la notion de dominance
 Méthodes d’agrégation

(PMOλ )
{ min F ( x ) = ∑i =1 λ i

s.c. x ∈C
n

λ
Complexité = problème combinatoire sous-jacent.
Ex : Polynomial = flot, cheminement, …
i
f i
( x)

≥ 0, i = 1,.., n
Agrégation linéaire

NP-complet = routage, affectation, ...

∑λ
n

i =1
i
=1

f 2 f 2
Hyperplan

Domaine réalisable
y

Optimiser F z
Frontière Pareto convexe Frontière Pareto concave
f 1 f 1
Métaheuristiques
ƒ Algorithmes génétiques [Hajela et Lin 92]
ƒ Codage d’un individu = Solution + λ
ƒ But = Générer une variété de solutions Pareto

ƒ Recuit simulé [Serafini 92]

 ∑ λ ( f ( x )− f
n
(y) )
p xy (T ) = min 1,e 
i =1 i i i

ƒ Fonction d ’acceptation T

 
ƒ Recherche tabou [Dahl et al. 95]
ƒ Poids = priorité de l ’objectif

ƒ Métaheuristiques hybrides [Talbi 98]

X Algorithme glouton + Recuit simulé [Tuyttens 98]
X Algorithme génétique(Recherche locale) [Ishibuchi et Murata 98]
• Sélection avec des poids différents
• Recherche locale sur l ’individu produit (même poids)
 Méthode E-contrainte

( PMOk (ε ))
{ f
min

s.c.
j
( x
f

) ≤
k

x ∈C
ε j
( x)

, j = 1,..n , j ≠ k ε = (ε 1 ,...,ε k +1 ,...,ε n )

f2
Solution optimale
ƒ Variation de ε
F ’(C)
ƒ F(C) = espace objectifs PMO
ƒ F ’(C) = espace objectifs du ε 2

problème transformé F(C)

{ max f
f ≥ε
2
1

2
f1
Métaheuristiques
ƒ Algorithmes génétiques
(i − 1).(ε − ε )
ƒ Individu = ε [Loughlin 98] ε i = ε min + max

(k − 1)
min

{
k : taille de la population
ƒ Recherche tabou [Hertz et al. 94]
ƒ Suite de sous-problèmes f* q
f (x )
= min q

ƒ Ordre de priorité (PMOq ) s.c. f ( x ) ≤ f ′ , r = 1,.., q − 1

r r
ƒ Seuil (f ’) = Optimum (f*)
ƒ + Déterioration acceptée x ∈C

ƒ Métaheuristiques hybrides [Quagliarella et al. 97]

ƒ Algorithme génétique + Recherche locale
 Programmation par but

{
1
 n p  p
min  ∑ λ f j ( x ) − z j 
( PMOk (ε ))  j =1
j

s.c. x ∈ C Z : Vecteur idéal ou de référence

Norme utilisée : Métrique de Tchebycheff L p métrique

f2 p=2 Métrique euclidienne p= ∞ Min-Max

F(C)
*
f 2

λ
z

f1
*
f 1
Métaheuristiques
ƒ Algorithmes génétiques
ƒ Fonction min-max, AG parallèle avec différents poids [Coello 98]
ƒ Règles floues dans l ’évaluation de F [Reardon 98]

ƒ Recuit simulé [Serafini 92]  max (λ ( f

i i
( x )− z i ))− max (λ ( f
i i
( y )− z i )) 
ƒ Fonction d ’acceptation p xy (T ) = min 1, e 
i i
T

 
λ λ
ƒ Itération = = ± [ −0.05,+0.05]
i i

ƒ Recherche tabou [Gandibleux 96]

ƒ Meilleur voisin = Meilleur compromis non tabou
ƒ Compromis = Norme L p de Tchebycheff par rapport au vecteur idéal
ƒ Mémorisation des M meilleures solutions
Analyse critique

ƒ Espace de recherche <> Problème initial. Le problème

perd ses éventuelles propriétés.

ƒ Une exécution produit une seule solution.

ƒ Connaissances a priori (détermination des paramètres).

ƒ Sensibles au paysage de la frontière Pareto (convexité,

discontinuité, …), et à différents paramètres (poids,
contraintes, buts, …).

ƒ Objectifs bruités ou données incertaines.

ƒ Coût associé aux algorithmes (exécution multiple).

Approches évolutionnaires non Pareto
Traitent séparément les différents objectifs non commensurables.
ƒ Sélection parallèle (VEGA) [Schaffer 85]
Génération t Génération t+1

sous-population 1
Objectif 1

Population Population

Objectif n sous-population n Crossover

ƒ Sélection Mutation
Reproduction
ƒ Sélection lexicographique (ordre de priorité)
ƒ Algorithmes génétiques [Fourman 85]
ƒ Stratégies évolutionistes [Kursawe 91]

ƒ Reproduction multi-sexuelle [Lis et Eiben 96]

X Plusieurs classes. Une classe = Un objectif
X Reproduction (crossover) sur plusieurs individus

Tendance à ignorer les solutions compromis

Approches Pareto
• Utilisent la notion de dominance dans la sélection des solutions.
• Capables de générer des solutions Pareto dans les portions concaves.

Objectifs
Convergence : Méthodes de Diversification : Maintenance
ranking (ordre entre individus) de la diversité
f 2 f 2

Domaine réalisable Domaine réalisable

Frontière Pareto Solution trouvée

f 1 f 1
Méthodes de ranking
ƒ NSGA [Srinivas et Deb 95]
ƒ Rang Individus non dominés = 1. Pop=Pop-Individus non dominés
ƒ NDS [Fonseca et Fleming 95]
ƒ Rang Individu = nombre de solutions le dominant
ƒ WAR [Bentley 97], …
X Rang Individu = moyenne des rangs / objectifs
f 2 f 2

A(1) A(1)
H(3) H(6)
F(2) F(3)
B(1) B(1)
C(1) C(1)
G(2) G(2)
D(1) D(1)
E(1) E(1)

f 1 f 1

NSGA NDS
 Sélection
ƒ Rang [Baker 85]
p = Probabilité de sélection
n

S ( N + 1 − Rn ) + Rn − 2 S = Pression de sélection
pn = R
n −1
= 1 + ri + 2 ∑ ri
N ( N − 1) i
i =1
r = Nombre d ’individus de rang i
ƒ Tournoi
i
[Horn et al. 97]
f 2

ƒ
A
Ensemble de comparaison

f 1

ƒ Autres : Roulette biaisée, etc ;

 Maintenance de la diversité
Optimisation multi-modale : Localiser tous les optima d ’un problème
F(x)
Dérive génétique

ƒ Exécutions itératives indépendantes

ƒ Niching séquentiel
ƒ Exécution itérative avec pénalisation des optima déjà trouvés

ƒ Niching parallèle (sharing, crowding)

ƒ Une seule exécution
 Fonction de partage (sharing)
' f ( x)
Dégrade le coût d ’un individu / nombre d ’individus similaires f ( x) =
m( x )
Compteur de niche m( x ) = ∑ sh(dist( x, y ) )
y∈Pop .


sh
 dist ( x , y )  α
1−  dist ( x, y ) < σ sh

Si 1
σ
sh(dist( x, y )) = 
 
 sh 

 0 Sinon

σ sh dist

ƒ Espace objectif et/ou Espace de décision (x,y),

combiné ?
ƒ Métrique utilisée (dist) ?
ƒ Taille des niches (σ sh
) ?
Classification
Méthodes d'optimisation multi-objectifs
Préférences
A priori Interactive A postériori

Algorithmes de résolution

Heuristiques
Algorithmes exacts

Heuristiques M étaheuristiques
spécifiques
Branch Programmation A*
and bound dynamique
Recuit Algorithmes Recherche
simulé génétiques tabou

Approches
de résolution
Approche à base Approches Approches
de transformation non-Pareto Preto

Agrégation E-contrainte Programmation Sélection Sélection

par but parallèle lexicographique
 Techniques avancées
ƒ Modèles parallèles
(Algorithmes génétiques) Utilisateur
ƒ Accélération de la recherche Contraintes, poids, ...

AG AG AG Recuit, Tabou

f1 f1 f1 Meilleures solutions

Ensemble PO*
ƒ Amélioration des résultats
(coopération)
ƒ Modèle insulaire GA GA
ƒ Modèle cellulaire
GA GA

GA GA
ƒ Opérateurs adaptatifs
GA GA
(mutation, crossover, …)
 Modèle parallèle hybride

ƒ 3 niveaux « Populations » de réseaux

hiérarchiques :
1. Modèle insulaire ...
coopératif
(È qualité)
2. Évaluation en
parallèle des réseaux Réseaux
(Ô temps)
3. Évaluation d’un
réseau en parallèle
(Ô temps) Réseau partiels
(partitionnement géographique)
Vers le « GRID » optimization

ƒ Réseaux hétérogènes de stations de

travail : 25 Intel/Linux,
6 Sparc/solaris, 1 Mips/Irix

ƒ CLUMPS - Grappe de SMP (mémoire

partagée): IBM SP3 (Lille) – 64
processeurs : 4 nœuds de 16
processeurs

ƒ Grappe de grappes de PCs : Icluster

(Grenoble) – 216 PC : 5 clusters
Techniques avancées
ƒ Hybridation
ƒ Algorithme Génétique + Recherche Locale (Tabou,
Archive Pareto) [Talbi et al. 2002]

ƒ Elitisme (archive PO*) [Zitzler et Thiele 98]

Population PO*
courante
N − A S ( N + 1 − Rn ) + Rn − 2
pn =
N N ( N − 1) Sélection
A : Nombre d ’individus sélectionnés à partir de PO*

ƒ Clustering de l’ensemble PO* [Roseman et Gero 85]

Evaluation des performances
• Ensemble PO connu [Teghem et al.]

- Efficacité Absolue
PO * ∩ PO
Proportion des solutions Pareto dans PO* AE =
PO

- Distance (PO*, PO)

Plus mauvaise distance WD = max(d ( PO*, y)), y ∈ PO

Distance moyenne MD =
∑ y∈PO
d ( PO *, y )
PO
d ( PO *, y ) = min (d ( x , y ) ), x ∈ PO *
- Uniformité n

WD d ( x, y) = ∑λi f ( x) − f j ( y)
DIV = i =1
i

MD
 Evaluation des performances
• Ensemble PO inconnu
- Efficacité relative (A, B) : Nombre de solutions de A dominées par des
solutions de B

f2 A f2
+ A≠ B + B + ND ( A < B ) = A
+
+ ND ( A < B ) = A B − ND( A < B ) ≠ Φ
+ +
+ +
+ +
A faiblement meilleur que B A fortement meilleur que B
f1 f1
f2 f2
+ ND ( A < B ) = B
A ,ND( A < B ) = Φ + +
+ + +
+
+ +
B totalement meilleur que A A et B incomparables
f1 f1
Evaluation des performances
• Ensemble PO inconnu

Contribution : Évaluation de la qualité des solutions

d’un ensemble par rapport à un autre
C 2+ W1 + N1
Cont(PO1/ PO2)=
C + W1 + N1 + W2 + N2
PO1 C W1 L1 N1

PO2 C W2 L2 N2

C=4
W1=4 - N1=1
W2=0 - N2=1
Ex: Si PO1=PO2 Alors CONT(PO1/PO2) = 0.5 •Cont(O,X)=0,7
Si PO1>PO2 Alors CONT(PO1/PO2) = 1 •Cont(X,O)=0,3
 Evaluation des performances
• Ensemble PO inconnu
Entropie : Odéfinit une niche autour de chaque solution de
ND(PO1 U PO2)=PO*
„ E(PO1,PO2) : diversité des solutions de PO1 par rapport aux niches de PO*
PO*
E(PO 1,PO 2)= −1 ∑ ( 1 ni ln ni )
ln(γ) i=1 Ni PO 1 PO 1

PO1
PO2
Niches
Paysages
Caractérisation du paysage de la frontière Pareto

ƒ Convexité de PO (supportées et non supportées)

ƒ Multi-modalité (Rugosité, Locale Pareto)

ƒ Déception (Attracteurs déceptifs)

ƒ Optimum isolé (Espace plat)

ƒ Discontinuité

ƒ Distribution non uniforme

 Paysages : Analyse de la convexité
ƒ Agrégation : solutions supportées uniquement
ƒ Convexité : Proportion des solutions Pareto situées sur
l’enveloppe convexe
Complexité :
f2 O([Link](n))

Solutions non-dominées
Solutions non-supportées

Enveloppe convexe
Solutions dominées

f1

Outil d’analyse et d’évaluation de performances GUIMOO :

[Link]/OPAC
 GUIMOO (A Graphical User Interface
for Multi-Objective Optimization)

ƒ Caractérisation de ƒ Analyse des

frontières Pareto performances
→ Affichage 2/3D → Métriques
(mise à jour continue) ƒ Contribution
ƒ Structure ƒ Entropie (par niches)
ƒ Continue/Discontinue
ƒ Distance
ƒ Concave/Convexe
générationnelle
ƒ Répartition des
ƒ Spacing
solutions dans l’espace
des critères

[Link]
Conclusions

ƒ Axe de recherche primordial pour les scientifiques et les

ingénieurs (problèmes réels, questions ouvertes).

ƒ Métaheuristiques à base de populations adaptés.

ƒ EO Æ PARADISEO : Bibliothèque de métaheuristiques

parallèles et distribués pour les PMO (Collaboration
OPAC-LIFL/FRACTALES-INRIA).

ƒ Application académique : VRP, Ordonnancement flow-

shop (comparaison d’algorithmes).

ƒ Application réelle : Design de réseaux (modèle et jeu de

test, codage, opérateurs, paysage du problème).
 Travaux actuels
View publication stats

ƒ Hybridation adaptative AG et recherche locale

ƒ Algorithmes complémentaires (Exploration / Exploitation)

ƒ Elaboration de benchmarks (jeux de test)

ƒ VRP et flow-shop ( [Link]/OPAC )

ƒ Evaluation de performances et comparaison

ƒ Métriques (Extensibilité, …)

ƒ Approche interactive (aide à la décision)

ƒ Apprentissage basé sur les paysages
ƒ Modélisation des choix, des préférences
ƒ Conception et implémentation sur Grilles (réseau large échelle) : Projet
ACI GRID DOC-G (Défis en Optimisation Combinatoire sur Grilles, LIFL Lille
- PRISM Versailles – ID Grenoble)