RECHERCHE TABOU (TABU SEARCH), 1989 (Glover)
Principe (4 me randonneur)
" m moire court terme : on m morise les derni res
configurations visit es (liste tabou)
(cid:1) viter les cycles
" choisir un des meilleurs voisins qui n'appartient pas la
liste tabou, m me s'il d grade f
" pas de tirages al atoires
155
I. Alaya
ENSI -ISID
RECHERCHE TABOU
Param tres
" liste tabou T : une file contenant les mouvements (ou
solutions) temporairement interdits
" nombre maximal d'it rations
" taille de la liste tabou : statique ou dynamique
" Crit res daspiration a(i,m) : d terminent
quand il est avantageux dentreprendre m, malgr son
statut tabou.
156
I. Alaya
ENSI -ISID
RECHERCHE TABOU
Algorithme
" Etape 1 (initialisation)
a) choisir une solution initiale s S
s, T (liste_tabou) 9
b) s* 9
" Etape 2 (choix et terminaison)
a) choisir s' V(s) tq
s" V(s), f(s')
f(s") (s' est le plus performant des voisins de s,
mais peut tre moins performant que s) et s' T ou un des
crit res a(i, s) est applicable
b) s 9
c) terminer si la condition d'arr t est r alis e (nb. Max d'it r)
s' (m me si f(s') > f(s))
" Etape 3 (mise jour)
a) mettre jour T et les crit res daspiration
b) s* 9
c) aller l' tape 2
s si f(s) < f(s*)
157
I. Alaya
ENSI -ISID
"
RECHERCHE TABOU
Intensification/Diversification
" Taille de la liste tabou permet la diversification et
lintensification
" Il est possible de violer une interdiction (violer T)
lorsquun mouvement interdit permet dobtenir la meilleure
solution enregistr e jusqu maintenant.
" Une liste T avec trop d l ments peut devenir tr s
restrictive.
" Une liste T contenant trop peu d l ments peu sav rer
inutile et mener des mouvements cycliques.
" Une liste T avec taille dynamique: commencer
g n ralement avec une taille grande qui diminue au fur et
mesure de lex cution
158
I. Alaya
ENSI -ISID
RECHERCHE TABOU
Avantages/Inconv nients
++ Elle se distingue des m thodes de recherche locale
simples par le recours un historique des solutions
visit es, de fa on rendre la recherche un peu moins
aveugle .
++ A l'inverse du recuit simul qui g n re de mani re
al atoire une seule solution voisine chaque it ration,
Tabou examine un chantillonnage de solutions de V(s) et
retient la meilleure s m me si f(s)>f(s). La recherche
Tabou ne s'arr te donc pas au premier optimum trouv .
-- Probl me de d termination de la taille de la liste tabou et
crit res daspiration
159
I. Alaya
Advertisement
ENSI -ISID
RECHERCHE LOCALE
Conclusion
L' l ment qui caract rise une recherche locale est le choix de la
solution voisine s dans le voisinage V(s)
" Descente :
(cid:2)s est une solution voisine plus performante que s : f (s) < f (s)
(cid:2)sest LA solution voisine LA plus performante f (s) < f (s) et "
V(s) f(s) < f(s)
s
" Recuit simul : s est choisie au hasard
- accept e si plus performante que s
- accept e si moins performante que s avec une probabilit donn e
" Recherche tabou :
s est l'une des meilleures solutions voisines de s, n'appartenant pas
la liste tabou
160
I. Alaya
ENSI -ISID
RECHERCHE LOCALE
Comparaison
" Descente (2 me randonneur) : m thode rapide, mais se
termine au premier optimum local rencontr
" Recuit & Tabou (3 me et 4 me randonneurs) : ne s'arr tent
pas au premier optimum local rencontr (gr ce aux
d gradations de f )
161
I. Alaya
ENSI -ISID
Approches volutionnaires
Algorithmes G n tiques
Algorithmes g n tiques
Origine
" Th orie de l volution et concept de S lection Naturelle de
Charles Darwin
" D s 1962, JH Holland et ses travaux sur les syst mes
adaptatifs : Crossing-Over en compl ment des mutations
" Ann es 1990, vulgarisation des algorithmes g n tiques avec
la publication de D. Goldberg
163
I. Alaya
ENSI -ISID
Algorithmes g n tiques
Un Individu est compos de:
Cellules
Chromosomes ADN
" ADN = Cha ne de G nes
" Variantes dun G ne = All le
" Emplacement du G ne sur le Chromosome = Locus
" Ensemble des Chromosomes = G nome
164
I. Alaya
ENSI -ISID
Algorithmes g n tiques
Notions principales
Evolution d'un ensemble de configurations (population)
Op rateurs d' volution : S lection, Croisement et Mutation
Proc dure g n rale
tape 1 : (initialisation)
(cid:1) Choisir un ensemble de configurations initiales (population)
tape 2 : ( volution)
(cid:1) S lection sur la population
(cid:1) Application d'op rateurs de recombinaison et de mutation
tape 3 : (mise jour)
(cid:1) R organisation de la population (ex, limination des
configurations non-performantes de la population)
165
I. Alaya
ENSI -ISID
Algorithmes g n tiques
" Individu
(cid:1) Suite de valeurs (g n ralement de bits)
" Population
(cid:1) Ensemble dindividus (solutions potentielles)
" G ne
(cid:1) Une des valeurs
166
I. Alaya
ENSI -ISID
Algorithmes g n tiques
" Algorithme g n ral
Advertisement
Les op rateurs n cessaires:
" Evaluation (calcul de f(x,y,z,&)
fitness)
" S lection (les meilleures
solutions uniquement)
" Croisement (deux parents
donnent deux enfants,
monopoint, bi-points,
uniforme...)
" Mutation (modifier une valeur
al atoirement)
167
I. Alaya
ENSI -ISID
Algorithmes g n tiques
S lection Diff rents types de s lection:
" Par rang ( litiste)
" Roue de la fortune (roulette)
Croisement un point ou multiple
Simple
Multiple
Mutations
" Taux relativement faible et volutif
" Permet de diversifier la population : viter les optima locaux
168
I. Alaya
ENSI -ISID
Algorithmes g n tiques
Avantages
" Facult dadaptation, r activit et prise en compte de
lenvironnement (les autres individus sont compris)
" Permet de traiter des espaces de recherche important
(beaucoup de solutions, pas de parcourt exhaustif envisag )
" Relativit de la qualit de la solution selon le degr de
pr cision demand
169
I. Alaya
ENSI -ISID
Algorithmes g n tiques
Inconv nients
" N cessitent plus de calculs que les autres algorithmes m ta
heuristiques (notamment la fonction valuation)
" Param tres difficiles fixer (taille population, % mutation)
" Choix de la fonction d valuation d licat
" Pas assur que la solution trouv e est la meilleure, mais
juste une approximation de la solution optimale
" Probl mes des optimums locaux si param tres mal valu s
170
I. Alaya
ENSI -ISID
Approches Hybrides
Hybridation
" Principe
Combiner diff rentes heuristiques/m taheuristiques dans un
m me algorithme
1. Hybrider deux heuristiques
Utiliser une heuristique constructive (ex: glouton) pour fournir
une solution initiale une heuristique de type recherche locale
(ex: greedy)
2. Hybrider une m taheuristique une heuristique simple
Utiliser une heuristique constructive (ex: glouton) pour fournir
une solution initiale une m taheuristique de recherche locale
(recuit simul , recherche tabou )
Essayer dam liorer les solutions trouv es par une
m taheuristique (ex: ACO, Ags) par une recherche locale
3. Hybrider deux m taheuristiques
172
I. Alaya
ENSI -ISID
Hybridation
" Avantages/ Inconv nients
++ Plusieurs m taheuristiques donnent de meilleurs
r sultats lorsquelles sont hybrid es
-- Pbm de temps dex cution
-- Pbm de param trages
173
I. Alaya
ENSI -ISID
Optimisation multi-objectifs
Optimisation multi-objectifs
Advertisement
PMO
max F(x) = (f1(x),f2(x),&, fn(x)) n e 2
s.c. x X
Variables de d cisions: (x1, x2,&, xk)
Espace objectif : Y=F(X)
175
I. Alaya
ENSI -ISID
D finitions
Relation de dominance (Cas de maximisation)
" Une solution x ={x1,...,xk} domine faiblement une solution
y ={y1,...,yk} Ssi " i {1,&,n} fi(y) d fi(x)
" Une solution x ={x1,...,xk} domine une solution y ={y1,...,yk}
Ssi " i {1,&,n} fi(x) d fi(y) et $ j {1,&,n} tq fj(y) < fj(x)
176
I. Alaya
ENSI 2013-2014
D finitions
Relation de dominance (Cas de maximisation)
Solution 1 et Solution 2 ne sont pas comparables
177
I. Alaya
ENSI -ISID
D finitions
Pareto optimalit (Cas de maximisation)
" Une solution x* X est Pareto optimale Ssi
Objectif 1
Co t
il nexiste pas une solution x X tq F(x) domine F(x*)
Front Pareto: ensemble des solutions non domin es
178
I. Alaya
ENSI -ISID
Objectif 2
Kilom tra
D finitions
Pareto optimalit (Cas de minimisation)
179
I. Alaya
ENSI -ISID
D finitions
" Point id al
Le vecteur id al y = (y1, .., ym*) est obtenu en optimisant
s par ment chaque fonction objectif fi, i.e. yi = fi(x)
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.
" Point Nadir
correspond aux bornes sup rieures de chaque objectif sur la
surface de Pareto, et non pas dans tout l'espace faisable
180
I. Alaya
ENSI -ISID
D finitions
181
I. Alaya
ENSI -ISID
D finitions
" Convexit
Certaines m thodes d'optimisation multi-objectif
n cessitent de travailler sur un espace Y des valeurs de F
qui soit convexe.
D finition
Un ensemble Y est convexe si, pour n'importe quels deux points
distincts de cet ensemble, le segment qui relie ces deux points
est contenu dans l'ensemble S.
182
I. Alaya
ENSI -ISID
D finitions
" Convexit
Fronti re Pareto convexe
Fronti re Pareto concave
183
I. Alaya
ENSI 2012-2013
Mesures de qualit
La mesure des surfaces de compromis est un probl me
d licat car elle doit repr senter la qualit des solutions,
Advertisement
la taille du front, la r partition des solutions sur le
front,...
Deux types de m triques
" les m triques relatives : comparent deux ensembles,
" les m triques absolues : valuent un ensemble sans avoir
besoin d'autres points ou ensemble de r f rence.
184
I. Alaya
ENSI 2012-2013
Mesures de qualit
" M trique C La couverture de deux ensembles
(M trique relative)
185
I. Alaya
ENSI 2012-2013
Mesures de qualit
" M trique C La couverture de deux ensembles
Objectif 2
X
X
Objectif 1
C(X,X)= 7/9
C(X,X)= 4/8
C(X,X)`1- C(X,X)
186
I. Alaya
ENSI 2012-2013
Mesures de qualit
" L'hypervolume (M trique absolue)
Cette m trique calcule une approximation du volume
compris sous la courbe form e par les points de
l'ensemble valuer.
187
I. Alaya
ENSI 2012-2013
M thodes de r solution
" Approches de Transformation du probl me initial
en probl me uni-objectif: retournent une seule
solution
" Approches multi-objectifs (Pareto et non-Pareto):
retournent un ensemble de solutions Pareto
optimales
188
I. Alaya
ENSI 2012-2013
M thodes de transformation en probl me
mono-objectif
" M thode dagr gation (Agr gation pond r e)
l
i=1..n
i fi(x) avec l
ie0 S
l
i=1..n
i=1
min F(x) = S
s.c. x X
" M thodes de -contraintes
min fk(x)
s.c. x X
fj(x) d
j, j=1..n, j k, = (
j,&
k+1,&,
n)
" Programmation par but
l
j |fj(x)-zj|p)1/p avec l
ie0 S
l
i=1..n
i=1
j=1..n
min (S
s.c. x X
189
I. Alaya
ENSI 2012-2013