II- 6. 2. 2 Recuit Simulé :
Le recuit simulé est une version
améliorée de la méthode
d'amélioration itérative. Il a été
proposé en 1983 par Kirkpatrick pour la résolution des
problèmes d'optimisation. La méthode imite le
principe thermodynamique. Elle s'inspire du
phénomène physique de refroidissement lent d'un
corps en fusion qui le conduit à un état solide de basse
énergie.
Un métal est chauffé à une
température très élevée, il devient liquide et peut
occuper toute configuration. Quand la température décroît,
le métal va se figer peu à peu dans une configuration
qu'il de plus en plus difficile à déformer, il
est refroidi. En le réchauffant (recuit), le métal peut
être retravaillé de nouveau pour lui donner la forme
désirée. Il faut baisser lentement la température en
marquant des palies suffisamment longs pour que le corps atteigne
l'équilibre thermodynamique à chaque palier de
la température, ce qui permet d'obtenir à la fin
processus un matériau dans un état cristallin bien ordonné
correspondant à un état d'énergie
minimum. Par contre, si la baisse de température se fait de
manière trop brutale, le matériau est amorphe et ses atomes sont
figés dans un état désordonné traduisant un minimum
local d'énergie [15].
II- 6. 2. 2. 1 Température initiale
La température initiale est choisie arbitrairement par le
programmeur, il est souvent nécessaire de tester l'algorithme pour
choisir la bonne température initiale.
II- 6. 2. 2. 3 Modification
élémentaire
La modification élémentaire permet de faire
évoluer la solution. Une fois cette modification effectuée, il
nous faut calculer la nouvelle valeur de l'énergie du système et
faire la différence avec l'ancienne.
II- 6. 2. 2. 4 Paramètres :
La principale difficulté rencontrée dans la
résolution d'un problème
d'optimisation par cette méthode est liée
à la détermination du schéma de refroidissement.
L'ensemble des paramètres qui gouvernent la convergence
de l'algorithme sont :
· Valeur initiale du paramètre de contrôle T0
(température initiale)
· Facteur de réduction de la température
rt
· Nombre d'itérations à
température constante (longueur de la chaîne de Markov) Lm
· Taille de voisinage Ns
· Critère d'arrêt
Début
II- 6. 2. 2. 5 Algorithme :
L'organigramme suivant expose l'algorithme du recuit
simulé. Les sections suivantes détaillent et expliquent
l'organigramme.
Configuration initiale
Température initiale T
Fin
Non
Règle d'acceptation de Metropolis
:
- Si ÄE = 0 : modification
accepté
- Si ÄE > 0 : modification
accepté
Modification élémentaire
Variation
d'énergie ÄE
Oui
Equilibre
thermodynamique
Oui
Système figé
Non
Programme du recuit
Diminution lente
de
T
Figure II -9 : Organigramme de
l'algorithme du recuit simulé.
| 
