Chapitre 11 • Métaheuristiques en optimisation combinatoire
408
ALGORITHME DU RECUIT SIMULE
CONFIGURATION INITIALE
TEMPERATURE INITIALE
NON
NON
PROGRAMME
DE RECUIT
OUI
OUI
STOP
équilibre
thermodynamique
?
système figé
?
diminution
lente de T
MODIFICATION élémentaire
REGLE D'ACCEPTATION de Metropolis
modification acceptée
modification acceptée avec la
probabilité exp (
)
si
0 :
0 :
si
T
variation d'énergie
⇒
Figure 11.3 Orga ni gramme de l’algo rithme du recuit simulé.
11.4 la recherche tabou
Comme le recuit simulé, la méthode de recherche tabou, ou sim ple ment méthode
tabou (« tabu search » en anglais), est une tech nique d’opti mi sation com bi na toire
conçue en vue de résoudre le pro blème du pié geage dans les mini mums locaux de la
fonc tion objec tif. Elle a été for ma li sée en 1986 par F. Glover [Glov86] et, indé pen
dam ment, sous une appel la tion dif fé rente, par Hansen [Hans86], mais elle tire son
ori gine de concepts anté rieurs (du domaine de l’intel li gence arti fi cielle), notam ment
d’idées déve lop pées par F. Glover [Glov77].
La prin ci pale par ti cu la rité de la méthode tient dans la mise en œuvre de méca
nismes ins pi rés de la mémoire humaine. La méthode tabou prend, sur ce plan, le
contre pied du recuit simulé, tota le ment dépourvu de mémoire, et donc inca pable
de tirer les leçons du passé. En revanche, la modé li sa tion de la mémoire intro duit de
408
ALGORITHME DU RECUIT SIMULE
CONFIGURATION INITIALE
TEMPERATURE INITIALE
NON
NON
PROGRAMME
DE RECUIT
OUI
OUI
STOP
équilibre
thermodynamique
?
système figé
?
diminution
lente de T
MODIFICATION élémentaire
REGLE D'ACCEPTATION de Metropolis
modification acceptée
modification acceptée avec la
probabilité exp (
)
si
0 :
0 :
si
T
variation d'énergie
⇒
Figure 11.3 Orga ni gramme de l’algo rithme du recuit simulé.
11.4 la recherche tabou
Comme le recuit simulé, la méthode de recherche tabou, ou sim ple ment méthode
tabou (« tabu search » en anglais), est une tech nique d’opti mi sation com bi na toire
conçue en vue de résoudre le pro blème du pié geage dans les mini mums locaux de la
fonc tion objec tif. Elle a été for ma li sée en 1986 par F. Glover [Glov86] et, indé pen
dam ment, sous une appel la tion dif fé rente, par Hansen [Hans86], mais elle tire son
ori gine de concepts anté rieurs (du domaine de l’intel li gence arti fi cielle), notam ment
d’idées déve lop pées par F. Glover [Glov77].
La prin ci pale par ti cu la rité de la méthode tient dans la mise en œuvre de méca
nismes ins pi rés de la mémoire humaine. La méthode tabou prend, sur ce plan, le
contre pied du recuit simulé, tota le ment dépourvu de mémoire, et donc inca pable
de tirer les leçons du passé. En revanche, la modé li sa tion de la mémoire intro duit de