Une méthode d'optimisation globale probabiliste qui explore un espace de solutions par perturbations aléatoires et accepte des changements selon une probabilité dépendant de la température (critère de Metropolis), de sorte que des mouvements pires peuvent être acceptés tôt pour échapper à des optima locaux et que la température décroît pour concentrer la recherche près des minima.

Principe

Imiter le recuit physique : contrôler l'exploration par un paramètre température qui diminue progressivement ; accepter des mouvements montant avec probabilité exp(-ΔE/T) pour franchir des barrières d'énergie, avec convergence vers un optimum global sous un programme de refroidissement suffisamment lent (théoriquement).

Démonstration

Optimiser une instance du voyageur de commerce en échangeant aléatoirement deux villes (voisinage). À haute température, beaucoup d'échanges sont acceptés, permettant d'échapper aux cycles locaux ; à mesure que la température baisse, moins d'échanges défavorables sont acceptés, affinant vers un tour de faible coût. En optimisation continue, perturber un vecteur de paramètres et accepter selon la règle de Metropolis.

Mauvaise application

Utiliser un refroidissement trop rapide (la température baisse trop vite) provoque une convergence prématurée vers des minima locaux médiocres ; une température initiale trop élevée ou des exécutions trop longues gaspillent du temps ; des opérateurs de voisinage inadéquats rendent l'exploration inefficace.

Conséquence

Heuristique flexible capable d'échapper à de nombreux minima locaux et souvent de trouver des solutions approchées de haute qualité dans des domaines discrets et continus ; le compromis est la stochasticité des résultats et la sensibilité au réglage du programme de température et du voisinage.

Inversion

Recherche gloutonne (hill-climbing) qui n'accepte que les améliorations et se retrouve facilement piégée dans des optima locaux, sans mécanisme probabiliste d'évasion.

Limite

Applicable aux problèmes d'optimisation discrets et continus lorsqu'une structure de voisinage et une fonction objectif sont définies ; il ne garantit pas de trouver l'optimum global sous des programmes de refroidissement pratiques, et l'efficacité dépend du choix du voisinage et de la température.

Tension sémantique

Tension entre exploration (haute température, grands mouvements) et exploitation (basse température, mouvements fins), et entre le recuit simulé et les méthodes stochastiques basées sur une population (p. ex. algorithmes génétiques) qui utilisent d'autres mécanismes pour maintenir la diversité et échapper aux minima locaux.

Synthèse

Le recuit simulé équilibre exploration aléatoire et acceptation contrôlée par la température pour franchir des barrières d'énergie et se concentrer sur des régions de faible coût ; avec un programme de refroidissement et un voisinage bien conçus, c'est une heuristique robuste pour des problèmes d'optimisation globale difficiles, bien que les résultats soient stochastiques et sensibles aux réglages.