Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
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 aujourd'hui utilisée en optimisation pour trouver les extréma 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.
| Sommaire |
La description des phénomènes physiques et quantiques liés au processus de recuit s'appuie sur la statistique de Boltzmann.
Le recuit simulé s'appuie sur l'algorithme de Metropolis, qui permet de décrire l'évolution d'un système thermodynamique. Par analogie avec le processus physique, la fonction à minimiser deviendra l'énergie du système. On introduit également un paramètre fictif, la température du système.
La solution initiale peut être prise au hasard dans l'espace des solutions possibles. À cette solution correspond une énergie initiale . Une température initiale élevée est également choisie.
À chaque itération de l'algorithme une modification élémentaire de la solution est effectuée. Cette modification entraîne une
variation de l'énergie du système. 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é 
.
On itère ensuite selon ce procédé 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. Si la température a atteint un seuil assez bas 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
( 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.
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.
Des études théoriques du recuit simulé ont pu montrer que sous certaines conditions, l'algorithme du recuit convergeait vers un optimum global. Ce résultat est important car il nous assure que le recuit simulé peut trouver la meilleure solution, contrairement à d'autres métaheuristiques.
La méthode trouve son application dans de nombreux domaines dans lesquels on a à résoudre des problèmes d'optimisation difficiles. On peut citer entre autres la conception des circuits électroniques (placement-routage) ou l'organisation de réseau informatiques.
