Recuit simulé

En algorithmique, le recuit simulé est une méthode empirique (métaheuristique) d'optimisation, inspirée d'un processus, le recuit, utilisé en métallurgie. On alterne dans cette dernière des cycles de refroidissement lent et de réchauffage (recuit) qui ont pour effet de minimiser l'énergie du matériau. Cette méthode est transposée en optimisation pour trouver les extrema 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. Černy en 1985. La méthode vient du constat que le refroidissement naturel de certains métaux ne permet pas aux atomes de se placer dans la configuration la plus solide. La configuration la plus stable est atteinte en maîtrisant le refroidissement et en le ralentissant par un apport de chaleur externe, ou bien par une isolation. recuit La description des phénomènes physiques et quantiques liés au processus de recuit s'appuie sur la statistique de Maxwell-Boltzmann. lien=|500x500px Ci-dessus, on donne un exemple de recuit simulé ayant pour but de chercher un maximum. Il n'est pas suffisant d'utiliser un simple algorithme de hill climbing car il y a de nombreux maxima locaux. En refroidissant le matériau lentement, le maximum global peut être trouvé, avec une probabilité assez élevée. Le recuit simulé s'appuie sur l'algorithme de Metropolis-Hastings, 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. Partant d'un état donné du système, en le modifiant, on obtient un autre état. Soit celui-ci améliore le critère que l'on cherche à optimiser — on dit alors qu'on a fait baisser l'énergie du système — soit celui-ci le dégrade. Si on accepte un état améliorant le critère, on tend ainsi à chercher l'optimum dans le voisinage de l'état de départ.