190
Recherche opérationnelle
8.2.3.2. La méthode Tabou
La méthode Tabou, qui date de la fin des années soixante-dix, est, elle aussi, fondée sur
un principe très simple : comme la méthode du recuit simulé, elle procède par itérations
en allant de solution en solution, mais de son côté elle s'interdit de revenir à une solution
déjà trouvée (d'où sa dénomination). Supposons alors qu'elle '' tombe '' en une solution
qui est un minimum local. L'exploration du voisinage va donner des solutions moins
bonnes ; si on accepte néanmoins l'une ce ces solutions, la moins mauvaise, le fait
d'interdire la solution optimum local va nous permettre de sortir du '' trou '' constitué par
le minimum local. On voit donc que, comme dans le cadre du recuit simulé, on accepte
de dégrader la fonction économique provisoirement. Mais le principe adopté conduit à
mettre en œuvre beaucoup moins d'ingrédients d'expertise que le recuit simulé. Si on
traduit en effet le principe dans un algorithme, alors on voit qu'il suffit :
- de se donner une fonction de voisinage,
- de partir d'une solution initiale,
- à partir de la dernière solution trouvée
à l'itération , d'explorer le voisinage
de cette solution, de prendre la meilleure solution dans ce voisinage
(éventuellement moins bonne que la solution dont on part),
- d'ajouter à la liste des solutions interdites (dite liste Tabou ) la solution
- de continuer ainsi jusqu'à un test d'arrêt (en général portant sur le nombre
d'itérations).
En fait, on n'applique pas directement cette procédure en général : en effet conserver en
mémoire la liste des solutions rencontrées, trouver dans
la meilleure solution,
comparer cette solution à toutes celles de la liste T prend beaucoup de place en mémoire
et beaucoup de temps de calcul. Pour éviter ces inconvénients, on retient plutôt la
transformation élémentaire qui permet de passer de
(par exemple changement
d'un
à une certaine place dans un codage en à
d'une solution). Ce sont alors
les transformations élémentaires inverses (les « mouvements ») qui vont être interdites.
Mais cela comporte alors un nouvel inconvénient. Si je passe de
par une certaine
transformation élémentaire
et de à
par une autre transformation élémentaire ,
alors j'interdis, peut-être à tort de revenir de
vers
par un mouvement
. On
risque d'appauvrir ainsi considérablement le voisinage des solutions explorées. Pour
pallier ce défaut, on limite la liste Tabou à une certaine taille, et on la gère par une
procédure « first in - first out » : quand la liste
est pleine, on supprime de
le
mouvement qui est le plus ancien et on le remplace par celui que l'on vient d'interdire.
Comme on le voit une autre différence de la méthode Tabou avec le recuit simulé est
qu'elle est déterministe et qu'elle ne fait pas intervenir de module de recherche aléatoire.
Cela dit, elle demande a priori que l'on explore le voisinage d'une solution
de façon
exhaustive. Cela peut prendre du temps de calcul ; aussi certaines adaptations de la
méthode préconisent-elles de considérer un échantillon aléatoire du voisinage de ,
auquel cas on retrouve des considérations qui ne sont pas très éloignées de la méthode
précédente.
Recherche opérationnelle
8.2.3.2. La méthode Tabou
La méthode Tabou, qui date de la fin des années soixante-dix, est, elle aussi, fondée sur
un principe très simple : comme la méthode du recuit simulé, elle procède par itérations
en allant de solution en solution, mais de son côté elle s'interdit de revenir à une solution
déjà trouvée (d'où sa dénomination). Supposons alors qu'elle '' tombe '' en une solution
qui est un minimum local. L'exploration du voisinage va donner des solutions moins
bonnes ; si on accepte néanmoins l'une ce ces solutions, la moins mauvaise, le fait
d'interdire la solution optimum local va nous permettre de sortir du '' trou '' constitué par
le minimum local. On voit donc que, comme dans le cadre du recuit simulé, on accepte
de dégrader la fonction économique provisoirement. Mais le principe adopté conduit à
mettre en œuvre beaucoup moins d'ingrédients d'expertise que le recuit simulé. Si on
traduit en effet le principe dans un algorithme, alors on voit qu'il suffit :
- de se donner une fonction de voisinage,
- de partir d'une solution initiale,
- à partir de la dernière solution trouvée
à l'itération , d'explorer le voisinage
de cette solution, de prendre la meilleure solution dans ce voisinage
(éventuellement moins bonne que la solution dont on part),
- d'ajouter à la liste des solutions interdites (dite liste Tabou ) la solution
- de continuer ainsi jusqu'à un test d'arrêt (en général portant sur le nombre
d'itérations).
En fait, on n'applique pas directement cette procédure en général : en effet conserver en
mémoire la liste des solutions rencontrées, trouver dans
la meilleure solution,
comparer cette solution à toutes celles de la liste T prend beaucoup de place en mémoire
et beaucoup de temps de calcul. Pour éviter ces inconvénients, on retient plutôt la
transformation élémentaire qui permet de passer de
(par exemple changement
d'un
à une certaine place dans un codage en à
d'une solution). Ce sont alors
les transformations élémentaires inverses (les « mouvements ») qui vont être interdites.
Mais cela comporte alors un nouvel inconvénient. Si je passe de
par une certaine
transformation élémentaire
et de à
par une autre transformation élémentaire ,
alors j'interdis, peut-être à tort de revenir de
vers
par un mouvement
. On
risque d'appauvrir ainsi considérablement le voisinage des solutions explorées. Pour
pallier ce défaut, on limite la liste Tabou à une certaine taille, et on la gère par une
procédure « first in - first out » : quand la liste
est pleine, on supprime de
le
mouvement qui est le plus ancien et on le remplace par celui que l'on vient d'interdire.
Comme on le voit une autre différence de la méthode Tabou avec le recuit simulé est
qu'elle est déterministe et qu'elle ne fait pas intervenir de module de recherche aléatoire.
Cela dit, elle demande a priori que l'on explore le voisinage d'une solution
de façon
exhaustive. Cela peut prendre du temps de calcul ; aussi certaines adaptations de la
méthode préconisent-elles de considérer un échantillon aléatoire du voisinage de ,
auquel cas on retrouve des considérations qui ne sont pas très éloignées de la méthode
précédente.