7.6 L’algorithme du recuit simul´ e
213
avec la probabilit´ e
e
−
1
T (V (y)−V (x))
Dans le cas contraire, il reste sur place. Le param` etre T repr´ esente la
temp´ erature du milieu ` a l’instant o` u il fait son choix. Lorsque T 0,
on peut noter que cette probabilit´ e est tr` es faible e
−Cte/0 = e
−∞ = 0. `
A
tr` es basse temp´ erature, le syst` eme se g` ele, et refuse presque toujours de
faire un quelconque effort.
Si l’on combine cette ´ etape d’acceptation-rejet apr` es chaque ´ etape d’exploration locale du paysage, on obtient un processus d’exploration en deux temps.
`
A chaque ´ etape n, le marcheur en X n = x examine au hasard un de ses sites
voisins X
n = y
(X n = x) (X
n = y)
Il ´ evalue ensuite l’effort demand´ e pour passer sur ce site. Sa d´ epense
d’´ energie n´ ecessaire pour passer de x vers un nouvel ´ etat y correspond aux
variations positives d’´ energie interne de la transition x y
(V (y)−V (x)) + = max {0, (V (y) − V (x))} =
(V (y) − V (x)) si V (y) > V (x)
0
s iV (y) ≤ V (x)
Il accepte alors cette transition x y suivant les r` egles pr´ ec´ edentes.
X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))+
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))+
Comme nous l’avons indiqu´ e plus haut, dans le cas o` u V (y) ≤ V (x) le syst` eme
passe sans effort de x ` a y. Dans cette situation, la transition pr´ ec´ edente se
r´ eduit ` a une simple acceptation
X n+1 =
y avec probabilit´ e 1
x avec probabilit´ e 0
Lorsque V (y) > V (x), le syst` eme ´ evalue ses chances de passage de x vers y
X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))
7.6.1 Description de la chaˆ ıne de Markov
Dans la section pr´ ec´ edente nous avons formalis´ e l’´ evolution d’un processus
recuit physique par une chaˆ ıne de Markov X n ´ evoluant pas `
a pas selon deux
´ etapes
(X n = x) (X
n = y) X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))
213
avec la probabilit´ e
e
−
1
T (V (y)−V (x))
Dans le cas contraire, il reste sur place. Le param` etre T repr´ esente la
temp´ erature du milieu ` a l’instant o` u il fait son choix. Lorsque T 0,
on peut noter que cette probabilit´ e est tr` es faible e
−Cte/0 = e
−∞ = 0. `
A
tr` es basse temp´ erature, le syst` eme se g` ele, et refuse presque toujours de
faire un quelconque effort.
Si l’on combine cette ´ etape d’acceptation-rejet apr` es chaque ´ etape d’exploration locale du paysage, on obtient un processus d’exploration en deux temps.
`
A chaque ´ etape n, le marcheur en X n = x examine au hasard un de ses sites
voisins X
n = y
(X n = x) (X
n = y)
Il ´ evalue ensuite l’effort demand´ e pour passer sur ce site. Sa d´ epense
d’´ energie n´ ecessaire pour passer de x vers un nouvel ´ etat y correspond aux
variations positives d’´ energie interne de la transition x y
(V (y)−V (x)) + = max {0, (V (y) − V (x))} =
(V (y) − V (x)) si V (y) > V (x)
0
s iV (y) ≤ V (x)
Il accepte alors cette transition x y suivant les r` egles pr´ ec´ edentes.
X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))+
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))+
Comme nous l’avons indiqu´ e plus haut, dans le cas o` u V (y) ≤ V (x) le syst` eme
passe sans effort de x ` a y. Dans cette situation, la transition pr´ ec´ edente se
r´ eduit ` a une simple acceptation
X n+1 =
y avec probabilit´ e 1
x avec probabilit´ e 0
Lorsque V (y) > V (x), le syst` eme ´ evalue ses chances de passage de x vers y
X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))
7.6.1 Description de la chaˆ ıne de Markov
Dans la section pr´ ec´ edente nous avons formalis´ e l’´ evolution d’un processus
recuit physique par une chaˆ ıne de Markov X n ´ evoluant pas `
a pas selon deux
´ etapes
(X n = x) (X
n = y) X n+1 =
y avec probabilit´ e e
−
1
Tn (V (y)−V (x))
x avec probabilit´ e 1 − e
−
1
Tn (V (y)−V (x))