Recuit Simulé

IDLabs

Recuit Simulé

 

 

 

 

SOMMAIRE

 

I. Les ancêtres du recuit simulé

A. Nicholas Constantine Metropolis
B. Le recuit

II. Le recuit simulé

A. Principe
B. L’algorithme du recuit simulé
C. L’exemple du voyageur de commerce

 

 

 

I. Les ancêtres du recuit simulé

A. Nicholas Constantine Metropolis

Né le 11 juin 1915 à Chicago, il entreprend et réussit avec brio un doctorat de physique. En avril 1943, Oppenheimer, physicien et directeur scientifique du Projet Manhattan, l’y recrute pour ses travaux sur les réacteurs nucléaires. Il mène alors des recherches sur les réactions des matériaux placés à de très hautes températures et pressions. Il passe aussi une grande partie de son temps à étudier les ordinateurs.

Nicholas Metropolis

A la fin de la Seconde Guerre Mondiale, il se met à diriger un groupe de chercheurs pour développer d’une part la méthode de Monte-Carlo, basée sur les jeux de hasard de Monte-Carlo, et d’autre part, le premier ordinateur à faire tourner une simulation de problème physique : le MANIAC. Ces deux recherches permirent de nombreuses avancées dans un grand nombre de domaines, le MANIAC dans la simulation informatique et la méthode de Monte-Carlo dans des domaines comme la physique quantique aux simulations sociales en passant par les automates cellulaires. Il écrit alors un article sur cette méthode avec l’aide d’Ulam en 1949. Grace à cette méthode, la physique statique a l’occasion de faire un bond en avant. En effet, auparavant, il fallait analyser toutes les situations possibles et en tirer des conclusions après avoir fait tous les calculs voulus sur ces dernières. La méthode de Monte-Carlo inverse alors absolument tout : les configurations sont tirées par la méthode elle-même de façon purement aléatoire, la méthode oubliant complètement les états précédents pour ne pas être affectée : ce principe est une chaine de Markov. Le but est d’avoir une loi de transition et que seul l’état présent est influencé par cette loi pour donner l’état futur, sans jamais prendre en compte les états voisins. Par la suite, la méthode de Monte-Carlo va tirer des valeurs aléatoires et calculer un rapport de probabilité entre l’état actuel et l’état calculé. S’il est supérieur à 1, l’état est accepté, sinon un autre tirage aléatoire est réalisé avec pour probabilité de 1 - le rapport calculé. Cela laisse une possibilité d’avancer même dans des cas qui de base auraient été acceptés.

Ces recherches ont réalisé de très grandes contributions dans le domaine du recuit simulé, recherches créditées à son nom même si la partie théorique a été principalement développée par Marshall Rosenbluth, reconnu seulement quelques années plus tard.

En plus d’être le premier employé du Los Alamos National Labotary a recevoir le titre Emeritus, il reçoit l’honneur de voir un prix en son nom se créer. Il est mort le 17 octobre 1999 à Los Alamos, alors âgé de 84 ans.

 

B. Le recuit

En métallurgie, il est notable que la déformation des matériaux à tendance à les modifier de l’intérieur. En effet, les matériaux solides sont constitués d’un schéma précis d’atomes formant un réseau, parfois non linéaire si le métal n’est pas pur. Lors de la chauffe et de la modification du matériau, ces atomes bougent, ces schémas cassent. Lorsque le matériau se refroidit, les atomes perdent leur énergie et se stabilisent, mais parfois dans une position où les schémas ne sont plus les bons. Cet état n’est pas « équilibré », comme un nœud de tension. Ces problèmes peuvent fragiliser le matériau voire lui faire perdre certaines propriétés.

     Le seul moyen pour redonner au matériau ses particularités est le recuit. Le matériau est alors chauffé de base à une haute température en général entre 500°C et 900°C. Par la suite il faut contrôler la descente de température. En perdant de l’énergie, les atomes vont ralentir petit à petit jusqu’à s’arrêter. Malheureusement, ils ne reviennent pas forcément à leur emplacement initial. Lorsqu’un atome se fige dans un état non adéquat et forme un nœud de tension, il faut réchauffer le métal pour faire atteindre au système un état d’équilibre. Une fois celui-ci atteint, il est possible de faire rebaisser la température du matériau. C’est en fonctionnant ainsi, par pallier, qu’il est possible de faire atteindre au système un état à froid quasiment exempte de défauts. De cette manière, le matériau aura une plus grande “souplesse” (les forces nécessaires pour le faire céder seront plus élevées, cela ne veut pas dire qu’il deviendra pour autant élastique) et il aura moins de chances de se briser suite à une pression sur un endroit sensible. Le recuit est très utilisé dans les domaines nécessitant des composants proches de la perfection sur le plan de la structure atomique comme la micro-électronique. Il est même possible de réparer certains semi-conducteurs avec un recuit

 

