Skip to content
Retour aux résultats

Recuit simulé — Optimisation probabiliste

Année
1983
Type
Probabilistic metaheuristic / local search

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Le recuit simulé est une métaheuristique probabiliste de recherche locale introduite par Kirkpatrick, Gelatt et Vecchi en 1983.

Elle modélise le processus physique de recuit en métallurgie — où un matériau est chauffé puis refroidi lentement pour atteindre un état cristallin de basse énergie — et utilise cette analogie pour échapper aux optima locaux dans les problèmes d'optimisation combinatoire et continue.

L’intuition derrière la méthode

Imaginez que vous cherchiez le point le plus bas dans un paysage vallonné tout en étant bandé. Une recherche purement gloutonne progresse toujours en descente et se bloque dans la première vallée qu'elle trouve — qui peut ne pas être la plus profonde. Le recuit simulé introduit un caractère aléatoire contrôlé : au début, lorsque la « température » est élevée, l'algorithme est disposé à monter occasionnellement, acceptant une solution moins bonne par hasard. À mesure que la température diminue selon un calendrier de refroidissement, l'algorithme devient de plus en plus sélectif, convergeant vers une solution. Cette volonté d'accepter des mouvements moins bons à haute température est ce qui permet à la méthode d'échapper aux optima locaux peu profonds et d'explorer le paysage plus en profondeur.

Histoire

Le recuit simulé a été introduit par Kirkpatrick, Gelatt et Vecchi dans leur article fondateur de 1983 dans Science, qui établissait une analogie explicite entre le recuit thermodynamique des solides et l'optimisation combinatoire. La même idée a été proposée indépendamment par Cerny (1985) dans le contexte du problème du voyageur de commerce. van Laarhoven et Aarts (1987) ont fourni le premier traitement théorique rigoureux, prouvant les propriétés de convergence sous divers calendriers de refroidissement. Depuis lors, la méthode est devenue l'une des métaheuristiques les plus étudiées et appliquées, utilisée dans la conception d'ingénierie, la recherche opérationnelle, la disposition VLSI et l'optimisation des hyperparamètres en apprentissage automatique.

Quand l’utiliser

Le recuit simulé est applicable à tout problème où une structure de voisinage peut être définie sur l'espace des solutions, indépendamment du fait que la fonction objectif soit différentiable, convexe, ou même analytiquement exprimable. Il est particulièrement bien adapté aux problèmes combinatoires (ordonnancement, routage, problèmes de graphes) et à l'optimisation continue boîte noire. Aucune donnée d'entraînement ni hypothèse de normalité n'est requise. Le calendrier de refroidissement et la structure du voisinage doivent être ajustés au problème ; exécuter moins d'environ 1 000 itérations risque une convergence prématurée vers un optimum local, auquel cas une recherche locale déterministe plus simple devrait être préférée.

Limites et points d’attention

  • La qualité de la solution est sensible au calendrier de refroidissement ; un mauvais calendrier peut donner des résultats pas meilleurs qu'une recherche aléatoire.
  • La structure du voisinage doit être conçue pour chaque classe de problème, ce qui nécessite une expertise du domaine.
  • La convergence vers l'optimum global nécessite un refroidissement extrêmement lent en pratique, rendant le temps d'exécution long pour des garanties de haute qualité.
  • N'exploite pas les informations de gradient ou structurelles, donc les méthodes basées sur le gradient le surpassent sur les problèmes lisses et différentiables.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Peut échapper aux optima locaux grâce à l'acceptation probabiliste de solutions moins bonnes, contrairement à la montée de colline pure.
  • S'applique à pratiquement tout type de problème — combinatoire, continu, mixte — tant qu'une structure de voisinage est définie.
  • Ne nécessite aucune information de gradient et est indifférent à la structure mathématique de la fonction objectif.
  • Possède une garantie théorique de convergence vers l'optimum global sous un refroidissement suffisamment lent (Hajek 1988).
  • Peu d'hyperparamètres : température initiale, taux de refroidissement et structure du voisinage.

Applications

  • Problèmes d'ordonnancement et de planification combinatoires où l'espace des solutions est trop vaste pour une recherche exhaustive.
  • Problèmes du voyageur de commerce et de tournées de véhicules en logistique et recherche opérationnelle.
  • Disposition de circuits VLSI et planification de puces en ingénierie électrique.
  • Problèmes de repliement de protéines et de conformation moléculaire en biologie computationnelle.
  • Optimisation des hyperparamètres pour les modèles d'apprentissage automatique lorsque les informations de gradient sont indisponibles.
  • Problèmes d'allocation et d'affectation de ressources en ingénierie et en sciences de gestion.

Comment ça marche

Comment ça marche

1

L'algorithme commence avec une solution initiale — tout point réalisable dans l'espace de recherche — et une température initiale élevée. La solution de départ peut être aléatoire ou spécifique au problème ; la température initiale est généralement réglée suffisamment haut pour que presque toute solution voisine soit acceptée au début.

2

