<!-- Slide number: 1 -->
La recherche tabou
Réalisé par
Boudhina Arij
<!-- Slide number: 2 -->
Plan
1
Introduction
Historique
2
3
Définition
4
Domaine d’application et Principe de la Recherche Tabou
5
Algorithme générale de la recherche tabou
9
Etude d’un exemple
10
Avantages et inconvénients de la Recherche tabou
11
Conclusion
Notes:
<!-- Slide number: 3 -->
Introduction
Un problème d’optimisation consiste à chercher le minimum s d’une fonction f (fonction économique) sur un ensemble fini S, les éléments de S vérifiant certaines contraintes sont appelés solutions réalisables ; parmi lesquels, figure la solution optimal
La recherche Tabou est une méthode efficace et simple, elle peut être appliquée à un grand nombre de problème d’optimisation combinatoire.
<!-- Slide number: 4 -->
Historique
Recherche TABOU
Notes:
son origine remonte à 1977 lorsque Fred Glover décrit un mécanisme de mémoire très simple pour implémenter l'heuristique d'assignation oscillante.
1986 il introduit la Recherche Tabou comme une metaheuristique enfin en 1989 Fred Glover fournit une description complète de la méthode.
<!-- Slide number: 5 -->
Définition
Métaheuristique
L’idée de base des métaheuristiques est d’accepter provisoirement une
mauvaise solution pour trouver une meilleure solution :
Pour éviter de rester bloqué sur un optimum local.
Eviter de boucler.
Pour parcourir le plus d'espace possible.
<!-- Slide number: 6 -->
Définition
Le mot Tabou vient du Tonga polynésien. Le Tonga indique une chose qui ne peut pas être touchée parce qu’elle est sacré, la signification du mot Tabou (Tabu en anglais) est interdit
La Recherche Tabou est une méthode heuristique de Recherche Locale utilisée pour résoudre des problèmes complexes et de très grande taille.
Une Recherche Locale simple mais avec une mémoire.
Mémoire à court terme : diversification
Mémoire à long terme : intensification
<!-- Slide number: 7 -->
Domaine d’application
Problèmes de transport.
Planification et ordonnancement.
Optimisation de graphes.
Télécommunications.
Logique et intelligence artificielle.
<!-- Slide number: 8 -->
Principe de la Recherche Tabou
Poursuivre la recherche de solutions même lorsqu’un optimum local est rencontré.
Publicité
⇒ En permettant des déplacements qui n’améliorent pas la solution.
⇒ En utilisant le principe de mémoire pour éviter les mouvements cycliques.
Notes:
<!-- Slide number: 9 -->
Algorithme générale de la recherche tabou
s0 : solution initiale
s* : meilleure solution jusqu'à présent
s : nouvelle solutions du voisinage de s*
f(s) : fonction objectif à minimiser
f(s*) : valeur de la meilleure solution.
<!-- Slide number: 10 -->
Éléments de la Recherche Tabou
Voisinage (neighborhood)
L’ensemble des solutions que l’on peut atteindre à partir d’une solution.
Un mouvement permet de passer d’une solution valide à une autre. On dit que la nouvelle solution est un voisin de la précédente.
Mouvement
Passer de la solution actuelle à la solution voisine.
Liste Tabou
Une mémoire à court terme qui enregistre les solutions qui ont été visitées pour éviter de répéter la recherche.
<!-- Slide number: 11 -->
Critère d'aspiration
Lorsqu'une solution dans la liste tabou est meilleure que la meilleure solution actuellement connue, la solution actuellement connue est remplacée par la meilleure solution.
Critères d’arrêt
On peut arrêter la recherche à tout moment, contrairement au recuit simulé.
Des critères d’arrêt possibles sont :
Toutes les solutions voisines sont tabou
Une solution prouvée optimale a été trouvée
Nombre maximal d'itérations dépassé
Nombre d’itérations sans amélioration de la meilleure configuration trouvée
<!-- Slide number: 12 -->
Diverses améliorations de la Recherche Tabou
La recherche de la solution optimale peut être améliorée.
Intensification
Est l’une des stratégies qui permet de mémoriser les meilleures solutions
rencontrées (ou leur configuration) et les utilise afin d’améliorer la recherche.
Diversification
Cherche à utiliser des mouvements encore jamais réalisés afin d’explorer des régions nouvelles de l’espace de recherche en mémorisant bien sur les solutions les plus visitées.
⇒ Les deux stratégies sont complémentaires.
Notes:
<!-- Slide number: 13 -->
Etude d’un exemple
Placer n reines sur un échiquier nxn, de telle manière qu’aucune reine n’en capture une autre.
| | | | R1 | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | R2 | | |
| | | R3 | | | | |
| | | | | | R4 | |
| | | | | | | R5 |
| R6 | | | | | | |
| | R7 | | | | | |
| 4 | 5 | 3 | 6 | 7 | 1 | 2 |
| --- | --- | --- | --- | --- | --- | --- |
<!-- Slide number: 14 -->
Formulation d’une collision :
X = {X(1), X(2),X(3),X(4),……,X(n)} ; X(i) est l’index de la colonne avec :
X(i) ≠ X(j) (pour que deux reines ne soient pas placées dans la même ligne ou la même colonne).
Publicité
les reines doivent être sur des diagonales différentes.
Pour représenter ce problème, on a:
Liste Tabou : contient les mouvements interdits.
Mouvement (permettant d’aller d’une solution à une autre) : correspond à permuter les positions des deux reines en collision.
Critère d’aspiration : entreprendre le mouvement en respectant les contraintes de collision.
La fonction f à minimiser : minimiser le nombre de collision.
<!-- Slide number: 15 -->
Itération 0
| | | | R1 | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | R2 | | |
| | | R3 | | | | |
| | | | | | R4 | |
| | | | | | | R5 |
| R6 | | | | | | |
| | R7 | | | | | |
| 4 | 5 | 3 | 6 | 7 | 1 | 2 |
| --- | --- | --- | --- | --- | --- | --- |
Les collisions:
(R1,R2)
(R4,R5)
(R6,R7)
(R2,R6)
F= 4
12
<!-- Slide number: 16 -->
Itération 1
| | R1 | | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | R2 | | |
| | | R3 | | | | |
| | | | | | R4 | |
| | | | | | | R5 |
| R6 | | | | | | |
| | | | R7 | | | |
| 2 | 5 | 3 | 6 | 7 | 1 | 4 |
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R1,R7)
Liste Tabou:
(R1,R7)
Les collisions:
(R2,R6)
(R4,R5)
F= 2
13
<!-- Slide number: 17 -->
Itération 2
| | R1 | | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | R2 | |
| | | R3 | | | | |
| | | | | R4 | | |
| | | | | | | R5 |
| R6 | | | | | | |
| | | | R7 | | | |
| 2 | 6 | 3 | 5 | 7 | 1 | 4 |
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R2,R4)
Liste Tabou:
(R1,R7)
Publicité
(R2,R4)
Les collisions:
(R1,R4)
F= 1
14
<!-- Slide number: 18 -->
Itération 3
| | | R1 | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | R2 | |
| | R3 | | | | | |
| | | | | R4 | | |
| | | | | | | R5 |
| R6 | | | | | | |
| | | | R7 | | | |
| 3 | 6 | 2 | 5 | 7 | 1 | 4 |
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R1,R3)
Liste Tabou:
(R1,R7)
(R2,R4)
(R1,R3)
Les collisions:
(R1,R5)
F= 1
15
<!-- Slide number: 19 -->
Itération 4
| | | R1 | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | R2 | |
| | R3 | | | | | |
| | | | | R4 | | |
| | | | R5 | | | |
| R6 | | | | | | |
| | | | | | | R7 |
| 3 | 6 | 2 | 5 | 4 | 1 | 7 |
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R5,R7)
Liste Tabou:
(R1,R7)
(R2,R4)
(R1,R3)
(R5,R7)
Les collisions:
(R3,R5)
(R4,R5)
F= 2
16
<!-- Slide number: 20 -->
Itération 5
| | | R1 | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | R2 | |
| | R3 | | | | | |
| | | | | | | R4 |
| | | | R5 | | | |
| R6 | | | | | | |
| | | | | R7 | | |
| 3 | 6 | 2 | 7 | 4 | 1 | 5 |
Publicité
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R4,R7)
Liste Tabou:
(R1,R7)
(R2,R4)
(R1,R3)
(R5,R7)
(R4,R7)
Les collisions:
(R3,R5)
F= 1
17
<!-- Slide number: 21 -->
Itération 6
| | R1 | | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | | | | R2 | |
| | | R3 | | | | |
| | | | | | | R4 |
| | | | R5 | | | |
| R6 | | | | | | |
| | | | | R7 | | |
| 2 | 6 | 3 | 7 | 4 | 1 | 5 |
| --- | --- | --- | --- | --- | --- | --- |
Critère d’aspiration: (R1,R3)
Liste Tabou:
(R1,R7)
(R2,R4)
(R1,R3)
(R5,R7)
(R4,R7)
(R1,R3)
Les collisions : aucune
F= 0
18
<!-- Slide number: 22 -->
Avantages et inconvénients de la Recherche tabou
Avantages :
Offre des économies de temps de résolution pour des programmes de grosse taille .
Très bons résultats sur certains types de problèmes.
Algorithmes faciles à mettre en œuvre.
Inconvénients :
Paramètres peu intuitifs.
Demande en ressources importantes si la liste des tabous est trop imposante.
Aucune démonstration de la convergence.
<!-- Slide number: 23 -->
Conclusion
La recherche Tabou peut être considérer comme une généralisation des méthodes d’améliorations locales traditionnelles.
L’application de recherche Tabou sur n’importe quel type de problèmes ne garantie en aucun cas un succès définitif, mais le plus important est de savoir comment adapter la recherche Tabou au problème posé, et ceci en ajustant de façon adéquate ses différents composants (restriction Tabou, critère d’aspiration,…).
<!-- Slide number: 24 -->
Références
http://wwwabi.snv.jussieu.fr/jompo/Public/OBI/OBI2/Optimisation_combinatoire.pdf
http://www.cours.polymtl.ca/mth6414/automne2004/presentations/MTH6414_Recherche_Tabou.pdf
http://www.cmi.univ-mrs.fr/~preaux/PDF/Optimisation%20Combinatoire.pdf
http://julien.chauveau.online.fr/m1info/optimisation_combinatoire/assets/OC-Hao-Meta06.ppt
http://www-igm.univ-mlv.fr/~desar/Cours/M1-1_Optimisation_Combinatoire/chap5.pdf
http://www.emse.fr/spip/IMG/ppt/Morineau_26-04-07.ppt
<!-- Slide number: 25 -->
Merci pour votre attention