212
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
7.6 L’algorithme du recuit simul´ e
Dans la section pr´ ec´ edente, nous avons examin´ e des ´ evolutions libres de
processus de recuits thermiques `
a tr` es haute temp´ erature. Par analogie avec
ces processus physiques, nous avons aussi d´ efini des explorations al´ eatoires
libres dans des espaces de configurations associ´ es `
a des probl` emes d’ing´ eni´ erie.
Tous ces mod` eles d’´ evolutions al´ eatoires correspondent ` a la donn´ ee d’une
s´ equence d’explorations locales sans contrainte sur des syst` emes de voisinages.
Reprenons notre analyse des processus de recuits thermiques. `
A tr` es haute
temp´ erature, le syst` eme physique peut ´ evoluer librement dans l’espace des
configurations atomiques. Pour des temp´ eratures interm´ ediaires mais assez
basses, le m´ etal a certaines difficult´ es `
a franchir des barri` eres ´ energ´ etiques.
Enfin, ` a tr` es basse temp´ erature, ces configurations ne varient plus. Le m´ etal
se trouve alors totalement gel´ e, et pi´ eg´ e dans un ´ etat m´ etastable ou stable.
Examinons de plus pr` es l’´ evolution du recuit thermique pour des temp´ eratures mod´ er´ ees. `
A la diff´ erence des hautes temp´ eratures, le processus semble
pr´ ef´ erer certaines transitions plutˆ ot que d’autres. Les passages vers des configurations plus ´ energ´ etiques restent toujours possibles, mais ces derniers sont
bien moins fr´ equents. Tout se passe comme si le processus physique acceptait moins fr´ equemment des transitions qui ne lui conviennent pas ! `
A tr` es
basse temp´ erature, les configurations qui augmentent son ´ energie interne lui
demandent trop d’efforts, et il pr´ ef` ere les ´ eviter d` es que possible. Le processus
pr´ ef` ere alors orienter ses choix uniquement vers de nouvelles configurations
diminuant son ´ energie interne. Il ´ evolue alors tranquillement, et sans plus
d’efforts, tel un skieur sur une piste noire vers un ´ etat stable ou m´ etastable.
D’un point de vue purement math´ ematique, ces propri´ et´ es physiques du
recuit thermique correspondent `
a des probabilit´ es plus ou moins grandes d’acceptation, ou de rejet de certaines transitions. L’amplitude de ces probabilit´ es
d´ epend de deux param` etres : les sch´ emas de d´ ecroissance de la temp´ erature,
et les mesures des efforts n´ ecessaires pour effectuer une transition donn´ ee.
Pour pr´ eciser ces deux notions, il convient de se donner une fonction
d’´ energie positive V sur l’espace des configurations E. Chaque ´ etat x est
associ´ e `
a une quantit´ e d’´ energie V (x). Lorsque le marcheur est sur un site
x, il poss` ede une ´ energie interne V (x). Cette valeur correspond `
a l’effort que
doit produire notre marcheur virtuel pour passer d’un ´ etat d’´ energie nulle `
a
un ´ etat d’´ energie V (x). Notre explorateur ´ evalue le degr´ e de difficult´ e pour
passer d’un ´ etat x vers un ´ etat y de la fa¸ con suivante :
– Lorsque V (y) ≤ V (x), il peut bruler son carburant librement, et passer sans effort d’une ´ energie V (x) `
a une ´ energie interne inf´ erieure. La
transition x y ne lui coˆ ute rien, et il l’accepte sans broncher !
– Lorsque V (y) > V (x), il lui manque un peu de carburant ! Il doit faire
un certain effort pour passer d’une ´ energie V (x) ` a une ´ energie interne
sup´ erieure V (y).
Cet effort est exactement ´ egal ` a la diff´ erence d’´ energie (V (y) − V (x)).
Notre explorateur intr´ epide accepte n´ eanmoins cette transition x y
ˆ
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
7.6 L’algorithme du recuit simul´ e
Dans la section pr´ ec´ edente, nous avons examin´ e des ´ evolutions libres de
processus de recuits thermiques `
a tr` es haute temp´ erature. Par analogie avec
ces processus physiques, nous avons aussi d´ efini des explorations al´ eatoires
libres dans des espaces de configurations associ´ es `
a des probl` emes d’ing´ eni´ erie.
Tous ces mod` eles d’´ evolutions al´ eatoires correspondent ` a la donn´ ee d’une
s´ equence d’explorations locales sans contrainte sur des syst` emes de voisinages.
Reprenons notre analyse des processus de recuits thermiques. `
A tr` es haute
temp´ erature, le syst` eme physique peut ´ evoluer librement dans l’espace des
configurations atomiques. Pour des temp´ eratures interm´ ediaires mais assez
basses, le m´ etal a certaines difficult´ es `
a franchir des barri` eres ´ energ´ etiques.
Enfin, ` a tr` es basse temp´ erature, ces configurations ne varient plus. Le m´ etal
se trouve alors totalement gel´ e, et pi´ eg´ e dans un ´ etat m´ etastable ou stable.
Examinons de plus pr` es l’´ evolution du recuit thermique pour des temp´ eratures mod´ er´ ees. `
A la diff´ erence des hautes temp´ eratures, le processus semble
pr´ ef´ erer certaines transitions plutˆ ot que d’autres. Les passages vers des configurations plus ´ energ´ etiques restent toujours possibles, mais ces derniers sont
bien moins fr´ equents. Tout se passe comme si le processus physique acceptait moins fr´ equemment des transitions qui ne lui conviennent pas ! `
A tr` es
basse temp´ erature, les configurations qui augmentent son ´ energie interne lui
demandent trop d’efforts, et il pr´ ef` ere les ´ eviter d` es que possible. Le processus
pr´ ef` ere alors orienter ses choix uniquement vers de nouvelles configurations
diminuant son ´ energie interne. Il ´ evolue alors tranquillement, et sans plus
d’efforts, tel un skieur sur une piste noire vers un ´ etat stable ou m´ etastable.
D’un point de vue purement math´ ematique, ces propri´ et´ es physiques du
recuit thermique correspondent `
a des probabilit´ es plus ou moins grandes d’acceptation, ou de rejet de certaines transitions. L’amplitude de ces probabilit´ es
d´ epend de deux param` etres : les sch´ emas de d´ ecroissance de la temp´ erature,
et les mesures des efforts n´ ecessaires pour effectuer une transition donn´ ee.
Pour pr´ eciser ces deux notions, il convient de se donner une fonction
d’´ energie positive V sur l’espace des configurations E. Chaque ´ etat x est
associ´ e `
a une quantit´ e d’´ energie V (x). Lorsque le marcheur est sur un site
x, il poss` ede une ´ energie interne V (x). Cette valeur correspond `
a l’effort que
doit produire notre marcheur virtuel pour passer d’un ´ etat d’´ energie nulle `
a
un ´ etat d’´ energie V (x). Notre explorateur ´ evalue le degr´ e de difficult´ e pour
passer d’un ´ etat x vers un ´ etat y de la fa¸ con suivante :
– Lorsque V (y) ≤ V (x), il peut bruler son carburant librement, et passer sans effort d’une ´ energie V (x) `
a une ´ energie interne inf´ erieure. La
transition x y ne lui coˆ ute rien, et il l’accepte sans broncher !
– Lorsque V (y) > V (x), il lui manque un peu de carburant ! Il doit faire
un certain effort pour passer d’une ´ energie V (x) ` a une ´ energie interne
sup´ erieure V (y).
Cet effort est exactement ´ egal ` a la diff´ erence d’´ energie (V (y) − V (x)).
Notre explorateur intr´ epide accepte n´ eanmoins cette transition x y
ˆ