Optimisation multi-critère :

approche par métaheuristiques

Clarisse DHAENENS, El-Ghazali TALBI

Equipe OPAC (Optimisation PArallèle Coopérative)

Laboratoire d’Informatique Fondamentale de Lille

Université de Lille 1, France

http://www.lifl.fr/~dhaenens
Optimisation multi-critère
§ 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ère linéaire ou non-linéaire en

variables continues [Steuer 86, White 90].
Optimisation combinatoire multi-critère.
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
 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ère [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 wi j : poids de l’élément j
j =1
c : utilité de l’élément j / critère i
∈ {0 ,1}, ∀ j = 1,.., m
j

x j
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, ...

Design de réseaux de radiocommunications mobiles

[P. Reininger et A. Caminada, CNET]
Objectifs et/ou contraintes :
Ø Min (Nombre de sites candidats utilisés)
Ø Min (Interférences)
Ø Min (Overhead)
Ø Max (Trafic)
Ø Couverture, Handover, Connectivité, ...
 Optimisation multi-objectif

(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 objectif 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 (minimisation)
y domine z ssi ∀ i ∈ [ 1 .. n ], f ( y ) ≤ f ( z ) et ∃k ∈ [ 1.. n ] / f ( y ) < f ( z )
i i k k

• Pareto optimalité
Une solution x*∈C est Pareto optimale ssi il n’existe pas de solution
x∈ C tel que x domine x*

f 2 Solution Pareto optimale

(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
de référence z* N : C → V (C )
y* / yi = 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
y * 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.
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

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
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
 Algorithmes d’optimisation
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
 Méthodes heuristiques

Problème de minimisation

Ø Méthode de descente
• Vers un meilleur voisin

Ø Recherche Tabou
• Vers un meilleur voisin mais,
• Possibilité de dégrader solution
• Impossibilité de retourner vers
solutions récemment visitées
(évite de cycler)
• Paramètres : fonction objectif,
voisinage,
description mouvement Tabou,
longueur liste Tabou
Méthodes heuristiques

Ø Recuit simulé
• Basé sur analogie avec recuit
des matériaux
• Vers un meilleur voisin mais,
• Possibilité de dégrader solution
• En fonction d’une température :
Au plus la recherche avance, au moins la dégradation est
acceptée.
• Paramètres : fonction objectif,
voisinage,
Temp initiale,
fonction de diminution Temp,
longueur palier de Temp,…
Méthodes heuristiques

Ø Algorithmes évolutionnaires
• A base de population
• Héritage de patrimoine génétique
• Les mieux adaptés survivent
• Amélioration globale
• Paramètres : fonction objectif,
taille de la population,
opérateurs,
sélection des parents,
remplacement, …
Algorithme génétique - Schéma

Sélection Reproduction

Remplacement

Croisements

Elitisme Maj
archives

Mutation
Mécanisme
Pareto
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution multicrière

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
Classification des méthodes

§ Transformation de PMO en uni-objectif

Ø Méthode d’agrégation
Ø Méthode ε-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

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

s.c. x ∈C λ i
≥ 0, i = 1,.., n ∑λ
i =1
i
=1

Complexité = problème combinatoire sous-jacent.

Ex : Polynomial = flot, cheminement, … NP-complet = routage, affectation, ...
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 + F(x)
Ø 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]

Ø Algorithme glouton + Recuit simulé [Tuyttens 98]
Ø 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 ε -contrainte

( PMO k (ε ))
{ f
min
s.c.

j
f k

x ∈C
(x)

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

f2
§ Variation de ε Solution optimale

§ F(C) = espace objectif PMO

§ F’(C) = espace objectif du F(C)
problème transformé
ε

{
2

min f 1 F’(C)

f 2 ≤ε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é (PMO ) q

s.c. f ( x ) ≤ f ′ , r = 1,.., q − 1
Ø Seuil (f’) = Optimum (f*) r r

+ Détérioration acceptée x ∈C

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

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

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

F(C)
*
f 2

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 ( x )− z i ))−max (λ ( f ( y )− z i )) 

Ø Fonction d’acceptation p xy (T ) = min 1, e 
i i i i i i
T

Ø Itération =λ i = λ i ± [ −0.05,+0.05]  

§ 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 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]

Ø Plusieurs classes. Une classe = Un objectif
Ø 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 : Maintient
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+1
§ WAR [Bentley 97], …
Ø 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 n
= Probabilité de sélection
S ( N + 1 − R n ) + Rn − 2 S = Pression de sélection
pn = R = 1 + r + 2∑ r
n −1

N ( N − 1) i i
i =1
i

§ Tournoi [Horn et al. 97]

r = Nombre d’individus de rang i
i

f 2

A
Ensemble de comparaison

f 1

§ Autres : Roulette biaisée, etc ;

 Maintient 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 .

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

 0 Sinon

σ sh dist

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

§ Métrique utilisée (dist) ?
§ Taille des niches (σ sh
) ?
Classification

Méthodes d'optimisation multi-objectif

Préférences
A priori Interactive A posteriori

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 Titre
Approches
de transformation non-Pareto Pareto
du
Programmation Sélection Sélection
diag
Agrégation ε-contrainte
par but parallèle lexicographique ram
me
Techniques avancées
§ Modèles parallèles
(Algorithmes génétiques) Utilisateur
Contraintes, poids, ...
Ø Accélération de la recherche
AG AG AG Recuit, Tabou

f1 f2 fn Meilleures solutions

Ensemble PO*

Ø Amélioration des résultats

GA GA
(coopération)
• Modèle insulaire GA
GA
• Modèle cellulaire

GA GA

GA GA
§ Restriction de voisinage
Techniques avancées
§ Hybridation
Ø Algorithme Génétique + Recherche Locale

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

courante
N − A S ( N + 1 − Rn ) + R n − 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]

Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes
Ø Paysage

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances
§ Exemple d’application
§ Conclusions & axes de recherche future
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 U B ) = A
ND ( A U B ) = A + B − ND ( A U B ) ≠ φ
+
+ +
+ +
+ +
A faiblement meilleur que B A fortement meilleur que B
f1 f1
f2 f2
+ ND ( A U B ) = B
+ +
A I ND( A U B) = φ
+ + +
+
+ +
B totalement meilleur que A A et B incomparables
f1 f1
Evaluation des performances

