11.3 La méthode du recuit simulé
405
© Dunod – Toute reproduction non autorisée est un délit.
11.3.1 Ana lo gie entre un pro blème d’opti mi sation
et cer tains phé no mènes phy siques
L’idée du recuit simulé peut être illus trée par une image ins pi rée par les pro blèmes de
pla ce ment et de rou tage des cir cuits élec tro niques : sup po sons qu’un élec tro ni cien peu
consciencieux ait jeté au hasard les com po sants sur un plan, et éta bli les connexions
comme indi qué sur la Figure 11.2(a). Il est clair que la dis po si tion obte nue est inac cep -
table pour des rai sons de lisi bilité et de fia bi lité. Le rôle d’un pro gramme de placementroutage est de trans for mer cette situa tion désor don née pour abou tir à un schéma élec trique
ordonné (Figure 11.2(b)), où toutes les connexions sont rec ti lignes, les com po sants ali -
gnés et pla cés de manière à minimi ser la fonc tion objec tif men tion née plus haut. En
d’autres termes, ce pro gramme doit réa li ser une trans for ma tion désordre ordre, qui, par
tant d’un « liquide » de com po sants, abou tit à un « solide » ordonné.
Figure 11.2 Trans for ma tion désordre- ordre réa li sée
par un pro gramme de placement- routage.
Or une telle trans for ma tion se pro duit spon ta né ment dans la nature si l’on abaisse
pro gres si ve ment la tem pé ra ture d’un sys tème ; il existe des tech niques numé riques
de simu la tion, sur ordi na teur, du com por te ment d’ensembles de par ti cules en inter
ac tion en fonc tion de la tem pé ra ture. Afin de trans po ser ces tech niques aux pro -
blèmes d’opti mi sation, on éta blit l’ana lo gie pré sen tée dans le tableau sui vant :
Pour conduire un sys tème phy sique dans un état de basse éner gie, les phy si ciens
uti lisent géné ra le ment la tech nique du recuit : nous allons exa mi ner com ment cette
405
© Dunod – Toute reproduction non autorisée est un délit.
11.3.1 Ana lo gie entre un pro blème d’opti mi sation
et cer tains phé no mènes phy siques
L’idée du recuit simulé peut être illus trée par une image ins pi rée par les pro blèmes de
pla ce ment et de rou tage des cir cuits élec tro niques : sup po sons qu’un élec tro ni cien peu
consciencieux ait jeté au hasard les com po sants sur un plan, et éta bli les connexions
comme indi qué sur la Figure 11.2(a). Il est clair que la dis po si tion obte nue est inac cep -
table pour des rai sons de lisi bilité et de fia bi lité. Le rôle d’un pro gramme de placementroutage est de trans for mer cette situa tion désor don née pour abou tir à un schéma élec trique
ordonné (Figure 11.2(b)), où toutes les connexions sont rec ti lignes, les com po sants ali -
gnés et pla cés de manière à minimi ser la fonc tion objec tif men tion née plus haut. En
d’autres termes, ce pro gramme doit réa li ser une trans for ma tion désordre ordre, qui, par
tant d’un « liquide » de com po sants, abou tit à un « solide » ordonné.
Figure 11.2 Trans for ma tion désordre- ordre réa li sée
par un pro gramme de placement- routage.
Or une telle trans for ma tion se pro duit spon ta né ment dans la nature si l’on abaisse
pro gres si ve ment la tem pé ra ture d’un sys tème ; il existe des tech niques numé riques
de simu la tion, sur ordi na teur, du com por te ment d’ensembles de par ti cules en inter
ac tion en fonc tion de la tem pé ra ture. Afin de trans po ser ces tech niques aux pro -
blèmes d’opti mi sation, on éta blit l’ana lo gie pré sen tée dans le tableau sui vant :
Pour conduire un sys tème phy sique dans un état de basse éner gie, les phy si ciens
uti lisent géné ra le ment la tech nique du recuit : nous allons exa mi ner com ment cette