Comprendre le recuit simulé : accepter un détour pour mieux optimiser

Le rôle de la température, la sortie des minima locaux et un exemple chiffré pour comprendre la méthode.

Le recuit simulé cherche une bonne solution à un problème d’optimisation en acceptant parfois une dégradation temporaire. Inspiré du refroidissement contrôlé des métaux, il utilise une « température » fictive : élevée au début pour favoriser l’exploration, puis progressivement réduite pour rendre la recherche plus sélective. Cette stratégie aide à dépasser des minima locaux, sans garantir la meilleure solution dans un temps de calcul limité. [3], [2], [1]

In this article

L’idée essentielle : ne pas toujours choisir le gain immédiat
Pourquoi parler de recuit et de température ?
La règle de décision, étape par étape
Exemple chiffré : accepter ou refuser un détour de 2 km
Quand l’utiliser et quels réglages surveiller ?

L’idée essentielle : ne pas toujours choisir le gain immédiat

Explorer : accepter parfois une solution moins bonne permet de ne pas limiter la recherche aux seules améliorations immédiates. [1]
Refroidir : diminuer la température rend les dégradations de moins en moins faciles à accepter. [1], [2]
Rester pragmatique : l’objectif pratique est de trouver une très bonne solution, pas de certifier systématiquement l’optimum. [1]

Imaginez une tournée reliant plusieurs villes : vous voulez réduire sa distance totale et essayez d’échanger l’ordre de deux visites. Une méthode qui conserve uniquement les échanges raccourcissant le trajet peut finir bloquée. Aucun échange autorisé n’améliore alors la tournée, même si une autre organisation serait globalement meilleure. C’est un minimum local : une solution avantageuse par rapport à ses voisines, mais pas nécessairement la meilleure parmi toutes les solutions possibles. Le recuit simulé introduit une marge de liberté pour tenter de dépasser ce blocage. [1]

Pourquoi parler de recuit et de température ?

Le nom vient du recuit métallurgique, qui associe chauffage et refroidissement contrôlé. L’analogie porte sur la recherche d’une configuration de faible énergie : en optimisation, cette énergie devient une fonction de coût, par exemple la distance d’une tournée. La température informatique est un paramètre fictif, et non la température du processeur. Elle règle la facilité avec laquelle l’algorithme accepte de passer vers une solution plus coûteuse. L’inspiration est donc celle d’un processus physique, plutôt que d’un comportement animal ou d’un mécanisme biologique. [1], [2], [3]

À température élevée, de nombreux changements défavorables sont acceptés : la recherche parcourt plus librement l’espace des solutions. Lorsque la température baisse, ces changements deviennent moins probables et la recherche se concentre davantage sur les améliorations. Refroidir ne signifie donc pas réduire mécaniquement le coût à chaque étape. Cela signifie modifier progressivement la règle d’acceptation. Même à basse température, certaines dégradations peuvent encore être retenues ; une phase finale n’acceptant que les améliorations constitue une possibilité distincte. [1], [3]

La règle de décision, étape par étape

On part d’une solution courante et on propose une solution voisine, généralement à l’aide d’une modification aléatoire. On calcule ensuite la variation ΔE = coût(voisine) − coût(courante). Une valeur négative indique une amélioration : on accepte le changement. Pour une dégradation, avec ΔE > 0, la règle usuelle de Metropolis utilise la probabilité p = exp(−ΔE / T), pour une température strictement positive. On tire un nombre aléatoire entre 0 et 1 : si celui-ci est inférieur à cette probabilité, le changement est accepté. [2], [1], [3]

La boucle se poursuit en abaissant la température selon un calendrier choisi. Il est utile de distinguer la solution courante, qui peut temporairement se dégrader, de la meilleure solution déjà rencontrée, conservée séparément. Le pseudo-code présenté dans la référence française mémorise cette meilleure solution et prévoit notamment un arrêt au nombre maximal d’étapes ou lorsqu’un objectif de coût est atteint. Cette distinction permet de poursuivre l’exploration sans devoir rendre une solution moins bonne que celle trouvée auparavant. [1], [3]

Exemple chiffré : accepter ou refuser un détour de 2 km

Prenons un exemple hypothétique : une tournée mesure 100 km. Un échange de deux visites produit un trajet de 102 km, soit une dégradation de 2 km. Pour appliquer la formule, exprimons le coût en unités correspondant au kilomètre et la température sur une échelle compatible : le rapport ΔE/T doit être sans dimension. Les valeurs suivantes sont des calculs illustratifs dérivés de la règle, et non des résultats expérimentaux ou des températures recommandées. [1], [3]

