170
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
6.4.4 L’algorithme de recuit simul´ e
L’algorithme de recuit simul´ e que nous allons pr´ esenter est une m´ ethode de
recherche al´ eatoire des extrema globaux d’une fonction num´ erique born´ ee
U : E → R + , d´ efinie sur un ensemble E. L’exploration al´ eatoire de l’espace
d’´ etat E est d´ efinie en terme d’une transition de probabilit´ es Q(x, dy) sur E,
r´ eversible par rapport ` a une mesure λ sur E. c’est-` a-dire, telle que
λ(dx) Q(x, dy) = λ(dy) Q(y, dx)
On notera que λ est n´ ecessairement une mesure invariante de Q. L’algorithme
de recuit simul´ e est un algorithme markovien non homog` ene. Il se pr´ esente
sous la forme d’une chaˆ ıne de Markov dont le noyau de transition ` a chaque
´ etape n ≥ 1 d´ epend d’un param` etre de temp´ erature T (n) ∈ R + .
– Pour n = 0, on simule une variable al´ eatoire X 0 , selon une distribution
initiale η 0 .
– A l’´ etape n, la transition X n → X n+1 est d´ ecompos´ ee en une ´ etape
d’exploration, et une ´ etape d’acceptation.
1. L’´ etape d’exploration consiste ` a proposer un ´ etat Y n de loi Q(X n , .).
2. L’´ etape d’acceptation se d´ ecompose `
a nouveau en deux sous-´ etapes :
– Si U (Y n ) ≤ U (X n ) on accepte l’´ etat Y n et on pose
X n+1 = Y n
– Si U (Y n ) > U(X n ), alors on effectue un effectue le choix al´ eatoire
suivant :
X n+1 =
Y n avec une probabilit´ e e
−
1
T (n)
(U (Yn)−U (Xn))
X n avec une probabilit´ e 1 − e
−
1
T (n)
(U (Yn)−U (Xn))
La figure 6.7 repr´ esente l’´ evolution d’un algorithme de recuit simul´ e sur 7
it´ erations, avec un rejet d’exploration ` a l’instant n = 3.
Au cours du temps, on fera d´ ecroˆ ıtre convenablement la temp´ erature de
sorte que l’algorithme de recherche se “g` ele” sur l’un des extrema globaux de la
fonction U . Le r´ eglage de la d´ ecroissance de T (n), lorsque n tend vers l’infini,
sera donc inversement li´ e aux possibilit´ es de mouvement de l’algorithme. Plus
T (n) est faible, plus l’algorithme aura tendance ` a ne plus changer d’´ etat.
Selon ces quelques remarques, une trop brusque variation de temp´ erature
pourrait conduire et figer l’algorithme dans des ´ etats non d´ esir´ es tels que les
extrema locaux de la fonction U . Cette id´ ee naturelle provient de la physique.
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
6.4.4 L’algorithme de recuit simul´ e
L’algorithme de recuit simul´ e que nous allons pr´ esenter est une m´ ethode de
recherche al´ eatoire des extrema globaux d’une fonction num´ erique born´ ee
U : E → R + , d´ efinie sur un ensemble E. L’exploration al´ eatoire de l’espace
d’´ etat E est d´ efinie en terme d’une transition de probabilit´ es Q(x, dy) sur E,
r´ eversible par rapport ` a une mesure λ sur E. c’est-` a-dire, telle que
λ(dx) Q(x, dy) = λ(dy) Q(y, dx)
On notera que λ est n´ ecessairement une mesure invariante de Q. L’algorithme
de recuit simul´ e est un algorithme markovien non homog` ene. Il se pr´ esente
sous la forme d’une chaˆ ıne de Markov dont le noyau de transition ` a chaque
´ etape n ≥ 1 d´ epend d’un param` etre de temp´ erature T (n) ∈ R + .
– Pour n = 0, on simule une variable al´ eatoire X 0 , selon une distribution
initiale η 0 .
– A l’´ etape n, la transition X n → X n+1 est d´ ecompos´ ee en une ´ etape
d’exploration, et une ´ etape d’acceptation.
1. L’´ etape d’exploration consiste ` a proposer un ´ etat Y n de loi Q(X n , .).
2. L’´ etape d’acceptation se d´ ecompose `
a nouveau en deux sous-´ etapes :
– Si U (Y n ) ≤ U (X n ) on accepte l’´ etat Y n et on pose
X n+1 = Y n
– Si U (Y n ) > U(X n ), alors on effectue un effectue le choix al´ eatoire
suivant :
X n+1 =
Y n avec une probabilit´ e e
−
1
T (n)
(U (Yn)−U (Xn))
X n avec une probabilit´ e 1 − e
−
1
T (n)
(U (Yn)−U (Xn))
La figure 6.7 repr´ esente l’´ evolution d’un algorithme de recuit simul´ e sur 7
it´ erations, avec un rejet d’exploration ` a l’instant n = 3.
Au cours du temps, on fera d´ ecroˆ ıtre convenablement la temp´ erature de
sorte que l’algorithme de recherche se “g` ele” sur l’un des extrema globaux de la
fonction U . Le r´ eglage de la d´ ecroissance de T (n), lorsque n tend vers l’infini,
sera donc inversement li´ e aux possibilit´ es de mouvement de l’algorithme. Plus
T (n) est faible, plus l’algorithme aura tendance ` a ne plus changer d’´ etat.
Selon ces quelques remarques, une trop brusque variation de temp´ erature
pourrait conduire et figer l’algorithme dans des ´ etats non d´ esir´ es tels que les
extrema locaux de la fonction U . Cette id´ ee naturelle provient de la physique.