Recuit simulé

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 génère successivement des configurations à partir d’une solution initiale R0 et d’une température initiale T0 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 :

  1. Prendre une solution initiale R=R0 et une température initiale T=T0. L’état initiale est comme pour les méthodes exactes, obtenu par une heuristique (descente ou glouton).
  2. Générer une solution aléatoire R(i+1) dans le voisinage de la solution courante :
    1. comparer R(i+1) avec Ri selon la règle de Metropolis
    2. répéter jusqu’à rencontrer une solution stable (ou après un certain nombre d’itérations)
  3. Décroitre la température T jusqu’à une température seuil Tmin, ou avoir une solution stable.
 R0
T0
tant que T > Tmin et E > emax
   R(i+1) = voisin(Ri)
   si E(R(i+1)) < E(Ri) ou aléatoire() < P(diff(E)/T) alors
      accepter R(i+1)
   màj T
retourne Rn

SA

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.

image7

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

img143

Publicités