Avec un tirage aléatoire égal à 0,40, ce détour serait accepté à T = 10, mais refusé à T = 0,5. Le même changement reçoit donc des décisions différentes selon la température. L’accepter peut ouvrir l’exploration d’autres tournées ; cela ne prouve toutefois pas qu’une meilleure tournée sera ensuite trouvée. Si un autre échange ramenait directement le trajet de 100 à 98 km, il serait accepté comme amélioration, indépendamment de cette tolérance aux dégradations. [1], [3]

Situation illustrative	Calcul d’acceptation	Interprétation
100 → 102 km ; T = 10	exp(−2/10) ≈ 0,819, soit 81,9 %	Dégradation assez facilement acceptée [3]
100 → 102 km ; T = 0,5	exp(−2/0,5) ≈ 0,0183, soit 1,83 %	Même dégradation rarement acceptée [3]
100 → 98 km ; T > 0	ΔE = −2 : amélioration acceptée	Pas de tirage nécessaire pour accepter l’amélioration [3]

Quand l’utiliser et quels réglages surveiller ?

Le recuit simulé présente un intérêt pour des problèmes combinatoires dont l’exploration devient difficile lorsque le nombre d’objets augmente. Le voyageur de commerce en est un exemple concret : il fournit une fonction de coût claire et un voisinage défini par des échanges de visites. Pour transposer la méthode, commencez donc par préciser ce que vous minimisez et comment vous produisez une solution voisine. Ces deux choix donnent un sens opérationnel à la recherche, avant même de choisir le refroidissement. [1], [3]

Les principaux paramètres sont la température initiale, sa loi de décroissance, la longueur des paliers et les critères d’arrêt. Leur choix est souvent empirique : il n’existe pas ici de recette chiffrée universelle à appliquer. Enfin, il faut séparer théorie et usage pratique. Des résultats de convergence vers l’optimum global existent sous certaines conditions, dans une perspective de recherche indéfinie. Ils ne constituent pas une garantie pour une exécution finie. La promesse raisonnable reste celle d’une méthode capable de trouver de très bonnes solutions, avec un effort de réglage. [3], [1]

Frequently asked questions

Une solution moins bonne est-elle toujours acceptée au début ?

Non. Pour une température finie et une dégradation strictement positive, l’acceptation reste probabiliste. Elle dépend à la fois de l’ampleur de la dégradation et de la température : une température élevée favorise l’acceptation, mais ne rend pas automatiquement tous les changements acceptables. [3], [1]

Que signifie exactement « minimum local » ?

C’est une solution qu’aucun changement du voisinage considéré ne permet d’améliorer, alors qu’une meilleure solution peut exister ailleurs. Dans une tournée, ne plus trouver d’échange de deux visites raccourcissant le trajet ne suffit donc pas à prouver que le trajet est optimal. [1]

Faut-il attendre que la température atteigne zéro ?

Pas nécessairement. Un arrêt peut être fixé par un nombre maximal d’étapes ou un objectif de coût. La formule présentée suppose une température positive ; une éventuelle phase finale n’acceptant que les améliorations peut être traitée séparément. [3], [1]

Pourquoi conserver la meilleure solution séparément ?

Parce que la solution courante peut se dégrader au cours de l’exploration. Mémoriser la meilleure solution rencontrée permet de restituer ce meilleur résultat plutôt que le dernier état visité. C’est la distinction utilisée dans le pseudo-code de la référence française. [3]

Existe-t-il une variante sans acceptation probabiliste ?

Oui : l’acceptation par seuil conserve les améliorations et accepte les dégradations inférieures à un seuil, abaissé périodiquement. Elle remplace ainsi la décision probabiliste d’acceptation par une comparaison à ce seuil ; elle ne doit pas être confondue avec le recuit simulé classique. [1]

Conclusion

Le recuit simulé repose sur une idée simple : une dégradation immédiate peut être un détour utile dans une recherche d’optimisation. La température règle cette liberté, puis son abaissement rend progressivement la recherche plus sélective. Pour bien comprendre ou mettre en œuvre la méthode, définissez d’abord le coût et les solutions voisines, distinguez l’état courant du meilleur résultat rencontré, puis choisissez le refroidissement et l’arrêt. Sa valeur pratique tient à cette exploration contrôlée, non à une garantie automatique d’optimalité. [1], [3]

Explore next

Sources

Open a source or expand its cited passages.

Relevance scores are model estimates of how well each source addresses this question, not probabilities or fact-check ratings. Reasoned guidance is identified on hover.