Recuit Simulé

Recuit simulé

Introduction :

La méthode du recuit simulé tire son origine de la physique. Son principe de fonctionnement repose sur une imitation du phénomène du recuit physique. Ce processus est utilisé en métallurgie pour améliorer la qualité d’un solide, cherche son état d’énergie minimale qui correspond à une structure stable de ce métal. En partant d’une haute température ou le métal serait liquide, on refroidit le métal progressivement en tentant de trouver le meilleur équilibre thermodynamique.

Historique :

1953 : Expériences réalisées par Metropolis et Al pour simuler l’évolution du processus du recuit simulé.

1983-1985 : l’utilisation pour la résolution des problèmes d’optimisation combinatoire (krik patrick, cerny)

Le recuit simulé la première métaheuristique qui a été proposé.

Le recuit physique :

Revenons maintenant à la thermodynamique. La "recherche" par un système physique des états d'énergie les plus bas est l'analogue formel d'un processus d'optimisation combinatoire. A température nulle, le système évolue à partir d'une configuration vers la, ou les, configurations d'énergie les plus basses par une méthode de type gradient. Par conséquent, dans le cas d'un système frustré, la configuration atteinte est le plus souvent un état métastable, dont l'énergie est supérieure à celle du minimum absolu. Le système est en quelque sorte piégé dans ce minimum local (Fig. 9.1).

Figure 9.1 Un paysage d'énergie. Suivant la configuration initiale, indiquée par les flèches, la dynamique aboutit à température nulle dans l'un quelconque des minima relatifs, séparés par les barrières indiquées en pointillés. A température élevée, les processus probabilistes permettent au système de sauter les barrières séparant les vallées.

En revanche, à température non nulle, le caractère probabiliste des changements de configuration peut permettre au système de remonter la pente et de ressortir du bassin d'attraction d'un minimum relatif pour accéder à un autre bassin plus profond. Idéalement, pour se rapprocher du minimum, il faudrait que la température soit assez grande pour permettre au système de sauter les barrières et qu'elle soit assez faible pour qu'il soit malgré tout attiré vers le fond des vallées.

Envisageons alors une double dynamique : celle de la recherche des minima à température fixée, plus une dynamique de diminution de la température. Si l'on part d'une température élevée, toutes les configurations sont accessibles et le système n'a qu'une faible préférence pour les états de faible énergie. En diminuant progressivement la température, on permet au système de rechercher des bassins d'attraction relativement larges au début, tout en lui évitant d'être piégé par les attracteurs métastables. Le nombre des configurations accessibles dépend de la température; aux températures moyennes le système semble surtout sensible aux traits les plus grossiers du paysage dynamique. En diminuant lentement la température, on évite de piéger le système dans des vallées d'énergie élevée, pour l'envoyer vers les bassins les plus importants et les plus profonds, là où les baisses ultérieures de température le précipiteront vers les fonds.

Un tel mécanisme s'appelle un recuit, par analogie avec les cycles thermiques utilisés en métallurgie. En effet, lors du refroidissement d'un métal ou d'un alliage, on choisit la vitesse de décroissance de la température en fonction des qualités mécaniques du solide que l'on souhaite obtenir. L'acier des outils tranchants par exemple est trempé par un refroidissement rapide : cette opération donne un cristal très imparfait, dans un état métastable donc, mais très dur. Par contre, si l'on souhaite obtenir un matériau malléable et peu cassant, il faut réaliser une structure cristalline la plus parfaite possible, d'où la nécessité d'opérer des recuits à des températures intermédiaires, de manière à éliminer les défauts du cristal. Les diagrammes suivants permettent de suivre ces phénomènes dans le cas d'un ferromagnétique (Fig. 9.2).

Figure 9.2 Configurations de basse énergie d'un ferromagnétique. A gauche figure la configuration d'énergie minimum, et à droite une configuration métastable, susceptible d'évoluer à température non nulle vers la configuration de gauche.

La structure homogène, à gauche de la figure 9.2, est obtenue à température nulle dans le cas d'un recuit : elle correspond bien à une configuration d'énergie minimum. La structure de droite est obtenue après une trempe. On y voit coexister des domaines d'aimantation positive et des domaines d'aimantation négative: si les domaines étaient isolés, chacun d'eux correspondrait à un minimum d'énergie. Mais les lignes de frontière ajoutent une contribution positive à l'énergie. Leur disparition nécessiterait le retournement simultané d'un nombre important de spins, donc un accroissement momentané de l'énergie du système, que la température faible rend très peu probable. Le système est bloqué dans un état métastable.

Les propriétés thermiques des verres sont très liées à l'existence de leurs multiples attracteurs. Si le verre est refroidi rapidement, la configuration des atomes est métastable; elle est obtenue pour une température relativement élevée que nous noterons Tr. Par contre si on recuit le matériau, les changements de configuration entre états métastables ont le temps de se produire et le système continue à évoluer, même pour des températures inférieures à Tr. La température de transition est donc plus faible pour les refroidissements les plus longs. Dans le cas de la silice, on peut obtenir, suivant la vitesse de refroidissement, soit une forme amorphe appelée communément silice, soit un cristal de quartz.

Algorithmes du recuit simulé

Par réduction continue : la température est modifiée à chaque itération

• Engendrer une configuration initiale S0 de S ; S := S0

• Initialiser T en fonction du schéma de refroissement

•

...