II. Le recuit simulé

A. Le principe

Contrairement à ce que l’on pourrait penser, le recuit simulé tire sa méthode du recuit, mais il est appliqué dans des cas complètement autre que la métallurgie, même s’il peut tout de même y être utilisé.

L’analogie est ici faite avec une colline. Le principe est simple : notre balle doit trouver l’endroit le plus bas. Si une énergie fournit une vitesse à la balle, elle a de grandes chances de tombers sur le côté. Cependant, elle peut très bien se coincer dans une des cuvettes sur les flancs des autres montagnes plutôt que d’atteindre le bas de la chaine.

Dans ce cas-là, il est notable que le système sera persuadé qu’il a atteint le minimum. Cependant, ce minimum est appelé le minimum local. Cependant, sans aide, la balle ne remontera jamais la pente pour arriver soit dans un autre minimum local, soit dans le vrai minimum dit global. Il faudrait alors, soit ne pas tomber dans un minimum local, soit arriver à en sortir. Dans certains cas, il est possible de les calculer avec par exemple les dérivées des fonctions. A partir de ses valeurs, il est possible de définir en quel point la fonction de départ est à son maximum ou minimum. Cependant, cela n’est vrai que dans le domaine d’application de la dérivée, et tout dépend aussi de l’ensemble utilisé.

Si le calcul simple est obsolète, il faut soit l’améliorer (ces méthodes ayant non seulement des limites mais aussi une difficulté beaucoup plus haute) soit utiliser des fonctions stochastiques (du grec stokhastikos et qui signifie des fonctions aléatoires). On va assembler le principe du recuit avec ces fonctions stochastiques de façon à pouvoir parcourir un maximum de terrain dépendant des voisins de l’état actuel. Quelle que soit la situation, il faut la voir comme une fonction possédant deux caractéristiques : la température et l’énergie du système. Le but : réduire l’énergie au maximum au fur et à mesure que la température baisse. Le but est donc d’avoir pour chaque température l’énergie la plus faible en cherchant dans le plus d’état possible. Quand elle trouve un état où l’énergie diminue, elle le garde, quand elle augmente, elle lance une fonction stochastique pour laisser une chance à l’état de remonter. Plus l’augmentation est grande, plus la probabilité qu’elle soit acceptée est faible. Quand la température est à son minimum, la probabilité est systématiquement de zéro.

La grande difficulté de cette méthode est surtout de “matérialiser le problème”. Dans le cas du voyageur de commerce qui sera traité par la suite, qu’est censé représenter l’énergie et la température ? A dire vrai, l’énergie est la donnée ayant pour but d’être minimisée alors que la température n’a souvent aucune réalité physique.

 

B. L'algorithme

Il faut entrer plusieurs paramètres dans l’algorithme de recuit simulé. Les plus importants sont évidemment l’énergie d’un état que l’on appellerait S0. La température de base sera alors nommée T0. L’énergie du système sera alors originalement nommée E0. La première étape est donc d’engendrer un état voisin à notre état S. Cet état est généré aléatoirement, pour laisser une chance à tous les états possibles. On obtient alors un état Sn+1 si on considère que n est le numéro de notre état actuel. Cet état est d’énergie En+1. Si En+1 est inférieur à En alors le nouvel état (Sn+1) est accepté et prend la place de l’état actuel.

Cependant, comme dit précédemment, il faut laisser une chance à l’énergie de remonter, dans le cas où l’on serait dans un minimum local. Pour cela, on utilise le une loi de probabilité trouvée

par Boltzmann qui déclare que la probabilité de trouver un système dans un certain état d’énergie est –(E/T). De cette manière, les plus hauts états d’énergie ont de faibles chances d’être acceptés, plus faibles que ceux de basses énergies, mais tout de même une chance.

De plus, quand la température est haute, les probabilités sont grandes, permettant au système d’adopter presque toutes les configurations trouvées, voire toutes quand la température tend vers l’infini. Il est d’ailleurs nécessaire que ce paramètre soit placé de manière à être extrêmement haut au début de l’algorithme. De cette manière, le système parcourra au début de très grandes régions puis, au fur et à mesure que la température baissera, l’amplitude elle aussi diminuera. A la fin, quand le système sera “froid” (il ne faut pas perdre à l’idée que le recuit simulé est une méthode d’optimisation, la chaleur n’a donc aucune réalité physique.), seule la diminution d’énergie sera acceptée, comme une pente permanente. Cela évite aussi que le système reparte en permanence à zéro et lui ajoute une sorte de précision.

