Recuit simulé

L'état initial peut être pris au hasard dans l'espace des états possibles. À cet état correspond une énergie initiale ${\displaystyle E=E_{0}}$. Cette énergie est calculée en fonction du critère que l'on cherche à optimiser. Une température initiale ${\displaystyle T=T_{0}}$ élevée est également choisie de façon totalement arbitraire indépendamment de la loi de décroissance utilisée.

À chaque itération de l'algorithme une modification élémentaire de l'état est effectuée. Cette modification entraîne une variation ${\displaystyle \Delta _{E}}$ de l'énergie du système (toujours calculée à partir du critère que l'on cherche à optimiser). Si cette variation est négative (c'est-à-dire qu'elle fait baisser l'énergie du système), elle est appliquée à l'état courant. Sinon, elle est acceptée avec une probabilité ${\displaystyle e^{-{\frac {\Delta _{E}}{T}}}}$. Ce choix de l'exponentielle pour la probabilité s'appelle règle de Metropolis.

On itère ensuite selon ce procédé en gardant la température constante.

Deux approches sont possibles quant à la variation de la température :

1. itérer en gardant la température constante. Lorsque le système a atteint un équilibre thermodynamique (au bout d'un certain nombre de changements), on diminue la température du système. On parle alors de paliers de température ;
2. faire baisser la température de façon continue. On peut imaginer toutes sortes de lois de décroissance, la plus courante étant ${\displaystyle T_{i+1}=\lambda T_{i}}$ avec ${\displaystyle \lambda <1}$ (on choisit assez couramment ${\displaystyle \lambda =0.99}$).

Dans les deux cas, si la température a atteint un seuil assez bas fixé au préalable ou que le système devient figé, l'algorithme s'arrête.

La température joue un rôle important. À haute température, le système est libre de se déplacer dans l'espace des états (${\displaystyle e^{-{\frac {\Delta _{E}}{T}}}}$ proche de 1) en choisissant des états ne minimisant pas forcément l'énergie du système. À basse température, les modifications baissant l'énergie du système sont choisies, mais d'autres peuvent être acceptées, empêchant ainsi l'algorithme de tomber dans un minimum local.

Le pseudo-code suivant met en œuvre le recuit simulé tel que décrit plus haut, en commençant à l'état s0 et continuant jusqu'à un maximum de kmax étapes ou jusqu'à ce qu'un état ayant pour énergie emax ou moins soit trouvé. E est une fonction calculant l'énergie de l'état s. L'appel voisin(s) génère un état voisin aléatoire d'un état s. L'appel aléatoire() renvoie une valeur aléatoire dans l'intervalle [0, 1]. L'appel temp(r) renvoie la température à utiliser selon la fraction r du temps total déjà dépensé, et P est une fonction de probabilité dépendant de la variation d'énergie et de la température.

s := s0
e := E(s)
k := 0
tant que k < kmax et e > emax
  sn := voisin(s)
  en := E(sn)
  si en < e ou aléatoire() < P(en - e, temp(k/kmax)) alors
    s := sn; e := en
  k := k + 1
retourne s

En pratique, dans le cas où le nombre d'itération est limité avec le kmax, on peut aussi considérer que s est un état optimal local et introduire une variable g pour conserver l'état optimal global, m pour la meilleure énergie avec initialement g := s0. Ainsi en fin d'algorithme, on retrouve l'état d'energie la plus basse plutôt qu'un état intermédiaire obtenu après un sursaut[3].

s := s0
g := s0
e := E(s)
m := E(g)
k := 0
tant que k < kmax et e > emax
  sn := voisin(s)
  en := E(sn)
  si en < e ou aléatoire() < P(en - e, temp(k/kmax)) alors
    s := sn; e := en
  si e < m alors
      g := s; m := e;
  k := k + 1
retourne g

Dans l'image ci-dessous, la droite verticale bleue représente les valeurs successives de g, la droite rouge représente les valeurs de s et la droite noire les valeurs de sn.

Les principaux inconvénients du recuit simulé résident dans le choix des nombreux paramètres, tels que la température initiale, la loi de décroissance de la température, les critères d'arrêt ou la longueur des paliers de température. Ces paramètres sont souvent choisis de manière empirique.