3.1.5. Méthode du recuit simulé
Le recuit simulé est une technique d'optimisation de type
Monte-Carlo généralisé à
laquelle on introduit un paramétrer de
température qui sera ajuster pendent
la recherche .Les concepts fondamentaux de cette technique sont
tirés de l'analogie
entre l'optimisation et la thermodynamique dans lequel les
déplacements dans l'espace
de recherche sont basés sur la distribution de Boltzmann
[26]. C'est-à-dire on cherche à
Obtenir un matériau sans impureté,
représenté par son état d'énergie minimale. Dans
le
processus de recuit réelle, nous élevons la
température du matériau jusque à ce qu'il se
trouver dans un état d'énergie
élevée .Ensuite, nous le refroidissons très lentement
de
façon à obtenir, à la fin du processus, un
matériau constitué par des atomes bien
ordonnés, correspondant à une valeur
d'énergie stable et minimale. La probabilité de
Boltzmann notée mesure la probabilité de trouver
un système dans une configuration
d'énergie , à une certaine température T
donnée, dans l'espace de configuration
et elle est définie par :
Ou : k est appelé la constante de Boltzmann
Dans cette expression, le facture KT montre que lorsque la
température est très
élevée, tous les états sont à peu
prés équiprobables, c'est-à- dire un nombre de
configuration sont accessibles .Au contraire quand la
température est basse, les états a
haute énergie deviennent peu probable s par rapport
à ceux de faible énergie. Pour
applique ce principe au problème de minimisation de
coût, le processus de recherche
peut être assimilé à un processus de recuit
comme en métallurgie .Quand on chauffe un
métal à une température très
élevés, le métal devient liquide et peut occuper toute
configuration. Quand la température décrite, le
métal va se figer peu a peu dans une
configuration .qu' il est de plus en plus difficile à,
déformer (on dit qu'il refroidie) .A
moins de le réchauffer (recuit), le métal peut
être retravailler de nouveau pour lui
donner la forme désire .l'algorithme de Kirkpatrick
simule ce processus en combinant
dans l'algorithme le mécanisme de refroidissement et de
recuit.
Figure 9: Parcours de l'espace de recherche avec le recuit
simulé .Le principe de « recuit » qui se
traduit par une augmentation du niveau d'énergie,
permet de sortir des mina locaux.
Cependant le concept de température d'un système
physique n'a pas d'équivalent
direct avec le problème à optimiser. Le
paramètre T doit être simplement un paramètre
de contrôle, indiquant le contexte dans lequel se trouve
le system (ex : stade de
recherche).En fait, le paramètre T contrôle les
déplacement vers les points voisins les
moins bons pour échapper aux optima locaux, sans pour
autant trop s'écarter du chemin
vers le vrai minimum .l'équivalent de l'énergie
sera la valeur de la fonction de coût .
Ainsi dans l'algorithme de recuit la probabilité de
Boltzmann n'est pas directement
applique, mais le critère de Metro polis est
utilisé. Le critère de Metro polis permet de
décider si une nouvelle configuration
générée présente une variation de coût
acceptable.
Il permet de décider aussi de sortir des minima locaux
quand le critère d'arrêt n'est pas
encore atteint. Le principe de Metro polis est basé sur
le calcul de la fonction de coût,
après chaque passage .D'une configuration a une
configuration.
On calcule la variation de la fonction de coût :
La transformation est acceptée selon la probabilité
telle que :
Chapitre 1: Étude de l'état de l'art
Lorsque la variation
, l'exponentielle est supérieure ou égale à
1, la nouvelle configuration doit être
acceptée, on lui affecte alors la probabilité
maximale de 1.
· , on compare à un nombre aléatoire .
· , la configuration v est acceptée.
Sinon, elle est rejetée et on essaie une autre
configuration. La configuration ayant
une forte augmentation en sont donc probables pour une
température donnée.
D'autant moins que la température est faible. Au
début de l'algorithme le facture T est
élevé, la probabilité est proche de 1 et
presque toutes les variations sont
acceptable .Au contraire, quand T diminue, les remontées
sont de plus difficiles et seules
de très faible variations peuvent être
accepté .Si une Configuration est rejetée, le system
essaie d'en trouver une autre, sinon elle est accepter et la
Recherche continue avec
celle -ci jusqu'à ce que le critère d'arrêt
soit atteint.
Génère une configuration aléatoire
et une température initiale
11 Oni Ri
Non
Oui
Non
Choisir dans le voisinage de
Génère un nombre aléatoire
Calculer )-
Abaisser
Equilibre
et
Oui
Non
41
Meilleure configuration obtenue
L'Algorithme :
1ere Etape :
Choisissons une solution initiale i dans S l'ensemble des
solutions) Appliquer
2emeEtape :
Appliquons et générons un sous-ensemble de
solutions en pour que:
une des critères d'aspiration a (i, m) soit applicable
3emeEtape :
Choisissons la meilleure solution i' parmi l'ensemble de
solutions voisines
Appliquer
4emeEtape :
Si alors nous avons trouvé une meilleure solution
Appliquer
3emeEtape :
Mettre à jour la liste et les critères
d'aspiration Étape 6: si une condition d'arrêt
est atteinte, stop. Sinon, retour à Étape 2.
Condition d'arrêt: condition qui régira l'arrêt
de l'algorithme. Ex: arrêt après 22
itérations k=22.La recherche est éloignée du
voisinage N(i) actuelle de l'ensemble des solutions Une haute
priorité est donnée aux
solutions d'une autre région que celle actuellement sous
exploration Le résultat :
chercher ailleurs
| 
