214
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
La premi` ere transition X n X
n est une ´ etape de proposition de mouvement.
Le marcheur examine au hasard une possibilit´ e de mouvement. Cette ´ etape
consiste le plus souvent `
a proposer un ´ etat voisin de l’´ etat courant
P(X
n = y | X n = x) = M (x, y) = d´ ef.
1
|V(x)|
1 V(x) (y)
Dans la seconde ´ etape, le marcheur choisi d’effectuer la transition avec une
certaine probabilit´ e. Autrement dit, il accepte de passer sur le site propos´ e,
dans le cas contraire il reste sur place. Cette transition s’exprime sous la forme
suivante
P(X n+1 = z | X
n = y , X n = x) = g Tn (x, y) 1 y (z) + (1 − g Tn (x, y)) 1 x (z)
avec la probabilit´ e d’acceptation
g Tn (x, y) = e
−
1
Tn (V (y)−V (x))+
La probabilit´ e d’une transition
(X n = x) (X n+1 = z)
est donn´ ee par la formule des conditionnements embo t´ es
P(X n+1 = z | X n = x) =
y∈E
P(X n+1 = z, X
n = y | X n = x)
=
y∈E
P(X n+1 = z | X
n = y , X n = x)
×P(X
n = y | X n = x)
D’apr` es la discussion pr´ ec´ edente, nous avons
P(X n+1 = z | X n = x) =
y∈E
[g Tn (x, y) 1 y (z) + (1 − g Tn (x, y)) 1 x (z)]
×M (x, y)
= M (x, z) g Tn (x, z)
+
⎛
⎝ 1 −
y∈E
M (x, y)g Tn (x, y)
⎞
⎠ 1 x (z)
7.6.2 Recuit homog` ene
`
A temp´ erature constante T n = T , le recuit simul´ e est une chaˆ ıne de Markov
X
T
n homog` ene dans le temps, en ce sens o` u ses transitions not´ ees M T ne
d´ ependent pas du param` etre temporel
ˆ ı