Recuit simulé

Recuit simulé

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. Cerny 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 contrôlant le refroidissement et en le ralentissant par un apport de chaleur externe.

Sommaire

Recuit réel

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 Boltzmann.

Déroulement du processus

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 du système. On introduit également un paramètre fictif, la température T du système.

Partant d'une solution donnée, en la modifiant, on en obtient une seconde. Soit celle-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 celle-ci le dégrade. Si on accepte une solution améliorant le critère, on tend ainsi à chercher l'optimum dans le voisinage de la solution de départ. L'acceptation d'une « mauvaise » solution permet alors d'explorer une plus grande partie de l'espace de solution et tend à éviter de s'enfermer trop vite dans la recherche d'un optimum local.

État initial de l'algorithme

La solution initiale peut être prise au hasard dans l'espace des solutions possibles. À cette solution correspond une énergie initiale E = E0. Cette énergie est calculée en fonction du critère que l'on cherche à optimiser. Une température initiale T = T0 é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

À chaque itération de l'algorithme une modification élémentaire de la solution est effectuée. Cette modification entraîne une variation Δ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 à la solution courante. Sinon, elle est acceptée avec une probabilité 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

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 Ti + 1 = λTi avec λ < 1 (assez couramment λ = 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 solutions (e^{-\frac{\Delta_E}{T}} proche de 1) en choisissant des solutions 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

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é. 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é.

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

Inconvénients

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

Des études théoriques du recuit simulé ont pu montrer que sous certaines conditions, l'algorithme du recuit convergeait vers un optimum global[1]. Ce résultat est important car il nous assure, contrairement à d'autres métaheuristiques, que le recuit simulé peut trouver 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é :

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 asymptotique permet alors d'aboutir à diverses conditions de convergence, dont celle de Hajek : si le schéma de température utilisé vérifie 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

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.

Exemple sous Mathematica

   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, PlotJoined -> True];

Notes et références

  1. Aarts, E. H. L., and v. Laarhoven (1985), Statistical cooling: A general approach to combinatorial optimization problems, Philips J. Res., 40(4), 193-226.
  2. http://www.proba.jussieu.fr/cours/dea/telehtml/node37.html

Voir aussi

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recuit simulé de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Recuit simule — Recuit simulé Le recuit simulé est une métaheuristique inspirée d un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l énergie du matériau. Elle est… …   Wikipédia en Français

  • recuit simulé — ● loc. m. ►ALGO Nom d un algorithme classique permettant d obtenir rapidement une valeur approchée d une solution d un problème NP complet (e.g. problème du voyageur de commerce). L idée est que si on a un problème contenant beaucoup de… …   Dictionnaire d'informatique francophone

  • Recuit — Le recuit d une pièce métallique est un procédé correspondant à un cycle de chauffage, maintien en température puis refroidissement permettant de modifier les caractéristiques d un métal. À l occasion d un recuit, les grains (mono cristaux) du… …   Wikipédia en Français

  • Détermination d'une structure cristalline — La détermination d une structure cristalline consiste, de manière générale, à déterminer, pour un cristal de structure inconnue, les paramètres de sa maille conventionnelle, son réseau de Bravais, son groupe d espace et la position des atomes… …   Wikipédia en Français

  • Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… …   Wikipédia en Français

  • Métaheuristiques — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Optimisation (mathématiques) — L optimisation est une branche des mathématiques, cherchant à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à déterminer le meilleur élément d un ensemble, au sens d un critère quantitatif donné. Ce mot vient …   Wikipédia en Français

  • PROGRAMMATION MATHÉMATIQUE — La programmation mathématique consiste à chercher, parmi tous les points x vérifiant certaines conditions du type: celui ou ceux qui rendent minimal (ou maximal, suivant le cas) un certain critère f (x ), qui sera interprété comme un gain dans le …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”