Chapitre 11 • Métaheuristiques en optimisation combinatoire
410
des mou ve ments inter dits, et non des confi gu ra tions inter dites – peut blo quer l’accès
à cer taines solu tions, pour tant non encore visi tées. En effet, l’on ne sau ve garde
géné ra le ment dans la liste tabou que la défi ni tion des mou ve ments inter dits (qui ne
s’expriment pas en fonc tion des confi gu ra tions que l’on vou drait inter dire). Nous
illus trons ci- dessous ce phé no mène par un exemple simple, emprunté à De Werra.
Étant donné l’ensemble {A, B, C, D, E} des 5 pre mières lettres de l’alpha bet,
intéressons- nous aux « confi gu ra tions » for mées par les paires (non ordon nées) de
deux lettres dif fé rentes. Les « mou ve ments » assu rant le pas sage d’une confi gu ra tion
à une voi sine sont les chan ge ments d’une seule lettre de la confi gu ra tion. On réca pi -
tule dans le tableau sui vant les résul tats de quelques mou ve ments effec tués à par tir
de la confi gu ra tion {A, B} :
configuration courante
mouvement effectué
liste des mouvements tabous
{A, B}
{D, C}
B remplacé par C
A remplacé par D
C remplacé par E
C remplacé par B
C remplacé par B
D remplacé par A
C remplacé par B
D remplacé par A
E remplacé par C
{D, E}
{A, C}
À l’issue de trois mou ve ments, on voit que la confi gu ra tion {A, E} ne peut pas être
atteinte à par tir de la confi gu ra tion cou rante {D, E}, puisque le mou ve ment « D rem
placé par A » est tabou. Pour tant, cette confi gu ra tion {A, E} n’a pas encore été visi tée :
ainsi la liste tabou, créée dans le seul but d’empê cher le retour à une solu tion visi tée
récem ment, peut elle aussi inter dire l’accès à une solu tion non encore visi tée…
Pour évi ter cet inconvé nient, on peut employer la méthode plus com plexe dite
Tabou géné ra li sée, qui pré voit la pos si bi lité d’annu ler le sta tut tabou d’un mou ve
ment, lorsque le béné fice escompté est suf fi sant. Cette cir constance est appré ciée à
l’aide de la notion de niveau d’aspi ra tion, qu’il serait trop long d’expli ci ter ici.
En outre, l’algo rithme décrit jus qu’ici n’exploite qu’une forme rudi men taire de
mémoire, la mémoire à court terme des solu tions visi tées récem ment, au moyen de
la liste tabou. Deux méca nismes sup plé men taires, nom més inten si fi ca tion et diver
si fi ca tion, sont sou vent mis en œuvre pour doter aussi l’algo rithme d’une mémoire à
long terme. Ces méca nismes n’exploitent plus la proxi mité dans le temps d’évé ne
ments par ti cu liers, mais plu tôt la fré quence de leur occur rence, sur une période plus
longue. L’inten si fi ca tion consiste à appro fon dir l’explo ra tion de cer taines régions de
l’espace des solu tions, iden ti fiées comme par ti cu liè re ment pro met teuses. La diver si -
fi ca tion est, au contraire, la réorien ta tion pério dique de la recherche d’un opti mum vers
des régions trop rare ment visi tées jus qu’alors. De nom breuses stra té gies d’inten si fi -
ca tion et de diver si fi ca tion ont été publiées. Enfin, de mul tiples per fec tion ne ments de
410
des mou ve ments inter dits, et non des confi gu ra tions inter dites – peut blo quer l’accès
à cer taines solu tions, pour tant non encore visi tées. En effet, l’on ne sau ve garde
géné ra le ment dans la liste tabou que la défi ni tion des mou ve ments inter dits (qui ne
s’expriment pas en fonc tion des confi gu ra tions que l’on vou drait inter dire). Nous
illus trons ci- dessous ce phé no mène par un exemple simple, emprunté à De Werra.
Étant donné l’ensemble {A, B, C, D, E} des 5 pre mières lettres de l’alpha bet,
intéressons- nous aux « confi gu ra tions » for mées par les paires (non ordon nées) de
deux lettres dif fé rentes. Les « mou ve ments » assu rant le pas sage d’une confi gu ra tion
à une voi sine sont les chan ge ments d’une seule lettre de la confi gu ra tion. On réca pi -
tule dans le tableau sui vant les résul tats de quelques mou ve ments effec tués à par tir
de la confi gu ra tion {A, B} :
configuration courante
mouvement effectué
liste des mouvements tabous
{A, B}
{D, C}
B remplacé par C
A remplacé par D
C remplacé par E
C remplacé par B
C remplacé par B
D remplacé par A
C remplacé par B
D remplacé par A
E remplacé par C
{D, E}
{A, C}
À l’issue de trois mou ve ments, on voit que la confi gu ra tion {A, E} ne peut pas être
atteinte à par tir de la confi gu ra tion cou rante {D, E}, puisque le mou ve ment « D rem
placé par A » est tabou. Pour tant, cette confi gu ra tion {A, E} n’a pas encore été visi tée :
ainsi la liste tabou, créée dans le seul but d’empê cher le retour à une solu tion visi tée
récem ment, peut elle aussi inter dire l’accès à une solu tion non encore visi tée…
Pour évi ter cet inconvé nient, on peut employer la méthode plus com plexe dite
Tabou géné ra li sée, qui pré voit la pos si bi lité d’annu ler le sta tut tabou d’un mou ve
ment, lorsque le béné fice escompté est suf fi sant. Cette cir constance est appré ciée à
l’aide de la notion de niveau d’aspi ra tion, qu’il serait trop long d’expli ci ter ici.
En outre, l’algo rithme décrit jus qu’ici n’exploite qu’une forme rudi men taire de
mémoire, la mémoire à court terme des solu tions visi tées récem ment, au moyen de
la liste tabou. Deux méca nismes sup plé men taires, nom més inten si fi ca tion et diver
si fi ca tion, sont sou vent mis en œuvre pour doter aussi l’algo rithme d’une mémoire à
long terme. Ces méca nismes n’exploitent plus la proxi mité dans le temps d’évé ne
ments par ti cu liers, mais plu tôt la fré quence de leur occur rence, sur une période plus
longue. L’inten si fi ca tion consiste à appro fon dir l’explo ra tion de cer taines régions de
l’espace des solu tions, iden ti fiées comme par ti cu liè re ment pro met teuses. La diver si -
fi ca tion est, au contraire, la réorien ta tion pério dique de la recherche d’un opti mum vers
des régions trop rare ment visi tées jus qu’alors. De nom breuses stra té gies d’inten si fi -
ca tion et de diver si fi ca tion ont été publiées. Enfin, de mul tiples per fec tion ne ments de