🎛️ Optimisation d'une fonction à pièges (vallées locales)
Une fonction f(x) à minimiser. Une descente naïve tombe dans le premier minimum local. Le recuit simulé, lui, accepte parfois de remonter — surtout au début quand T est haut — et trouve le vrai minimum global.
Température
5.000
f(x) courant
—
Meilleur trouvé
—
La balle suit la courbe. À T élevée, elle saute les barrières. Quand T baisse, elle se fige dans la vallée la plus profonde.
⚒️ La métaphore métallurgique
Depuis des millénaires, les forgerons et métallurgistes connaissent la technique du recuit : chauffer un métal jusqu'à très haute température, puis le refroidir très lentement. Résultat : les atomes ont le temps de se réorganiser en cristal parfait, sans défaut. Le métal devient plus résistant, moins cassant.
Si on refroidit trop vite (trempe), les atomes restent figés dans des positions sous-optimales : il y a des défauts, des contraintes internes. Le métal est dur mais cassant.
🎯 1983 : Kirkpatrick traduit l'idée en algorithme
Scott Kirkpatrick, C. Daniel Gelatt et Mario Vecchi, chercheurs à IBM, travaillent sur le design VLSI (intégration à très grande échelle de circuits) : placer des millions de transistors sur une puce pour minimiser la longueur totale des connexions. Problème NP-difficile.
Ils ont l'intuition : un système physique qui se refroidit lentement trouve son état d'énergie minimale (l'état fondamental). Pourquoi ne pas imiter cette physique pour résoudre des problèmes d'optimisation ?
En 1983, ils publient « Optimization by Simulated Annealing » dans Science. L'article est devenu l'un des plus cités de toute l'informatique théorique.
🔥 L'algorithme en 5 lignes
- Partir d'une solution initiale x. Évaluer son coût E(x).
- À chaque étape, proposer une perturbation x' (voisin aléatoire). ΔE = E(x') − E(x).
- Si ΔE < 0 (amélioration) : accepter x → x'.
- Si ΔE > 0 (détérioration) : accepter avec probabilité exp(−ΔE/T).
- Diminuer la température T (schéma de refroidissement). Recommencer.
Critère de Metropolis (1953)
P(accepter) = exp(−ΔE / T)
T grand → on accepte presque tout (exploration)
T petit → on n'accepte que les améliorations (exploitation)
🌡️ Schémas de refroidissement
- Géométrique : T_{n+1} = α · T_n avec α ∈ [0.8, 0.999]. Le plus utilisé.
- Logarithmique : T_n = T₀ / log(n + 2). Convergence garantie théoriquement (Geman-Geman 1984), mais en pratique trop lent.
- Linéaire : T_n = T₀ · (1 − n/N).
- Adaptatif : ajuster T selon le taux d'acceptation. Plus sophistiqué, utilisé en pratique.
⚖️ Garantie théorique (Geman-Geman 1984)
Si la température décroît assez lentement (T_n ≥ C / log(n)), le recuit simulé converge vers l'optimum global avec probabilité 1. C'est une garantie unique parmi les heuristiques.
En pratique, on triche : on utilise un refroidissement géométrique beaucoup plus rapide. On n'a plus la garantie, mais on obtient d'excellentes solutions en temps raisonnable.
🚀 Applications concrètes
- Design VLSI : placement de transistors sur les puces Intel, AMD, Apple Silicon. Encore utilisé aujourd'hui en complément du recuit quantique (D-Wave).
- Voyageur de commerce (TSP) : recuit simulé est l'un des algorithmes standards. Résout des instances de 10 000 villes à 5 % de l'optimum.
- Planification d'horaires : SNCF, Air France, universités. Affecter cours/professeurs/salles sous contraintes.
- Image processing : restauration d'images, segmentation, débruitage. Champ de Markov.
- Repliement de protéines : trouver la conformation 3D d'énergie minimale. Pré-AlphaFold, c'était la méthode dominante.
- Optimisation de portefeuille financier : Markowitz avec contraintes complexes (entiers, transactions, taxes).
- Allocation de fréquences : assigner des canaux à des antennes mobiles (4G/5G) en évitant les interférences.
- Conception de molécules : drug discovery, optimisation de la liaison ligand-protéine.
- Optimisation de codes : compilateurs, ordonnancement d'instructions CPU.
- Cryptanalyse : casser certains chiffrements simples (substitution, transposition).
- Sport : optimiser le calendrier de la NBA, NFL, Coupe du monde.
🌌 Famille des métaheuristiques bio-inspirées
Le recuit simulé fait partie d'une grande famille d'algorithmes inspirés de la nature :
- Algorithmes génétiques (Holland 1975) : population, sélection, mutation, crossover. Imite l'évolution darwinienne.
- Particle Swarm Optimization (Kennedy-Eberhart 1995) : volée d'oiseaux.
- Colonies de fourmis (Dorigo 1992) : phéromones. Excellent pour le TSP.
- Algorithmes immunitaires : imite le système immunitaire.
- Recuit quantique (Kadowaki-Nishimori 1998) : version quantique exploitant l'effet tunnel. Cœur des ordinateurs D-Wave (5000+ qubits en 2024).
🔍 Comparaison avec la descente de gradient
| Aspect | Descente de gradient | Recuit simulé |
|---|---|---|
| Vitesse | Très rapide | Lent |
| Minimum global | Non (piégé localement) | Oui (asymptotiquement) |
| Continuité requise | Oui (gradient) | Non (combinatoire OK) |
| Cas d'usage | Deep learning, convexe | NP-difficile, discret |
📐 Le lien avec ton programme
- Exponentielle : exp(−ΔE/T) est la base du critère d'acceptation. Programme 2BAC SM.
- Probabilités : on accepte avec une certaine probabilité. Loi uniforme, simulation. Programme 2BAC SM.
- Suites : la température T_n est une suite (géométrique le plus souvent). Programme 1BAC et 2BAC SM.
- Convergence : analyse de la convergence vers l'optimum. Programme suites 2BAC SM.
- Thermodynamique / Boltzmann : la distribution exp(−E/T) est la distribution de Boltzmann. Physique 2BAC.
- Méthodes numériques : algorithmes itératifs. Programme info option.