Chapitre 11 • Métaheuristiques en optimisation combinatoire
404
Les méta heu ris tiques « dis tri buées » (telles que les algo rithmes géné tiques) ont
elles aussi des méca nismes per met tant la sor tie d’une solu tion par ti cu lière hors d’un
minimum (ou « puits ») local (piège) de la fonc tion objec tif. Ces méca nismes indi
vi duels (comme la muta tion dans les algo rithmes géné tiques) viennent, dans ce cas,
seconder le méca nisme col lec tif de lutte contre les mini mums locaux, que repré sente
le contrôle en paral lèle de toute une « popu la tion » de solu tions.
11.3 la Méthode du recuit siMulé
La struc ture com plexe de l’espace des confi gu ra tions d’un pro blème d’opti mi sation
dif fi cile, illus trée par la Figure 11.1, a ins piré une ana lo gie avec des phé no mènes
phy siques, ce qui a conduit trois chercheurs de la Société IBM : S. Kirkpatrick,
C.D. Gelatt et M.P. Vecchi, à pro po ser, en 1982, une nou velle méthode ité ra tive : la
méthode du recuit simulé [Kirk83], qui évite les mini mums locaux. Des tra vaux sem -
blables, déve lop pés indé pen dam ment à la même époque en Slovaquie par V. Cerny,
ont été publiés en 1985 [Cern85].
S. Kirkpatrick et ses col lègues étaient des spé cia listes de phy sique sta tistique (qui
s’inté res saient pré ci sé ment aux confi gu ra tions de basse éner gie de maté riaux magné -
tiques désor don nés, regrou pés sous le terme de verres de spin). La déter mi na tion
numé rique de ces confi gu ra tions posait de redou tables pro blèmes d’opti mi sation, car
le « pay sage d’éner gie » d’un verre de spin pré sente une mul ti tude de val lées de pro
fon deurs inégales ; il est ana logue au « pay sage » de la Figure 11.1. S. Kirkpatrick et
al. ont pro posé de trai ter ces pro blèmes en s’ins pi rant de la tech nique expé ri men tale
du recuit uti li sée par les métal lur gistes pour obte nir un état solide « bien ordonné »,
d’éner gie mini male (en évi tant les struc tures « méta stables », carac té ris tiques des
mini mums locaux d’éner gie). La tech nique consiste à por ter le maté riau à haute tem
pé ra ture, puis cette tem pé ra ture est abais sée len te ment. Les auteurs ont simulé ce
pro ces sus sur un ordi na teur, en adjoi gnant à l’algo rithme de Metropolis et al. – qui
per met de décrire le com por te ment d’un ensemble d’atomes en équi libre à une cer
taine tem pé ra ture – une loi empi rique de décrois sance (par paliers) de la tem pé ra ture.
La méthode du recuit simulé consiste à trans po ser ce pro cédé à la réso lu tion d’un
pro blème d’opti mi sation com bi na toire : la fonc tion de coût du pro blème, ana logue à
l’éner gie d’un maté riau, est alors minimi sée, moyen nant l’intro duc tion d’une tem pé
ra ture fic tive, qui est, dans ce cas, un simple para mètre de contrôle de l’algo rithme.
Depuis son appa ri tion, la méthode du recuit simulé a prouvé son effi ca cité dans
des domaines très divers. Elle s’est par contre avé rée trop gour mande ou inadap tée
pour cer tains pro blèmes d’opti mi sation com bi na toire, mieux réso lus par des heu ris
tiques spé ci fiques (en ordon nan ce ment par exemple).
Dans ce para graphe, nous expo sons le prin cipe de la méthode, en nous appuyant
sur l’exemple du pro blème du pla ce ment d’un cir cuit élec tro nique. Une biblio gra
phie com plète se trouve dans les ouvrages [Siar89, VanL87] et dans l’article [Coll88]
parus sur le sujet. Nous ren voyons aussi le lec teur inté ressé aux pré sen ta tions didac
tiques du recuit simulé qui figurent dans l’article [Pirl92] et dans le cha pitre 2 de
l’ouvrage [Reev95].
404
Les méta heu ris tiques « dis tri buées » (telles que les algo rithmes géné tiques) ont
elles aussi des méca nismes per met tant la sor tie d’une solu tion par ti cu lière hors d’un
minimum (ou « puits ») local (piège) de la fonc tion objec tif. Ces méca nismes indi
vi duels (comme la muta tion dans les algo rithmes géné tiques) viennent, dans ce cas,
seconder le méca nisme col lec tif de lutte contre les mini mums locaux, que repré sente
le contrôle en paral lèle de toute une « popu la tion » de solu tions.
11.3 la Méthode du recuit siMulé
La struc ture com plexe de l’espace des confi gu ra tions d’un pro blème d’opti mi sation
dif fi cile, illus trée par la Figure 11.1, a ins piré une ana lo gie avec des phé no mènes
phy siques, ce qui a conduit trois chercheurs de la Société IBM : S. Kirkpatrick,
C.D. Gelatt et M.P. Vecchi, à pro po ser, en 1982, une nou velle méthode ité ra tive : la
méthode du recuit simulé [Kirk83], qui évite les mini mums locaux. Des tra vaux sem -
blables, déve lop pés indé pen dam ment à la même époque en Slovaquie par V. Cerny,
ont été publiés en 1985 [Cern85].
S. Kirkpatrick et ses col lègues étaient des spé cia listes de phy sique sta tistique (qui
s’inté res saient pré ci sé ment aux confi gu ra tions de basse éner gie de maté riaux magné -
tiques désor don nés, regrou pés sous le terme de verres de spin). La déter mi na tion
numé rique de ces confi gu ra tions posait de redou tables pro blèmes d’opti mi sation, car
le « pay sage d’éner gie » d’un verre de spin pré sente une mul ti tude de val lées de pro
fon deurs inégales ; il est ana logue au « pay sage » de la Figure 11.1. S. Kirkpatrick et
al. ont pro posé de trai ter ces pro blèmes en s’ins pi rant de la tech nique expé ri men tale
du recuit uti li sée par les métal lur gistes pour obte nir un état solide « bien ordonné »,
d’éner gie mini male (en évi tant les struc tures « méta stables », carac té ris tiques des
mini mums locaux d’éner gie). La tech nique consiste à por ter le maté riau à haute tem
pé ra ture, puis cette tem pé ra ture est abais sée len te ment. Les auteurs ont simulé ce
pro ces sus sur un ordi na teur, en adjoi gnant à l’algo rithme de Metropolis et al. – qui
per met de décrire le com por te ment d’un ensemble d’atomes en équi libre à une cer
taine tem pé ra ture – une loi empi rique de décrois sance (par paliers) de la tem pé ra ture.
La méthode du recuit simulé consiste à trans po ser ce pro cédé à la réso lu tion d’un
pro blème d’opti mi sation com bi na toire : la fonc tion de coût du pro blème, ana logue à
l’éner gie d’un maté riau, est alors minimi sée, moyen nant l’intro duc tion d’une tem pé
ra ture fic tive, qui est, dans ce cas, un simple para mètre de contrôle de l’algo rithme.
Depuis son appa ri tion, la méthode du recuit simulé a prouvé son effi ca cité dans
des domaines très divers. Elle s’est par contre avé rée trop gour mande ou inadap tée
pour cer tains pro blèmes d’opti mi sation com bi na toire, mieux réso lus par des heu ris
tiques spé ci fiques (en ordon nan ce ment par exemple).
Dans ce para graphe, nous expo sons le prin cipe de la méthode, en nous appuyant
sur l’exemple du pro blème du pla ce ment d’un cir cuit élec tro nique. Une biblio gra
phie com plète se trouve dans les ouvrages [Siar89, VanL87] et dans l’article [Coll88]
parus sur le sujet. Nous ren voyons aussi le lec teur inté ressé aux pré sen ta tions didac
tiques du recuit simulé qui figurent dans l’article [Pirl92] et dans le cha pitre 2 de
l’ouvrage [Reev95].