# Recuit simulé

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant la science.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

Le recuit simulé est une méthode empirique (métaheuristique) inspirée d'un processus utilisé en métallurgie. On alterne dans cette dernière des cycles de refroidissement lent et de réchauffage (recuit) qui ont pour effet de minimiser l'énergie du matériau. Cette méthode est transposée en optimisation pour trouver les extrema d'une fonction.

Elle a été mise au point par trois chercheurs de la société IBM, S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi en 1983, et indépendamment par V. Černy en 1985.

La méthode vient du constat que le refroidissement naturel de certains métaux ne permet pas aux atomes de se placer dans la configuration la plus solide. La configuration la plus stable est atteinte en maîtrisant le refroidissement et en le ralentissant par un apport de chaleur externe, ou bien par une isolation.

## Recuit réel[modifier | modifier le code]

Article détaillé : recuit.

La description des phénomènes physiques et quantiques liés au processus de recuit s'appuie sur la statistique de Maxwell-Boltzmann.

Recuit simulé cherchant un maximum. L'objectif ici est de trouver le plus haut point; seulement, ce n'est pas suffisant d'utiliser un simple algorithme de hill climbing (en) car il y a de nombreux maximum locaux. En refroidissant le matériau lentement, le maximum global peut être trouvé.

## Déroulement du processus[modifier | modifier le code]

Le recuit simulé s'appuie sur l'algorithme de Metropolis-Hastings, qui permet de décrire l'évolution d'un système thermodynamique. Par analogie avec le processus physique, la fonction à minimiser deviendra l'énergie E {\displaystyle E} du système. On introduit également un paramètre fictif, la température T {\displaystyle T} du système.

Partant d'un état donné du système, en le modifiant, on obtient un autre état. Soit celui-ci améliore le critère que l'on cherche à optimiser, on dit alors qu'on a fait baisser l'énergie du système, soit celui-ci le dégrade. Si on accepte un état améliorant le critère, on tend ainsi à chercher l'optimum dans le voisinage de l'état de départ. L'acceptation d'un « mauvais » état permet alors d'explorer une plus grande partie de l'espace des états et tend à éviter de s'enfermer trop vite dans la recherche d'un optimum local.

### État initial de l'algorithme[modifier | modifier le code]

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

### Itérations de l'algorithme[modifier | modifier le code]

