Principe du recuit simulé

Le cadre de présentation le plus approprié est de nouveau celui de la mécanique statistique [#!LaaAar!#]. Ainsi, on s'intéresse à un système qui vit sur un graphe, , au plus dénombrable. Ce graphe indexe un champ de Markov , avec un espace compact. À l'aide des potentiels d'interaction on définit un hamiltonien qui à chaque configuration, , associera son énergie (ou son coût) .

Le problème que l'on se propose de résoudre est de trouver les configurations qui minimisent .

On serait tenté d'utiliser un des algorithmes standard de minimisation (la méthode du gradient par exemple) ; ce qui risque de se passer cependant, quand est grand, est que la méthode du gradient reste piégée dans un minimum local profond sans jamais pouvoir en sortir.

Le remède consiste à imiter une procédure utilisée depuis des millénaires^10.1par les métallurgistes qui, pour obtenir un alliage exempt des défauts, chauffent d'abord à blanc leur morceau de métal et ensuite laissent l'alliage se refroidir très lentement (recuit).

En termes mathématiques, au lieu de chercher directement l'ensemble , on utilise une description statistique pour chercher une spécification de Gibbs

pour tout ensemble mesurable des configurations. En refroidissant lentement on espère que va converger faiblement vers la probabilité uniforme sur . La formulation exacte [#!AniFed!#,#!Aze!#] est la suivante. On fixe une suite décroissante de températures (ou de manière équivalente une suite croissante de ) qui sera le programme du refroidissement. Pour chaque , on construit comme d'habitude la matrice stochastique , admettant comme vecteur propre gauche la probabilité

Pour ce faire on peut utiliser l'un des algorithmes étudiés dans le cas homogène (Metropolis, Kawasaki). La chaîne de Markov que l'on simule est une chaîne inhomogène de matrice de transition à l'étape donnée par .

Avant de montrer que cette chaîne converge effectivement, quand , à la probabilité uniforme sur , on a besoin de certaines notions. On se souvient d'abord que le point de départ pour la construction de est le choix d'une matrice stochastique des tentatives définie sur chaque site . À l'aide des matrices sur les sites et selon le mode de balayage suivi on construit la matrice des tentatives (égale à ou à selon le cas).

Pour chaque , on définit les états accessibles comme étant l'ensemble des configurations susceptibles d'être proposées par .

Une configuration, , est un minimum local de si pour tout . Elle est un minimum global de si pour tout . On note et les ensembles des minima locaux et globaux.

Deux configurations et de communiquent à hauteur , on note alors , si ou bien et ou alors il existe une suite avec telle que , , et pour tout .

La profondeur d'un minimum local est définie par

De manière évidente, si alors .

Voir [#!Haj!#].

Ce théorème garantit qu'un programme de refroidissement tel que

convergera effectivement à une configuration minimisante si, et seulement si, . Ce résultat se trouve complété par le théorème suivant, dû à Chiang et Chow [#!ChiCho!#], qui donne les conditions sous lesquelles la chaîne de Markov charge positivement chaque minimum global de .

La méthode du recuit peut aussi s'étendre au cas d'espace d'états continu [#!Haa_SPMgt__SPMgt__SPMgt_!#].

Les théorèmes précédents imposent des limites sur la vitesse de refroidissement pour que l'algorithme de recuit converge aux minima globaux de l'hamiltonien. Cependant, les limites imposées sont draconiennes (programme logarithmique) et trés coûteuses en temps de calcul. Les praticiens de la simulation, très souvent, transgressent ces bornes en se servant, sciemment, de programmes de refroidissement plus rapides (linéaire ou même exponentiel). Quoique les théorèmes de convergence ne s'appliquent plus à ces situations, très souvent, d'un point de vue pratique, les résultats obtenus restent encore acceptables [#!Cat!#,#!Def!#].

Un autre point important pour la convergence est le choix de la température initiale, , qui doit être choisie suffisamment élévée ( assez petit) pour permettre au système de changer aisément de vallée pendant les prémières étapes de la simulation. Dans la pratique, la détermination de se fait en imposant qu'en début de simulation, il y ait une probabilité d'au moins 0,8 pour qu'une transition vers n'importe quelle partie de l'espace de configurations soit acceptée [#!Laa_SPMgt__SPMgt__SPMgt_!#].