La dernière étape est l’une des plus complexes : il faut définir comment va baisser la température.

Avant cela, il est utile de préciser que le recuit simulé est avant tout une méthode fortement empirique : Que ce soit les critères de départ, ceux d’arrivée ou de baisse de température, aucun n’est défini par la méthode. Il convient à l’utilisateur de les définir. La situation, le problème donné et les précédentes expérimentations sont les seuls moyens de les définir.

La baisse progressive de la température, nommée “Schéma de refroidissement”, peut être réalisée de plusieurs manières : la faire baisser à chaque itération, choisir une valeur fixe (représentatif de l’algorithme de Metropolis de base) ou utiliser un système de palier. Dans ce cas-là, plusieurs possibilités peuvent être réalisées encore : faire un nombre d’itérations par pallier fixe, changer de pallier quand le système commencer à stagner voire même des schémas beaucoup plus complexes.

L’un des plus courants et le système de pallier changeant lorsque l’évolution stagne : on y met un compteur d’itération et un taux d’acceptation. Quand le compteur atteint le maximum défini, selon le taux et les critères voulu, le pallier recommence ou la température baisse.

Encore une fois, même lorsque le Schéma de refroidissement est défini, il faut encore prévoir quel sera le taux de baisse de la température, ce dernier étant choisi de manière empirique. Il est même possible de donner une chance à la température de remonter, à la manière des états d’énergie.

 

C. L'exemple du voyageur de commerce

Un voyageur de commerce doit se rendre dans plusieurs villes pour rencontrer ses clients. On considère ici que seule la distance entre les villes importe, et il se trouve qu’il essaye de la minimiser. Appelons D la distance totale et n le nombre de villes. d(v;v2) sera la distance entre la ville 1 et la ville 2. Dans ce cas-là D est la somme de tous les d soit d(v;v2) + d(v;v3) + … + d(vn-1 ;vn) + d(v;v1) puisqu’il faut que le voyageur de commerce rentre chez lui. Le nombre de parcours possible devient rapidement grand, et peut-être assimilé à la factorielle de n. Et si la factorielle de 4 vaut 24, celle de 5 vaut 120 et les valeurs continuent d’augmenter de manière exponentielle (à partir de 10 villes, le nombre de possibilités dépasse le million). Alors si ce voyageur devait passer dans chaque capitale européenne, soit 28 villes, il y aurait 300 000 milliards de milliards de possibilités. Le voyageur peut toujours essayer de chercher à la main laquelle est la meilleure, mais il risque de mourir avant.

L’énergie globale du système est alors associée à la distance totale D et l’énergie d’un état du système est la distance entre deux villes d. On voit bien ici que la température n’est encore une fois qu’un paramètre invisible, n’ayant aucune existence dans le problème malgré le fait qu’elle soit nécessaire pour le réaliser.

L’algorithme n’aura, lui, qu’à permuter les trajets entre les villes pour tenter de trouver le plus court sans s’enfermer dans un minimum local.

 

 

 

CONCLUSION

 

Le recuit simulé, bien que peu utilisé, est une méthode d’optimisation très utile basée sur une méthode de réparation et de fortification des matériaux. Il y a beau exister de nombreuses méthodes d’optimisation, celle-ci est l’une des plus flexibles, même si le nombre de paramètres à choisir sans particularités précises en font une méthode nécessitant parfois plusieurs essais pour obtenir un résultat utilisable et concret.

Cependant, il est possible de l’utiliser dans un grand nombre de problèmes de différents types, que ce soit pour un vrai recuit comme pour des problèmes purement mathématiques comme celui vu ci-dessus avec le voyageur de commerce. C’est pour sa mise en application simple et sa multiplicité de possibilité d’utilisations qu’il est utilisé.

 

 

 

BIBLIOGRAPHIE

 

Nicholas Metropolis :

http://scienceworld.wolfram.com/biography/Metropolis.html

https://www.atomicheritage.org/profile/nicholas-metropolis

https://fr.wikipedia.org/wiki/Nicholas_Metropolis

Recuit :

https://fr.wikipedia.org/wiki/Recuit

Recuit Simulé :

http://www.tangentex.com/RecuitSimule.htm

file:///C:/Users/Alianor/Downloads/RCP104_recuit_simule.pdf

http://hebergement.u-psud.fr/hamadache/simulated_annealing.pdf

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *