4.4 Le recuit simulé (Simulated Annealing)
4.4.1 Présentation
Comme son nom l'indique, cette métaheuristique RS
simule une opération de "recuit" qui est courante, notamment en
sidérurgie. De quoi s'agit-il? Un matériel, qui par exemple a
subi des déformations, est chauffé afin de lui fournir un haut
degré d'énergie susceptible de faire disparaitre. Puis le
matériel est refroidi très lentement, afin qu'il puisse retrouver
progressivement un équilibre, c'est-à-dire un état stable
correspondant à un niveau minimum d'énergie. L'analogie est faite
entre le niveau d'énergie et la valeur de la fonction à
minimiser. Aussi, la simulation nécessitera d'introduire dans la
méthode RS, un paramètre
69
4.4. LE RECUIT SIMULÉ
è appelé température.[13]
4.4.2 L'analogie entre le recuit physique et le recuit
simulé
On résume dans le tableau suivant l'analogie qui se trouve
entre les termes employés en recuit physique et ceux employés en
recuit simulé :
|
Problème d'optimisation
|
Système physique.
|
|
fonction objectif de coût/objectif f(x)
|
énergie libre E(x).
|
|
variable de problème
|
"Cordonnées"des atomes.
|
|
trouver une bonne configuration
|
trouver un état de basse énergie.
|
TABLE 4.1 - Analogies recuit physique / recuit
simulé
4.4.3 Paramètres opérationnelles
La fixation des paramètres
Déterminer la valeur la plus appropriée des
paramètres est certainement l'aspect le plus délicat de
l'implémentation du recuit simulé, qui sont choisi en fonction du
problème considéré et de l'instance traitée.
a) La température initiale
Elle doit être élevée pour accepter
suffisamment et facilement une solution moins bonne que la solution courante,
donc tous les voisins de la solution courante ont la même
probabilité d'être acceptés.
b) Le coefficient de refroidissement
Le paramètre á est à choisir
avec précaution. En effet, s'il est choisi trop grand, la
température baissera très rapidement et l'algorithme pourra
être bloqué dans un minima local, si au contraire il est choisi
trop petit, la température baissera très lentement et le temps de
calcul sera très grand.
70
4.4. LE RECUIT SIMULÉ
c) Le nombre d'itérations à chaque palier
de température
Un paramètre borne le nombre d'essais (itérations)
par palier. A la fin d'un palier, le compteur est incrémenté si
le pourcentage d'acceptation est inférieur à un seuil, remis
à zéro si la qualité de la meilleure solution a
évolué au cours du palier.
d) Critère d'arrêt
Tout au long du processus la température sera
diminuée, il faudra donc déterminer une température
finaleof telle que la procédure du recuit simulé se
termine lorsque la température courante atteint la température
finale.
| 
