II-6. 2.3 La méthode tabou :
La recherche tabou est une métaheuristique
d'optimisation présentée par Fred Glover en
1986. On trouve souvent l'appellation recherche avec
tabous en français.
- Principe :
L'idée de la recherche tabou consiste,
à partir d'une position donnée, à en
explorer le voisinage et à choisir la position dans ce voisinage qui
minimise la fonction objectif. Il est essentiel de noter que cette
opération peut conduire à augmenter la valeur de la fonction,
c'est le cas lorsque tous les points du voisinage ont une
valeur plus élevée.
C'est à partir de ce mécanisme
que l'on échappe aux minima locaux. Le risque cependant
est qu'à l'étape suivante, on
retombe dans le minimum local auquel on vient
d'échapper. C'est pourquoi il faut que
l'heuristique ait de la mémoire, le mécanisme
consiste à interdire (d'où le nom de tabou)
certains mouvements ou certaines composantes de ce mouvement
(l'exemple le plus simple est d'interdire les
derniers mouvements).
Les positions déjà explorées sont
conservées dans ce qu'on appel la Liste Tabou
d'une taille donnée, qui est un paramètre
ajustable de l'heuristique [17].
- Les tabous :
Les tabous sont une manière de représenter la
mémoire du cheminement effectué pour diriger l'exploration vers
des régions non visitées.
La manière la plus simple de définir les tabous
est de conserver une liste T des card. (T) dernières solutions
rencontrées et on empêche la procédure d'y retourner. On
gère cette liste comme une liste circulaire : on élimine le plus
vieux tabou et on insère la nouvelle solution (cette solution peut
s'avérer coûteuse en termes de quantité d'information
requise).
On peut alors définir les tabous en fonction des
"transformations" permettant de passer d'une solution à une autre.
Ainsi, on garde une liste des card. (T). dernières transformations
effectuées et on s'interdit de les inverser.
- Algorithme :
La méthode consiste à se déplacer d'une
solution vers une autre par observation du voisinage de la solution de
départ et à définir des transformations tabous que l'on
garde en mémoire. Une transformation tabou est une transformation que
l'on s'interdit d'appliquer à la solution courante.
Début
|
Nouvelle configuration courante s = t
|
Insertion du mouvement
t ? s
dans la liste tabou
Configuration initiale s
Liste Tabou initiale vide
Perturbation de s suivant N mouvements non
tabous : Evaluation des N voisins
Sélection du meilleur voisin t
Actualisation de la meilleure solution connue
Non
Critère d'arrêt atteint
Oui
Fin
Figure II-10 : Organigramme de
l'algorithme de tabou simple.
| 
