11.4 La recherche tabou
409
© Dunod – Toute reproduction non autorisée est un délit.
mul tiples degrés de liberté, qui s’opposent – de l’avis même de l’auteur [Glov97] –
à toute ana lyse mathéma tique rigou reuse de la méthode tabou.
Le prin cipe de base de la méthode Tabou est simple. À par tir d’une solu tion ini
tiale quel conque, Tabou engendre une suc ces sion de solu tions, ou confi gu ra tions,
qui doit abou tir à une solu tion opti male. À chaque ité ra tion, le méca nisme de pas
sage d’une confi gu ra tion, soit s, à la sui vante, soit t, est le sui vant :
• on construit l’ensemble des voi sins de s, c’est- à-dire l’ensemble des confi gu ra -
tions acces sibles en un seul mou ve ment élé men taire à par tir de s (si cet ensemble est
trop vaste, on en extrait aléa toi re ment un sous- ensemble de taille fixée) ; soit V(s)
l’ensemble (ou le sous ensemble) de ces voi sins ;
• on éva lue la fonc tion objec tif f du pro blème pour cha cune des confi gu ra tions
appar te nant à V(s). La confi gu ra tion t, qui suc cède à s dans la chaîne construite par
Tabou, est la confi gu ra tion de V(s) pour laquelle f prend la valeur mini male.
Notons que la confi gu ra tion t est adop tée même si t est moins bonne que s, i.e. si
f (t) . f (s) : c’est grâce à cette par ti cu la rité que Tabou per met d’évi ter le pié geage
dans les mini mums locaux de f.
Cepen dant, telle quelle, la pro cé dure ne fonc tionne géné ra le ment pas, car il y a
un risque impor tant de retour ner à une confi gu ra tion déjà rete nue lors d’une ité ra tion
pré cé dente, ce qui pro voque un cyclage : si le meilleur voi sin de s, soit t, est moins
bon que s, le meilleur voi sin de t, recherché à l’ité ra tion sui vante, risque fort d’être
s… Pour évi ter ce phé no mène, qui concerne plu tôt des confi gu ra tions peu éloi gnées
(au sens du nombre de mou ve ments), on tient à jour, à chaque ité ra tion, une « liste
tabou » de mou ve ments inter dits ; cette liste cir cu laire – qui a donné son nom à la
méthode – contient m mou ve ments « inverses » (t S s). Il s’agit des inverses des m
der niers mou ve ments (s S t) effec tués (on prend sou vent m = 7 pour la taille de la
liste tabou ; choix qui, empi ri que ment, se révèle bon). La recherche du suc ces seur
de la confi gu ra tion cou rante s est alors res treinte aux voi sins de s qui peuvent être
atteints sans uti li ser un mou ve ment de la liste tabou.
La pro cé dure peut être stop pée dès que l’on a effec tué un nombre donné d’ité ra
tions sans amé lio rer la meilleure solu tion cou rante.
Remarque. Si l’on s’en tient au méca nisme de base décrit jus qu’ici, la
méthode tabou est déter mi niste, dans le cas où les voi sins de la solu tion cou
rante sont explo rés exhaus ti ve ment. Cepen dant des élé ments sup plé men taires,
expo sés plus loin, et qui sont le plus sou vent intro duits dans la méthode, donnent un aspect sto chas tique à la méthode tabou, même dans le cas pré cé dent.
L’algo rithme ainsi pré senté est dit « Tabou simple ». Son orga ni gramme est repré -
senté en Figure 11.4. Selon De Werra [DeWe90], il serait en par ti cu lier plus effi -
cace que le recuit simulé pour le pro blème du “colo riage d’un graphe” (associer une
couleur à tout sommet d’un graphe, sans que deux sommets adjacents n’aient la même
couleur) qui intervient, notamment, dans les problèmes d’« emploi du temps »).
Cepen dant, le mode de construc tion de la liste tabou – qui, pour des rai sons pra
tiques d’éco no mie de place mémoire et de rapi dité lors de l’explo ra tion, contient
409
© Dunod – Toute reproduction non autorisée est un délit.
mul tiples degrés de liberté, qui s’opposent – de l’avis même de l’auteur [Glov97] –
à toute ana lyse mathéma tique rigou reuse de la méthode tabou.
Le prin cipe de base de la méthode Tabou est simple. À par tir d’une solu tion ini
tiale quel conque, Tabou engendre une suc ces sion de solu tions, ou confi gu ra tions,
qui doit abou tir à une solu tion opti male. À chaque ité ra tion, le méca nisme de pas
sage d’une confi gu ra tion, soit s, à la sui vante, soit t, est le sui vant :
• on construit l’ensemble des voi sins de s, c’est- à-dire l’ensemble des confi gu ra -
tions acces sibles en un seul mou ve ment élé men taire à par tir de s (si cet ensemble est
trop vaste, on en extrait aléa toi re ment un sous- ensemble de taille fixée) ; soit V(s)
l’ensemble (ou le sous ensemble) de ces voi sins ;
• on éva lue la fonc tion objec tif f du pro blème pour cha cune des confi gu ra tions
appar te nant à V(s). La confi gu ra tion t, qui suc cède à s dans la chaîne construite par
Tabou, est la confi gu ra tion de V(s) pour laquelle f prend la valeur mini male.
Notons que la confi gu ra tion t est adop tée même si t est moins bonne que s, i.e. si
f (t) . f (s) : c’est grâce à cette par ti cu la rité que Tabou per met d’évi ter le pié geage
dans les mini mums locaux de f.
Cepen dant, telle quelle, la pro cé dure ne fonc tionne géné ra le ment pas, car il y a
un risque impor tant de retour ner à une confi gu ra tion déjà rete nue lors d’une ité ra tion
pré cé dente, ce qui pro voque un cyclage : si le meilleur voi sin de s, soit t, est moins
bon que s, le meilleur voi sin de t, recherché à l’ité ra tion sui vante, risque fort d’être
s… Pour évi ter ce phé no mène, qui concerne plu tôt des confi gu ra tions peu éloi gnées
(au sens du nombre de mou ve ments), on tient à jour, à chaque ité ra tion, une « liste
tabou » de mou ve ments inter dits ; cette liste cir cu laire – qui a donné son nom à la
méthode – contient m mou ve ments « inverses » (t S s). Il s’agit des inverses des m
der niers mou ve ments (s S t) effec tués (on prend sou vent m = 7 pour la taille de la
liste tabou ; choix qui, empi ri que ment, se révèle bon). La recherche du suc ces seur
de la confi gu ra tion cou rante s est alors res treinte aux voi sins de s qui peuvent être
atteints sans uti li ser un mou ve ment de la liste tabou.
La pro cé dure peut être stop pée dès que l’on a effec tué un nombre donné d’ité ra
tions sans amé lio rer la meilleure solu tion cou rante.
Remarque. Si l’on s’en tient au méca nisme de base décrit jus qu’ici, la
méthode tabou est déter mi niste, dans le cas où les voi sins de la solu tion cou
rante sont explo rés exhaus ti ve ment. Cepen dant des élé ments sup plé men taires,
expo sés plus loin, et qui sont le plus sou vent intro duits dans la méthode, donnent un aspect sto chas tique à la méthode tabou, même dans le cas pré cé dent.
L’algo rithme ainsi pré senté est dit « Tabou simple ». Son orga ni gramme est repré -
senté en Figure 11.4. Selon De Werra [DeWe90], il serait en par ti cu lier plus effi -
cace que le recuit simulé pour le pro blème du “colo riage d’un graphe” (associer une
couleur à tout sommet d’un graphe, sans que deux sommets adjacents n’aient la même
couleur) qui intervient, notamment, dans les problèmes d’« emploi du temps »).
Cepen dant, le mode de construc tion de la liste tabou – qui, pour des rai sons pra
tiques d’éco no mie de place mémoire et de rapi dité lors de l’explo ra tion, contient