5.3 Algorithme du recuit simulé
75
Cela conduit à un algorithme stochastique pour simuler μ ∞ appelé algorithme
du recuit simulé
6 , qui consiste à utiliser l’algorithme de Metropolis-Hastings
mais avec une température 1/β = 1/β t décroissante au cours du temps t. La
chaîne de Markov de Metropolis-Hastings (X t ) t∈N ainsi modifiée n’est plus
homogène en temps. Considérons par exemple le cas où α(u) = min(1, u)
pour tout u ∈ R, et où Q est tel que Q(x, y) = Q(y, x) pour tous x, y ∈ E.
La fonction d’acceptation-rejet dépend du temps et est donnée par
ρ t (x, y) = α
μ βt (y)
μ βt (x)
= α
e
−βt(H(y)−H(x))
= e
−βt max(0,H(y)−H(x)) .
Sachant que la chaîne (ou l’algorithme) se trouve en l’état x au temps t, on
simule une proposition y de loi Q(x, ·), qu’on accepte ssi U < ρ t (x, y) où U
est une variable aléatoire uniforme sur [0, 1] indépendante, c’est-à-dire avec
probabilité 1 si H(y) H(x) et probabilité e
−βt(H(y)−H(x)) sinon (vaut 0 si
1/β t = 0). L’algorithme explore le graphe de H, accepte toujours une transition qui abaisse l’énergie H et accepte une transition qui l’augmente avec une
probabilité décroissant vers zéro au fur et à mesure que la température baisse.
Contrairement à une méthode de type descente de gradient, le recuit simulé
peut «remonter la pente» et ainsi échapper, au début, aux minima locaux.
Il reste cependant à régler la température : un refroidissement trop brusque
peut piéger la trajectoire près d’un minimum local tandis qu’un refroidissement trop lent peut empêcher l’algorithme de se concentrer près de l’ensemble
M . Un résultat théorique assure que pour un schéma de décroissance de la
température 1/β t de la forme c/ log(t) quand t → ∞, la chaîne s’accumule
sur des points de M . Ce théorème remarquable est toutefois peu utile en pratique ! La performance de l’algorithme dépend beaucoup de la régularité du
graphe de H par rapport à la structure de voisinage de l’exploration.
Considérons à présent le problème du voyageur de commerce pour n villes
positionnées dans l’espace en v 1 , . . . , v n , qui consiste à trouver une tournée
de longueur minimale, c’est-à-dire une permutation x ∈ S n dans le groupe
symétrique S n qui minimise la fonction
x ∈ S n → H(x) :=
n
i=1
dist
v x(i) , v x(i+1)
où x(n + 1) := x(1).
La longueur d’une tournée joue le rôle d’énergie ici. Le cardinal de E = S n est
énorme : n!. À coût total fixé, on ne pourra qu’explorer une partie restreinte
F ⊂ E et retenir le minimum de H sur F comme approximation du minimum
de H sur E. La génération d’une partie F ⊂ E peut se faire de manière
déterministe
7 , ou de manière stochastique par exemple avec l’algorithme du
6. «Simulated annealing» en anglais.
7. L’algorithme (déterministe) de Steinhaus-Johnson-Trotter permet de lister les
éléments de Sn sans comparaison aux éléments déjà produits. Algébriquement, il
correspond à parcourir un graphe de Cayley de Sn, tandis que géométriquement, il
correspond à parcourir les sommets adjacents du polytope appelé permutaèdre.
75
Cela conduit à un algorithme stochastique pour simuler μ ∞ appelé algorithme
du recuit simulé
6 , qui consiste à utiliser l’algorithme de Metropolis-Hastings
mais avec une température 1/β = 1/β t décroissante au cours du temps t. La
chaîne de Markov de Metropolis-Hastings (X t ) t∈N ainsi modifiée n’est plus
homogène en temps. Considérons par exemple le cas où α(u) = min(1, u)
pour tout u ∈ R, et où Q est tel que Q(x, y) = Q(y, x) pour tous x, y ∈ E.
La fonction d’acceptation-rejet dépend du temps et est donnée par
ρ t (x, y) = α
μ βt (y)
μ βt (x)
= α
e
−βt(H(y)−H(x))
= e
−βt max(0,H(y)−H(x)) .
Sachant que la chaîne (ou l’algorithme) se trouve en l’état x au temps t, on
simule une proposition y de loi Q(x, ·), qu’on accepte ssi U < ρ t (x, y) où U
est une variable aléatoire uniforme sur [0, 1] indépendante, c’est-à-dire avec
probabilité 1 si H(y) H(x) et probabilité e
−βt(H(y)−H(x)) sinon (vaut 0 si
1/β t = 0). L’algorithme explore le graphe de H, accepte toujours une transition qui abaisse l’énergie H et accepte une transition qui l’augmente avec une
probabilité décroissant vers zéro au fur et à mesure que la température baisse.
Contrairement à une méthode de type descente de gradient, le recuit simulé
peut «remonter la pente» et ainsi échapper, au début, aux minima locaux.
Il reste cependant à régler la température : un refroidissement trop brusque
peut piéger la trajectoire près d’un minimum local tandis qu’un refroidissement trop lent peut empêcher l’algorithme de se concentrer près de l’ensemble
M . Un résultat théorique assure que pour un schéma de décroissance de la
température 1/β t de la forme c/ log(t) quand t → ∞, la chaîne s’accumule
sur des points de M . Ce théorème remarquable est toutefois peu utile en pratique ! La performance de l’algorithme dépend beaucoup de la régularité du
graphe de H par rapport à la structure de voisinage de l’exploration.
Considérons à présent le problème du voyageur de commerce pour n villes
positionnées dans l’espace en v 1 , . . . , v n , qui consiste à trouver une tournée
de longueur minimale, c’est-à-dire une permutation x ∈ S n dans le groupe
symétrique S n qui minimise la fonction
x ∈ S n → H(x) :=
n
i=1
dist
v x(i) , v x(i+1)
où x(n + 1) := x(1).
La longueur d’une tournée joue le rôle d’énergie ici. Le cardinal de E = S n est
énorme : n!. À coût total fixé, on ne pourra qu’explorer une partie restreinte
F ⊂ E et retenir le minimum de H sur F comme approximation du minimum
de H sur E. La génération d’une partie F ⊂ E peut se faire de manière
déterministe
7 , ou de manière stochastique par exemple avec l’algorithme du
6. «Simulated annealing» en anglais.
7. L’algorithme (déterministe) de Steinhaus-Johnson-Trotter permet de lister les
éléments de Sn sans comparaison aux éléments déjà produits. Algébriquement, il
correspond à parcourir un graphe de Cayley de Sn, tandis que géométriquement, il
correspond à parcourir les sommets adjacents du polytope appelé permutaèdre.