Une solution voisine est générée en appliquant une petite modification aléatoire (un « mouvement ») à la solution actuelle. La structure du voisinage doit être adaptée au problème : pour un problème d'ordonnancement, un mouvement peut échanger deux tâches ; pour une fonction continue, il peut ajouter une petite perturbation aléatoire au vecteur de paramètres actuel.

3

La différence de valeur objective entre la nouvelle solution et la solution actuelle est calculée. Si la nouvelle solution est meilleure, elle est toujours acceptée. Si elle est moins bonne, elle est acceptée avec une probabilité qui décroît avec l'ampleur de la détérioration et la température actuelle — typiquement exp(−ΔE / T). Cette acceptation probabiliste est le mécanisme central qui empêche la convergence prématurée.

4

Après chaque itération (ou après un nombre fixe de mouvements à la même température), la température est réduite selon un calendrier de refroidissement — couramment un calendrier géométrique T ← α·T où α est légèrement inférieur à 1. Le choix du calendrier de refroidissement affecte fortement la qualité de la solution : un refroidissement trop rapide piège la recherche dans un optimum local ; un refroidissement trop lent gaspille du temps de calcul.

5

L'algorithme s'arrête lorsque la température tombe en dessous d'un seuil minimum, qu'un nombre maximum d'itérations est atteint, ou que la solution ne s'est pas améliorée depuis un nombre spécifié d'étapes. La meilleure solution rencontrée tout au long de l'exécution — pas seulement l'état final — est retournée comme résultat.

Pièges courants

  • Exécuter trop peu d'itérations (environ moins de 1 000) empêche le calendrier de refroidissement de fonctionner correctement et laisse la recherche piégée dans un optimum local — préférez la recherche tabou ou une recherche locale déterministe si le temps d'exécution est sévèrement limité.
  • Régler la température initiale trop bas signifie que l'algorithme se comporte immédiatement comme une montée de colline gloutonne et perd sa capacité à échapper aux optima locaux.
  • Régler le taux de refroidissement trop agressivement (par exemple, α inférieur à 0,9) provoque une convergence prématurée ; vérifiez la qualité de la solution finale en redémarrant à partir de plusieurs solutions initiales.
  • Appliquer un mouvement de voisinage conçu pour un type de problème à un problème différent peut rendre les mouvements infaisables ou dénués de sens — vérifiez toujours que chaque voisin généré est une solution valide.
  • Rapporter uniquement l'état final plutôt que la meilleure solution jamais vue pendant l'exécution peut manquer l'optimum réel trouvé à une étape intermédiaire.

Questions fréquentes

Comment choisir le calendrier de refroidissement ?

Le calendrier géométrique T ← α·T avec α entre 0,90 et 0,99 est le point de départ le plus courant. Une approche pratique consiste à régler la température initiale suffisamment haut pour qu'environ 80 % des mouvements soient acceptés au début, puis à la réduire jusqu'à ce que moins de 1 % des mouvements ascendants soient acceptés. Si la qualité de la solution finale est médiocre, ralentissez le taux de refroidissement (augmentez α) ; si le temps d'exécution est trop long, accélérez-le. Exécutez toujours l'algorithme plusieurs fois à partir de différentes solutions initiales pour évaluer la robustesse.

En quoi le recuit simulé diffère-t-il des algorithmes génétiques ou de l'optimisation par essaim particulaire ?

Le recuit simulé maintient une seule solution et explore le voisinage par des perturbations aléatoires, acceptant les solutions moins bonnes de manière probabiliste. Les algorithmes génétiques et l'optimisation par essaim particulaire maintiennent une population de solutions et utilisent le croisement, la mutation ou le mouvement de l'essaim pour faire évoluer la population. Le recuit simulé est généralement plus simple à implémenter pour les problèmes avec une structure de voisinage naturelle, tandis que les méthodes basées sur la population peuvent être plus efficaces pour les problèmes continus de haute dimension.

L'optimum global est-il garanti ?

Théoriquement oui, à condition que la température diminue suffisamment lentement (refroidissement logarithmique). En pratique, un tel refroidissement est informatiquement infaisable, donc l'algorithme trouve une solution quasi optimale. La qualité du résultat s'améliore avec un refroidissement plus lent et plus d'itérations, mais il n'y a pas de garantie en temps fini. Exécuter plusieurs redémarrages et conserver la meilleure solution trouvée est un moyen pratique d'accroître la confiance.

Quand devrais-je préférer la recherche tabou ou un algorithme génétique à la place ?

Choisissez la recherche tabou lorsque vous avez besoin d'une recherche déterministe guidée par la mémoire qui évite de revisiter les solutions récentes et peut exploiter efficacement la structure du problème en un temps d'exécution plus court. Choisissez un algorithme génétique ou une optimisation par essaim particulaire lorsque le problème est de haute dimension et continu, ou lorsqu'une population de solutions diverses est nécessaire pour cartographier le paysage de l'optimum. Le recuit simulé est un excellent choix par défaut pour les problèmes combinatoires avec une structure de voisinage claire et lorsque la simplicité d'implémentation est importante.

Méthodes associées

Sources

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    Ouvrir la référence DOI
    Copié.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN : 9789027725431
    Copié.