À chaque itération de l'algorithme une modification élémentaire de l'état est effectuée. Cette modification entraîne une variation Δ E {\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é e − Δ E T {\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.

### Programme de recuit[modifier | modifier le code]

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

1. Pour la première, on itère 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. La seconde approche fait baisser la température de façon continue. On peut imaginer toute sorte de loi de décroissance, la plus courante étant T i + 1 = λ T i {\displaystyle T_{i+1}=\lambda T_{i}} avec λ < 1 {\displaystyle \lambda <1} (assez couramment λ = 0.99 {\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 ( e − Δ E T {\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.

### Pseudo-code[modifier | modifier le code]

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.[1]

    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.

### Inconvénients[modifier | modifier le code]

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.

## Étude théorique[modifier | modifier le code]

Des études théoriques du recuit simulé ont pu montrer que sous certaines conditions, l'algorithme du recuit convergeait vers un optimum global[2]. Ce résultat est important car il nous assure, contrairement à d'autres métaheuristiques, que le recuit simulé peut trouver un état correspondant à la meilleure solution, si on le laisse chercher indéfiniment.

Les preuves de convergence reposent sur le principe de construction de l'algorithme du recuit simulé :

- Sous réserve qu'elle respecte la condition de Doeblin[3] une chaîne de Markov admet une unique distribution stationnaire
- L'algorithme de Metropolis-Hastings permet, étant donnée une distribution de probabilité, de construire une chaîne de Markov dont la distribution stationnaire est cette distribution de probabilité.

Par ailleurs, les mesures de Gibbs, très utilisées en physique statistique, sont une famille de mesures dépendant d'un paramètre température de telle sorte que lorsque la température tend vers 0, la mesure converge vers un Dirac en un point donné (état d'énergie minimale).

En composant les deux, on obtient une chaîne de Markov qui converge vers une mesure invariante qui évolue dans le même temps vers une mesure désignant l'optimum recherché (au sens de la fonction d'énergie associée à la mesure de Gibbs).

Une analyse fine des vitesses de convergence et des écarts asymptotiques permet alors d'aboutir à diverses conditions de convergence, dont celle de Hajek : si le schéma de température utilisé vérifie T n ≥ K ln ⁡ n {\displaystyle T_{n}\geq {\frac {K}{\ln {n}}}} , alors l'algorithme converge en probabilité vers l'optimum global.

En pratique, ce schéma converge beaucoup trop lentement et l'on préfère des températures à décroissance linéaire ou quadratique, quitte à n'obtenir qu'un minimum local (qu'on espère proche du minimum global).

## Applications[modifier | modifier le code]

Comme pour toute métaheuristique, la méthode trouve son application dans de nombreux domaines dans lesquels on a à résoudre des problèmes d'optimisation difficile. On peut citer entre autres la conception des circuits électroniques (placement-routage) ou l'organisation de réseaux informatiques. Cet algorithme a été utilisé dès la fin des années 1980 pour déterminer l’architecture optimale de grands réseaux télématiques[4].

## Exemple sous Mathematica[modifier | modifier le code]

Cet article doit être recyclé (mars 2017).

Une réorganisation et une clarification du contenu paraissent nécessaires. Améliorez-le, discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.

       F[X_] := Abs[X[[1]]] + Abs[X[[2]]];
        g[T_] := N[T^0.99];

            Recuit[F_, g_,Xi_,Ti_,Tf_,Ampli_,MaxTconst_,itermax_] := Module[{T,Xopt,iter=1,DF,p,L,X,compteur},
               X = Xi; T = Ti; L = {Xi}; Xopt = X;
             While [T > Tf && iter < itermax,
              compteur = 1;
               While[compteur < MaxTconst,
                 Y = X + Table[Ampli*Random[Real, {-1, 1}], {i, 1, Length[X]}];
                 DF = F[Y] - F[X];
                  If[DF < 0, X = Y; AppendTo[L, X];
                    If[F[X] < F[Xopt], Xopt = X],
                    p = Random[];
                  If [p ≤ Exp[-DF/T], X = Y; AppendTo[L, X]];
                  ];
                  compteur = compteur + 1;
                  ];
                T = g[T];
                iter = iter + 1;
                ];
              Return[L]
              ];

        resR = Recuit[F, g, {2, 3}, 10, 1, 0.5, 1.5, 1000];
        ListPlot[resR, Joined -> True];

## Notes et références[modifier | modifier le code]

1. ↑ Virginie MATHIVET, L'Intelligence Artificielle pour les développeurs, édition eni, décembre 2017, 521 p. (ISBN 978-2-409-01140-5, lire en ligne [archive]), p. 10.3.5 Métaheuristique d'optimisation. Implémentation du Recuit simulé
2. ↑ Aarts, E. H. L., and v. Laarhoven (1985), Statistical cooling: A general approach to combinatorial optimization problems, Philips J. Res., 40(4), 193-226.
3. ↑ Cf. J. Lacroix, « Chaînes de Markov et Processus de Poisson » [archive], sur Université Pierre et Marie Curie DEA Probabilités et Applications, 2001-2002) (consulté le 6 mars 2017).
4. ↑ Cf. Jean-Luc Lutton et Ernesto Bonomi, « Le recuit simulé », Pour la science, no 129,‎ juillet 1988, p. 68- 77.

## Voir aussi[modifier | modifier le code]

- Retour sur trace

## Liens externes[modifier | modifier le code]

- recuit simulé [archive] (Applet java)
- recuit simulé pour le voyageur de commerce, application en ligne [archive]

- Portail de l'informatique théorique

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Recuit_simulé&oldid=146924416 ».
Catégorie :

- Métaheuristique

[+]
Catégories cachées :

- Wikipédia:ébauche science
- Article à recycler/Liste complète
- Article à recycler
- Portail:Informatique théorique/Articles liés
- Portail:Informatique/Articles liés
- Projet:Mathématiques/Articles