11.3 La méthode du recuit simulé
407
© Dunod – Toute reproduction non autorisée est un délit.
cette condi tion est réa li sée de la manière sui vante : on tire au hasard un nombre
com pris entre 0 et 1, et on accepte la confi gu ra tion dégra dant la fonc tion objec tif de
la quan tité DE, si le nombre tiré est infé rieur ou égal à exp(–DE/T)). En appli quant
itérativement cette règle d’accep ta tion de Metropolis, on engendre une séquence de
confi gu ra tions qui consti tue une chaîne de Markov (en ce sens que chaque confi -
gu ra tion ne dépend que de celle qui la pré cède immé dia te ment). Avec ce for ma
lisme, on montre que, lorsque la chaîne est de « lon gueur » infi nie, c’est- à-dire que
le nombre de tran si tions est illi mité (en pra tique : lorsque la chaîne est de lon gueur
suf fi sante…), le sys tème atteint (en pra tique : se rap proche de) l’équi libre ther mo dy
na mique à la tem pé ra ture consi dé rée : autre ment dit, on abou tit à une dis tri bu tion de
Boltzmann des états d’éner gie à cette tem pé ra ture.
On com prend le rôle confié à la tem pé ra ture par la règle de Metropolis : à haute
tem pé ra ture, DE/T est voi sin de 0, et donc exp(–DE/T) est voi sin de 1 ; par consé
quent la plu part des mou ve ments sont accep tés : l’algo rithme équi vaut à une simple
marche aléa toire dans l’espace des confi gu ra tions. À basse tem pé ra ture, DE/T est très
grand, et donc exp(–DE/T) est voi sin de 0 ; par consé quent la plu part des mou ve ments
aug men tant l’éner gie sont refu sés : l’algo rithme se ramène à une amé lio ra tion ité ra
tive clas sique. À tem pé ra ture inter mé diaire, l’algo rithme auto rise, de temps en temps,
des trans for ma tions qui dégradent la fonc tion objec tif : il laisse ainsi au sys tème une
chance de s’extraire d’un mini mum local (comme, en Figure 11.1, le pas sage de c n
à cr n , qui peut per mettre ensuite d’atteindre c*). Une fois l’équi libre ther mo dy na
mique atteint à une tem pé ra ture don née, on abaisse légè re ment la tem pé ra ture, et l’on
engendre une nou velle séquence de confi gu ra tions (nou velle chaîne de Markov) à ce
nou veau palier de tem pé ra ture (si la tem pé ra ture est abais sée trop vite, l’évo lu tion
vers le nou vel équi libre ther mo dy na mique est ralen tie : la théo rie éta blit une cor ré la
tion étroite entre le taux de décrois sance de la tem pé ra ture et la durée mini male des
paliers de tem pé ra ture). À l’issue des dif fé rents paliers de tem pé ra ture, on constate une
aug men ta tion pro gres sive de la fré quence des confi gu ra tions de faible coût (de basse
éner gie) : lorsque la tem pé ra ture tend vers zéro, l’algo rithme converge vers la confi -
gu ra tion de coût mini mal (mini mum absolu de l’éner gie). En pra tique, le pro ces sus est
stoppé lorsque le sys tème est figé : la tem pé ra ture a atteint la valeur nulle, ou bien plus
aucun mou ve ment de remon tée du coût (accrois se ment de l’éner gie) n’a été accepté
au cours du palier. L’orga ni gramme de l’algo rithme du recuit simulé est pré senté en
Figure 11.3.
En résumé. Les inconvé nients du recuit simulé résident d’une part dans les
« réglages », comme la ges tion de la décrois sance par paliers de la tem pé ra ture ;
de « bons » réglages relèvent sou vent du savoir faire de l’ingé nieur. D’autre
part, les temps de cal cul peuvent deve nir selon les cas très impor tants (ce qui a
conduit à des parallélisations de la méthode). Par contre, les méthodes de recuit
simulé ont l’avan tage d’être souples et rapi de ment implémentables lors qu’on
veut résoudre des pro blèmes d’opti mi sation com bi na toire, le plus sou vent de
grande taille. Elles ont donné d’excel lents résul tats pour nombre de pro blèmes,
et notam ment pour le pro blème du voya geur de com merce (TSP), sur des
ins tances com por tant plu sieurs cen taines, voire plu sieurs milliers de villes.
407
© Dunod – Toute reproduction non autorisée est un délit.
cette condi tion est réa li sée de la manière sui vante : on tire au hasard un nombre
com pris entre 0 et 1, et on accepte la confi gu ra tion dégra dant la fonc tion objec tif de
la quan tité DE, si le nombre tiré est infé rieur ou égal à exp(–DE/T)). En appli quant
itérativement cette règle d’accep ta tion de Metropolis, on engendre une séquence de
confi gu ra tions qui consti tue une chaîne de Markov (en ce sens que chaque confi -
gu ra tion ne dépend que de celle qui la pré cède immé dia te ment). Avec ce for ma
lisme, on montre que, lorsque la chaîne est de « lon gueur » infi nie, c’est- à-dire que
le nombre de tran si tions est illi mité (en pra tique : lorsque la chaîne est de lon gueur
suf fi sante…), le sys tème atteint (en pra tique : se rap proche de) l’équi libre ther mo dy
na mique à la tem pé ra ture consi dé rée : autre ment dit, on abou tit à une dis tri bu tion de
Boltzmann des états d’éner gie à cette tem pé ra ture.
On com prend le rôle confié à la tem pé ra ture par la règle de Metropolis : à haute
tem pé ra ture, DE/T est voi sin de 0, et donc exp(–DE/T) est voi sin de 1 ; par consé
quent la plu part des mou ve ments sont accep tés : l’algo rithme équi vaut à une simple
marche aléa toire dans l’espace des confi gu ra tions. À basse tem pé ra ture, DE/T est très
grand, et donc exp(–DE/T) est voi sin de 0 ; par consé quent la plu part des mou ve ments
aug men tant l’éner gie sont refu sés : l’algo rithme se ramène à une amé lio ra tion ité ra
tive clas sique. À tem pé ra ture inter mé diaire, l’algo rithme auto rise, de temps en temps,
des trans for ma tions qui dégradent la fonc tion objec tif : il laisse ainsi au sys tème une
chance de s’extraire d’un mini mum local (comme, en Figure 11.1, le pas sage de c n
à cr n , qui peut per mettre ensuite d’atteindre c*). Une fois l’équi libre ther mo dy na
mique atteint à une tem pé ra ture don née, on abaisse légè re ment la tem pé ra ture, et l’on
engendre une nou velle séquence de confi gu ra tions (nou velle chaîne de Markov) à ce
nou veau palier de tem pé ra ture (si la tem pé ra ture est abais sée trop vite, l’évo lu tion
vers le nou vel équi libre ther mo dy na mique est ralen tie : la théo rie éta blit une cor ré la
tion étroite entre le taux de décrois sance de la tem pé ra ture et la durée mini male des
paliers de tem pé ra ture). À l’issue des dif fé rents paliers de tem pé ra ture, on constate une
aug men ta tion pro gres sive de la fré quence des confi gu ra tions de faible coût (de basse
éner gie) : lorsque la tem pé ra ture tend vers zéro, l’algo rithme converge vers la confi -
gu ra tion de coût mini mal (mini mum absolu de l’éner gie). En pra tique, le pro ces sus est
stoppé lorsque le sys tème est figé : la tem pé ra ture a atteint la valeur nulle, ou bien plus
aucun mou ve ment de remon tée du coût (accrois se ment de l’éner gie) n’a été accepté
au cours du palier. L’orga ni gramme de l’algo rithme du recuit simulé est pré senté en
Figure 11.3.
En résumé. Les inconvé nients du recuit simulé résident d’une part dans les
« réglages », comme la ges tion de la décrois sance par paliers de la tem pé ra ture ;
de « bons » réglages relèvent sou vent du savoir faire de l’ingé nieur. D’autre
part, les temps de cal cul peuvent deve nir selon les cas très impor tants (ce qui a
conduit à des parallélisations de la méthode). Par contre, les méthodes de recuit
simulé ont l’avan tage d’être souples et rapi de ment implémentables lors qu’on
veut résoudre des pro blèmes d’opti mi sation com bi na toire, le plus sou vent de
grande taille. Elles ont donné d’excel lents résul tats pour nombre de pro blèmes,
et notam ment pour le pro blème du voya geur de com merce (TSP), sur des
ins tances com por tant plu sieurs cen taines, voire plu sieurs milliers de villes.