Recuit simulé

Contenus

Le recuit est une méthode métallurgique permettant d’obtenir des solides cristallisés en évitant l’état de verre. Une fois le métal fondu, la température est baissée progressivement jusqu’à atteindre un état solide. Pour enlever tous les défauts, le métal est réchauffé puis refroidi, par paliers décroissant de température, jusqu’à atteindre un état stable.

Ce système de palier décroissant à donné naissance à l’algorithme de Metropolis de 1953 puis au recuit simulé par IBM en 1983.

Présentation de l’algorithme

L’algorithme du recuit simulé, ou simulated annealing pour les anglophones, est donc l’adaptation algorithmique du processus du recuit.

Le but est d’atteindre un état stable de la fonction objectif – un optimum local ou global – à partir d’une solution aléatoire. Cet état est atteint par paliers, où l’acceptation d’une mutation se fait en fonction de la « température » du palier.

L’algorithme de recuit simulé génère successivement des configurations à partir d’une solution initiale R₀ et d’une température initiale T₀ diminuant à chaque itération, jusqu’à obtenir une configuration stable. La probabilité d’accepter une nouvelle configuration est (règle de Metropolis) :

1 si la configuration améliore la fonction objectif;
exp(diff(E)/T) avec diff(E) la différence énergétique et T la température; la différence énergétique est une fonction en interne, dépendant de la fonction objectif.

Déroulement de l’algorithme

L’algorithme du recuit est le suivant :

Prendre une solution initiale R=R₀ et une température initiale T=T₀. L’état initiale est comme pour les méthodes exactes, obtenu par une heuristique (descente ou glouton).
Générer une solution aléatoire R_(i+1) dans le voisinage de la solution courante :
1. comparer R_(i+1) avec R_i selon la règle de Metropolis
2. répéter jusqu’à rencontrer une solution stable (ou après un certain nombre d’itérations)
Décroitre la température T jusqu’à une température seuil T_min, ou avoir une solution stable.

 R₀
T₀
tant que T > T_min et E > e_max
   R_(i+1) = voisin(R_i)
   si E(R_(i+1)) < E(R_i) ou aléatoire() < P(diff(E)/T) alors
      accepter R_(i+1)
   màj T
retourne R_n

Puisque T est grand au début, beaucoup de solutions dégradant la solution courante peuvent être choisies. Cela permet de s’échapper d’un optimum local. La figure suivante présente la valeur de la fonction objectif en fonction du vecteur de paramètre X. La température permet donc de « sauter » des zones moins « bonnes » pour sortir d’une « vallée ». Les billes et signaux de la figure suivante montrent jusqu’à quelle hauteur les billes peuvent « sauter », c’est-à-dire la tolérance de variation négative de la fonction objectif dans l’obtention d’une nouvelle solution.

Si la température est basse, il est plus difficile de s’échapper d’un optimum local :