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 d’aspiration a(i,m) : déterminent
quand il est avantageux d’entreprendre 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) ‹ b) s* ‹
• 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 ‹ 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 d’aspiration b) s* ‹ 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 l’intensification • Il est possible de violer une interdiction (violer T) lorsqu’un mouvement interdit permet d’obtenir 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 s’avé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 l’exé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 d’aspiration
159
I. Alaya
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)s’est 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
Publicité
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 d’un 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 d’individus (solutions potentielles)
• Gène
(cid:1) Une des valeurs
166
I. Alaya
ENSI -ISID
Algorithmes génétiques
• Algorithme général
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é d’adaptation, réactivité et prise en compte de l’environnement (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)
Publicité
• 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 d’amé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 lorsqu’elles sont hybridées
-- Pbm de temps d’exécution -- Pbm de paramétrages
173
I. Alaya
ENSI -ISID
Optimisation multi-objectifs
Optimisation multi-objectifs
PMO
max F(x) = (f1(x),f2(x),…, fn(x)) n ≥ 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) ≤ fi(x) • Une solution x ={x1,...,xk} domine une solution y ={y1,...,yk} Ssi " i˛ {1,…,n} fi(x) ≤ 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 n’existe 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
Publicité
• 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, 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 d’agrégation (Agrégation pondérée) l i=1..n
i fi(x) avec l
i≥0 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) ≤ ’
j, j=1..n, j „ k, ’ = (’
j,… ’
k+1,…, ’
n)
• Programmation par but
l
j |fj(x)-zj|p)1/p avec l
i≥0 S
l i=1..n
i=1
j=1..n
min (S s.c. x˛ X
189
I. Alaya
ENSI 2012-2013