Algorithmes de simulation

Loi d'un champ de Markov

$$P(x)=\frac{1}{Z}\exp(-\sum_{c \in C} U_c (x))$$

Simulation

• La loi globale d'un champ de Markov n'est pas calculable, à cause de la fonction de partition Z.
• On montre que la loi conditionnelle prend une forme simple ne faisant intervenir qu'un Z local.

=> Algorithmes d'échantillonnage du champ : échantillonneur de Gibbs, algorithme de Metropolis.

Optimisation : Recuit simulé

• Distribution de Gibbs avec température

  
  

  $$P_T(X=x)=\frac{1}{Z(T)}\exp(-\frac{U(x)}{T})$$
  
  

     : P_T converge vers une loi uniforme sur .
    T = 0 : P_T est uniformément distribuée sur les minima globaux de U.

• L'algorithme du recuit simulé :

  T⁽⁰⁾ grande et x⁽⁰⁾ quelconque.

  Etape n : - simulation de x⁽ⁿ⁾ pour la loi de Gibbs d'énergie , à partir de x^(n-1),
                   - décroissance théorique de la température de sorte que :
  

  $$T^{(n)}>\frac{c}{\log (1+n)}$$
  
  

  Itérations jusqu'au critère d'arrêt.