Ø Contribution: Apport de chaque heuristique dans la

construction de PO*.
C 2 + W 1 + N1
Cont( PO1 / PO 2) =
C + W 1 + N1 + W 2 + N 2

C=4
W1=4 - N1=1
W2=0 - N2=1

Cont(O,X)=0,7
Cont(X,O)=0,3
 Evaluation des performances

§ S metric [Zitzler99]: Évaluation de l’aire de

dominance des fronts.
Zref
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
 Flowshop de permutation bicritère

• N jobs à ordonnancer sur M machines.

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

M1

M2
M3
Travaux précédents

§ Première étude: comparaison de différentes

techniques de sélection et diversification
[Mabed00]
Ø Approche pareto.
Ø Sélection élitiste avec ranking NSGA.
Ø Diversification par sharing combiné (espace objectif
et décisionnel).
Ø Hybridé avec une recherche locale.

§ Résultats
Ø Bons résultats sur petit problèmes
Ø Manque de robustesse
Ø Paramétrage
Travaux précédents
§ AG hybride adaptatif [Basseur02]
Ø Diversification adaptative.
Ø Mutation adaptative.
Ø Hybridation par une recherche mimétique sur le
front.

§ Résultats:
Ø Bons résultats dans l’ensemble.
Ø Mutation adaptative à améliorer.
Ø Bonne robustesse.
Ø Exploration insuffisante.
Mutation adaptative

§ AG hybride adaptatif :

Ø A chaque mutation Mi, on associe une probabilité de

sélection P(Mi) ajustable durant l’algorithme [Wang 00]

Ø Deux phases principales pour la mise en œuvre:

• Choix de l’opérateur à appliquer (en fonction des P(Mi))
• Mise à jour des probabilités de sélection des différents
opérateurs (en fonction des progrès réalisés)
L’algorithme

Create initial Elitist selection into

population the population

Start Set new PMi

Crossover

Mutation n
Computation of PO* … Mutation selection
and the population
Mutation 1

End of GA
 Ajustement des P(Mi)
Ajustement des P(Mi) adapté aux problèmes multi-critères:

0 si I domine IMi
π ( M iN )= 1 si I est dominé par IMi 1/2 0
1/2 sinon

Progress(Mi)= ∑π(M )
iN 1 1/2
MiN

×(1−n×δ )+δ
Progress(Mi)
P(Mi)=
∑ j=1Progress(Mj)
n
Résultats – exemple 20jx10m
Résultats – exemple 50jx20m
Plan de la présentation
§ Optimisation multi-critère (multi-objectif) :
Ø Définitions
Ø Problèmes

§ Algorithmes d’optimisation
Ø Classification
Ø Présentation des métaheuristiques

§ Classification des méthodes de résolution

§ Evaluation des performances et paysages
§ Exemple d’application
§ Conclusions & axes de recherche future
Conclusions

§ Axe de recherche primordial pour les scientifiques et les

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

§ Métaheuristiques à base de populations.

§ Un algorithme génétique générique pour les PMO

(C++).

§ Application académique : flow-shop bi-objectif

(comparaison d’algorithmes).

§ Application réelle : Positionnement de sites (modèle et

jeu de test, codage, opérateurs, paysage du problème).
Perspectives

§ Hybridation AG et recherche locale

Ø Algorithmes complémentaires (Exploration / Exploitation)

§ Modèles parallèles

§ Elaboration de benchmarks (jeux de test)

Ø Différents paysages

§ Evaluation de performances et comparaison

Ø Métriques (Extensibilité, …)

§ Approche interactive (aide à la décision)

Ø Apprentissage basé sur les paysages