216
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
μ T (x) =
1
Z T
e
−
1
T V (x) μ(x) avec Z T =
y∈E
e
−
1
T V (y) μ(y)
est une mesure r´ eversible du processus de recuit homog` ene ` a temp´ erature
constante T . En physique, et plus particuli` erement en m´ ecanique statistique,
ces mesures sont appel´ ees des mesures de Boltzmann-Gibbs associ´ ees au potentiel V , et `
a la mesure de r´ ef´ erence μ. Dans ce contexte, la constante de
normalisation est souvent appel´ ee la fonction de partition.
Cette distribution μ T caract´ erise le comportement en temps long du processus de recuit `
a temp´ erature T fix´ ee. Autrement dit, si l’on laisse ´ evoluer
l’algorithme de recuit suffisamment longtemps, apr` es un horizon de temps
assez long n son ´ etat X
T
n est approximativement distribu´ e selon la loi μ T
P(X
T
n = x) μ T (x)
Nous allons d´ esormais d´ ecrire les r´ egions o` u le processus X
T
n a le plus de
chances de se trouver. Gardons toujours en vue que l’objectif de notre algorithme stochastique est d’explorer les r´ egions o` u le potentiel V est d’´ energie
minimale. Si l’on consid` ere la fonction re-centr´ ee
V
𨐽 (x) = V (x) − inf
y∈E
V (y)
ces r´ egions `
a minimum d’´ energie sont d´ ecrites par l’ensemble V d´ ecrit cidessous
V = {x ∈ E : V
(x) = 0} =
x ∈ E : V (x) = inf
y∈E
V (y)
Avec ces notations, la mesure invariante μ T du processus d’exploration peut
s’exprimer sous la forme suivante :
μ T (x) =
1
Z
T
e
−
1
T V
(x) μ(x)
avec la constante de normalisation
Z
T = =
y∈E
e
−
1
T V
(y) μ(y) =
y∈V
μ(y) +
y ∈V
e
−
1
T V
(y) μ(y)
On peut commencer par remarquer que
lim
T ↓0
Z
T =
y∈V
μ(y) = d´ ef. μ (V)
Ces derni` eres observations permettent de d´ emontrer, sans trop de difficult´ es, que la mesure μ T est ` a peu pr
´
es ´ egale `
a la restriction de la mesure μ
` a l’ensemble V lorsque T est petit
7 M´ ethodes d’exploration locale et sch´ emas de temp´ erature
μ T (x) =
1
Z T
e
−
1
T V (x) μ(x) avec Z T =
y∈E
e
−
1
T V (y) μ(y)
est une mesure r´ eversible du processus de recuit homog` ene ` a temp´ erature
constante T . En physique, et plus particuli` erement en m´ ecanique statistique,
ces mesures sont appel´ ees des mesures de Boltzmann-Gibbs associ´ ees au potentiel V , et `
a la mesure de r´ ef´ erence μ. Dans ce contexte, la constante de
normalisation est souvent appel´ ee la fonction de partition.
Cette distribution μ T caract´ erise le comportement en temps long du processus de recuit `
a temp´ erature T fix´ ee. Autrement dit, si l’on laisse ´ evoluer
l’algorithme de recuit suffisamment longtemps, apr` es un horizon de temps
assez long n son ´ etat X
T
n est approximativement distribu´ e selon la loi μ T
P(X
T
n = x) μ T (x)
Nous allons d´ esormais d´ ecrire les r´ egions o` u le processus X
T
n a le plus de
chances de se trouver. Gardons toujours en vue que l’objectif de notre algorithme stochastique est d’explorer les r´ egions o` u le potentiel V est d’´ energie
minimale. Si l’on consid` ere la fonction re-centr´ ee
V
𨐽 (x) = V (x) − inf
y∈E
V (y)
ces r´ egions `
a minimum d’´ energie sont d´ ecrites par l’ensemble V d´ ecrit cidessous
V = {x ∈ E : V
(x) = 0} =
x ∈ E : V (x) = inf
y∈E
V (y)
Avec ces notations, la mesure invariante μ T du processus d’exploration peut
s’exprimer sous la forme suivante :
μ T (x) =
1
Z
T
e
−
1
T V
(x) μ(x)
avec la constante de normalisation
Z
T = =
y∈E
e
−
1
T V
(y) μ(y) =
y∈V
μ(y) +
y ∈V
e
−
1
T V
(y) μ(y)
On peut commencer par remarquer que
lim
T ↓0
Z
T =
y∈V
μ(y) = d´ ef. μ (V)
Ces derni` eres observations permettent de d´ emontrer, sans trop de difficult´ es, que la mesure μ T est ` a peu pr
´
es ´ egale `
a la restriction de la mesure μ
` a l’ensemble V lorsque T est petit