74
5 Mesures de Gibbs
Q(x, y) =
1 y∈Vx
|V x |
où V x := {y ∈ E : dist(x, y) = 1}.
Si le graphe est régulier, c’est-à-dire que |V x | = |V y | pour tous x, y ∈ E, et si
μ β est la mesure uniforme sur E, alors P = (1 − ε)Q + εI, où 0 < ε < 1, et
on peut prendre ε = 0 si Q est apériodique.
Exemple 5.3 (Échantillonneur de Gibbs). Soit F ⊂ Z une partie finie et non
vide de Z, comme par exemple F = {−1, 1} comme dans le modèle d’Ising
évoqué dans l’introduction du chapitre. Soit également Λ ⊂ Z
d une partie finie
et non vide de Z
d . Soit enfin E = F
Λ . Un noyau d’exploration Q naturel sur
E consiste, à partir d’une configuration courante x ∈ E, à sélectionner un
site i ∈ Λ au hasard
4 , puis à modifier x i en utilisant la loi conditionnelle
μ β (x i | x −i ) où x −i := (x j ) j =i .
Cette loi conditionnelle est facile à calculer et à simuler dans le cas par
exemple du modèle d’Ising. Cela revient à prendre, pour tous x, y ∈ E,
Q(x, y) =
i∈Λ
q(i)μ x,i (y i )1 {x−i=y−i} , où μ x,i := μ β (x i | x −i )
et où q est une loi sur Λ chargeant tous les états comme par exemple la loi
uniforme sur Λ. L’échantillonneur de Gibbs est le nom donné à l’algorithme
de Metropolis-Hastings lorsque le noyau d’exploration Q est défini comme cela.
5.3 Algorithme du recuit simulé
L’algorithme du recuit simulé a pour objectif de minimiser une fonction
H : E → R sur E fini. Pour ce faire, on considère la mesure de Gibbs μ β
d’énergie H et de paramètre β > 0, définie pour tout x ∈ E par
μ β (x) =
1
Z β
e
−βH(x) , où Z β =
x∈E
e
−βH(x) .
Il est commode d’interpréter le paramètre 1/β comme une température ou
une variance par analogie gaussienne. La loi μ β favorise les configurations de
faible énergie, d’autant plus que la température 1/β est basse. On a établi
dans la démonstration du théorème 5.1 la convergence suivante
5 :
μ ∞ (x) := lim
β→∞
μ β (x) =
1 x∈M
|M |
où M :=
y ∈ E : H(y) = inf
E
H
.
La loi μ ∞ est uniforme sur l’ensemble M des minima globaux de H. On
prendra garde à ne pas confondre μ ∞ avec la loi μ 0 qui est uniforme sur E.
4. On préfère parfois balayer méthodiquement les sites les uns après les autres.
5. Il s’agit d’une instance très simple du principe de Laplace.
5 Mesures de Gibbs
Q(x, y) =
1 y∈Vx
|V x |
où V x := {y ∈ E : dist(x, y) = 1}.
Si le graphe est régulier, c’est-à-dire que |V x | = |V y | pour tous x, y ∈ E, et si
μ β est la mesure uniforme sur E, alors P = (1 − ε)Q + εI, où 0 < ε < 1, et
on peut prendre ε = 0 si Q est apériodique.
Exemple 5.3 (Échantillonneur de Gibbs). Soit F ⊂ Z une partie finie et non
vide de Z, comme par exemple F = {−1, 1} comme dans le modèle d’Ising
évoqué dans l’introduction du chapitre. Soit également Λ ⊂ Z
d une partie finie
et non vide de Z
d . Soit enfin E = F
Λ . Un noyau d’exploration Q naturel sur
E consiste, à partir d’une configuration courante x ∈ E, à sélectionner un
site i ∈ Λ au hasard
4 , puis à modifier x i en utilisant la loi conditionnelle
μ β (x i | x −i ) où x −i := (x j ) j =i .
Cette loi conditionnelle est facile à calculer et à simuler dans le cas par
exemple du modèle d’Ising. Cela revient à prendre, pour tous x, y ∈ E,
Q(x, y) =
i∈Λ
q(i)μ x,i (y i )1 {x−i=y−i} , où μ x,i := μ β (x i | x −i )
et où q est une loi sur Λ chargeant tous les états comme par exemple la loi
uniforme sur Λ. L’échantillonneur de Gibbs est le nom donné à l’algorithme
de Metropolis-Hastings lorsque le noyau d’exploration Q est défini comme cela.
5.3 Algorithme du recuit simulé
L’algorithme du recuit simulé a pour objectif de minimiser une fonction
H : E → R sur E fini. Pour ce faire, on considère la mesure de Gibbs μ β
d’énergie H et de paramètre β > 0, définie pour tout x ∈ E par
μ β (x) =
1
Z β
e
−βH(x) , où Z β =
x∈E
e
−βH(x) .
Il est commode d’interpréter le paramètre 1/β comme une température ou
une variance par analogie gaussienne. La loi μ β favorise les configurations de
faible énergie, d’autant plus que la température 1/β est basse. On a établi
dans la démonstration du théorème 5.1 la convergence suivante
5 :
μ ∞ (x) := lim
β→∞
μ β (x) =
1 x∈M
|M |
où M :=
y ∈ E : H(y) = inf
E
H
.
La loi μ ∞ est uniforme sur l’ensemble M des minima globaux de H. On
prendra garde à ne pas confondre μ ∞ avec la loi μ 0 qui est uniforme sur E.
4. On préfère parfois balayer méthodiquement les sites les uns après les autres.
5. Il s’agit d’une instance très simple du principe de Laplace.