160
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
Dans le cadre de l’optimisation, il est bien entendu souhaitable que l’exploration al´ eatoire de la chaˆ ıne se concentre asymptotiquement, et le plus
rapidement possible sur l’ensemble des solutions du probl` eme. Dans ce
contexte, il est bien plus judicieux de commencer par choisir une mesure
limite concentr´ ee sur les r´ egions d´ esir´ ees. Parmi ces mesures stationnaires,
les plus connues sont sans nul doute les mesures de Boltzmann-Gibbs.
Ces mesures de Boltzmann-Gibbs de probabilit´ es sont d´ efinies par la
formule suivante :
μ β (dx) =
1
Z β
exp[−β U(x)] λ(dx) avec Z β = λ(exp[−βU ]),
Dans la d´ efinition ci-dessus, λ d´ esigne une mesure de probabilit´ e sur
l’espace E, β un param` etre de temp´ erature inverse, et enfin
U : E → [0; ∞)
une fonction ´ energie.
On notera qu’` a basse temp´ erature la mesure μ β se concentre sur les
r´ egions de faible ´ energie.
Une fois la mesure invariante fix´ ee, il reste ` a choisir judicieusement une
transition de probabilit´ e d’une chaˆ ıne de Markov ayant un tel comportement asymptotique. Il existe essentiellement deux techniques universelles permettant de construire une transition de probabilit´ e M ayant
une mesure invariante donn´ ee : la transition de Metropolis-Hastings, et
l’´ echantillonneur de Gibbs. Nous d´ ecrivons respectivement ces deux algorithmes de simulation dans la section 6.3, et dans la section 6.5.
Dans les deux sections suivantes, on examine deux exemples acad´ emiques
de mesures de Boltzmann-Gibbs. Le premier concerne la repr´ esentation d’un
probl` eme d’optimisation num´ erique en terme de mesure de Boltzmann-Gibbs.
Le second correspond au mod` ele d’Ising. Ce mod` ele probabiliste est utilis´ e
en m´ ecanique statistique pour ´ etudier des configurations ferromagn´ etiques
d’aimants.
6.2.1 Plus court chemin
On se donne un ensemble fini E m = {e 1 , . . . , e m }, muni d’une m´ etrique d.
Cet ensemble abstrait peut repr´ esenter un ensemble de villes sur une carte,
une collection d’´ etoiles dans l’espace. Ces mod` eles ne sont pas restreints `
a des
familles de points dans R
d , muni de la distance euclidienne. Ils peuvent aussi
repr´ esenter des contrˆ oles, ou des s´ equences d’objectifs ` a atteindre, muni d’une
distance refl´ etant le degr´ e de difficult´ e de passage d’un ´ etat ` a un autre, etc.
6 M´ ethodes de Monte Carlo par chaˆ ınes de Markov (MCMC)
Dans le cadre de l’optimisation, il est bien entendu souhaitable que l’exploration al´ eatoire de la chaˆ ıne se concentre asymptotiquement, et le plus
rapidement possible sur l’ensemble des solutions du probl` eme. Dans ce
contexte, il est bien plus judicieux de commencer par choisir une mesure
limite concentr´ ee sur les r´ egions d´ esir´ ees. Parmi ces mesures stationnaires,
les plus connues sont sans nul doute les mesures de Boltzmann-Gibbs.
Ces mesures de Boltzmann-Gibbs de probabilit´ es sont d´ efinies par la
formule suivante :
μ β (dx) =
1
Z β
exp[−β U(x)] λ(dx) avec Z β = λ(exp[−βU ]),
Dans la d´ efinition ci-dessus, λ d´ esigne une mesure de probabilit´ e sur
l’espace E, β un param` etre de temp´ erature inverse, et enfin
U : E → [0; ∞)
une fonction ´ energie.
On notera qu’` a basse temp´ erature la mesure μ β se concentre sur les
r´ egions de faible ´ energie.
Une fois la mesure invariante fix´ ee, il reste ` a choisir judicieusement une
transition de probabilit´ e d’une chaˆ ıne de Markov ayant un tel comportement asymptotique. Il existe essentiellement deux techniques universelles permettant de construire une transition de probabilit´ e M ayant
une mesure invariante donn´ ee : la transition de Metropolis-Hastings, et
l’´ echantillonneur de Gibbs. Nous d´ ecrivons respectivement ces deux algorithmes de simulation dans la section 6.3, et dans la section 6.5.
Dans les deux sections suivantes, on examine deux exemples acad´ emiques
de mesures de Boltzmann-Gibbs. Le premier concerne la repr´ esentation d’un
probl` eme d’optimisation num´ erique en terme de mesure de Boltzmann-Gibbs.
Le second correspond au mod` ele d’Ising. Ce mod` ele probabiliste est utilis´ e
en m´ ecanique statistique pour ´ etudier des configurations ferromagn´ etiques
d’aimants.
6.2.1 Plus court chemin
On se donne un ensemble fini E m = {e 1 , . . . , e m }, muni d’une m´ etrique d.
Cet ensemble abstrait peut repr´ esenter un ensemble de villes sur une carte,
une collection d’´ etoiles dans l’espace. Ces mod` eles ne sont pas restreints `
a des
familles de points dans R
d , muni de la distance euclidienne. Ils peuvent aussi
repr´ esenter des contrˆ oles, ou des s´ equences d’objectifs ` a atteindre, muni d’une
distance refl´ etant le degr´ e de difficult´ e de passage d’un ´ etat ` a un autre, etc.