7.6 L’algorithme du recuit simul´ e
217
lim
T ↓0
μ T (x) = μ |V (x) = d´ ef.
1
μ (V)
1 V (x) μ(x)
Par cons´ equent, pour des horizons temporels assez longs, et des temp´ eratures
assez basses l’´ etat du syst` eme X
T
n est ` a peu pr` es distribu´ e dans l’ensemble
des ´ etats stables de V selon la loi μ |V . On v´ erifie la derni` ere limite en notant
les deux implications suivantes :
V
(x) = 0 =⇒ μ T (x) =
1
Z
T
1 V (x) μ(x)
T ↓0
−→
1
μ (V)
1 V (x) μ(x)
V
(x) > 0 =⇒ μ T (x) =
1
Z
T
e
−
1
T V
(x) μ(x)
T ↓0
−→
0
7.6.4 R´ eglages de temp´ erature
R´ ecapitulons les deux principaux r´ esultats d´ ecrits dans les sections pr´ ec´ edentes.
Tout d’abord, `
a temp´ erature fix´ ee T , nous avons vu que le recuit simul´ e est
une chaˆ ıne de Markov homog` ene
X
T
0 −→ X
T
1 −→ . . . −→ X
T
n−1 −→ X
T
n −→
de transitions de probabilit´ es M T (x, y), et de loi invariante μ T . Enfin, lorsque
la temp´ erature T ↓ 0, la mesure de Gibbs se concentre sur la mesure r´ eversible
μ de la transition M , restreinte `
a l’ensemble des optima globaux du potentiel
V . On a donc deux types d’asymptotiques
P(X
T
n = x)
n↑∞
−→ μ T (x) =
1
μ(e −
1
T V )
e
−
1
T V (x) μ(x)
T ↓0
−→
1
μ (V)
1 V (x) μ(x)
En g´ en´ eral la premi` ere vitesse de convergence `
a l’´ equilibre du recuit homog` ene
est d’autant plus lente que la temp´ erature est basse. Cette propri´ et´ e refl` ete
la lourdeur du processus d’acceptation rejet. `
A tr` es basse temp´ erature, les
mauvaises propositions d’´ evolution locale sont en g´ en´ eral toutes refus´ ees ! Les
bons sch´ emas de d´ ecroissance de temp´ erature au fil du temps T n sont ceux
pour lesquels l’algorithme de recuit non homog` ene X n est tel que les deux
asymptotiques pr´ ec´ edentes se combinent et permettent de prouver que
P(X n = x)
n↑∞
−→
1
μ (V)
1 V (x) μ(x)
En r´ ealit´ e on recherche le r´ esultat plus faible suivant
P(X n ∈ V)
n↑∞
−→ 1
Lorsque les probabilit´ es de transitions M (x, y) permettent de relier deux
´ etats quelconques de l’espace d’´ etat, tous les sch´ emas de d´ ecroissance de
217
lim
T ↓0
μ T (x) = μ |V (x) = d´ ef.
1
μ (V)
1 V (x) μ(x)
Par cons´ equent, pour des horizons temporels assez longs, et des temp´ eratures
assez basses l’´ etat du syst` eme X
T
n est ` a peu pr` es distribu´ e dans l’ensemble
des ´ etats stables de V selon la loi μ |V . On v´ erifie la derni` ere limite en notant
les deux implications suivantes :
V
(x) = 0 =⇒ μ T (x) =
1
Z
T
1 V (x) μ(x)
T ↓0
−→
1
μ (V)
1 V (x) μ(x)
V
(x) > 0 =⇒ μ T (x) =
1
Z
T
e
−
1
T V
(x) μ(x)
T ↓0
−→
0
7.6.4 R´ eglages de temp´ erature
R´ ecapitulons les deux principaux r´ esultats d´ ecrits dans les sections pr´ ec´ edentes.
Tout d’abord, `
a temp´ erature fix´ ee T , nous avons vu que le recuit simul´ e est
une chaˆ ıne de Markov homog` ene
X
T
0 −→ X
T
1 −→ . . . −→ X
T
n−1 −→ X
T
n −→
de transitions de probabilit´ es M T (x, y), et de loi invariante μ T . Enfin, lorsque
la temp´ erature T ↓ 0, la mesure de Gibbs se concentre sur la mesure r´ eversible
μ de la transition M , restreinte `
a l’ensemble des optima globaux du potentiel
V . On a donc deux types d’asymptotiques
P(X
T
n = x)
n↑∞
−→ μ T (x) =
1
μ(e −
1
T V )
e
−
1
T V (x) μ(x)
T ↓0
−→
1
μ (V)
1 V (x) μ(x)
En g´ en´ eral la premi` ere vitesse de convergence `
a l’´ equilibre du recuit homog` ene
est d’autant plus lente que la temp´ erature est basse. Cette propri´ et´ e refl` ete
la lourdeur du processus d’acceptation rejet. `
A tr` es basse temp´ erature, les
mauvaises propositions d’´ evolution locale sont en g´ en´ eral toutes refus´ ees ! Les
bons sch´ emas de d´ ecroissance de temp´ erature au fil du temps T n sont ceux
pour lesquels l’algorithme de recuit non homog` ene X n est tel que les deux
asymptotiques pr´ ec´ edentes se combinent et permettent de prouver que
P(X n = x)
n↑∞
−→
1
μ (V)
1 V (x) μ(x)
En r´ ealit´ e on recherche le r´ esultat plus faible suivant
P(X n ∈ V)
n↑∞
−→ 1
Lorsque les probabilit´ es de transitions M (x, y) permettent de relier deux
´ etats quelconques de l’espace d’´ etat, tous les sch´ emas de d´ ecroissance de