Simulated Annealing
Le Recuit Simulé, en anglais Simulated Annealing (SA), est une méthode d’optimisation métaheuristique probabiliste utilisée pour trouver une approximation de l’optimum global d’une fonction objectif donnée dans un vaste espace de recherche. Inspirée par le processus physique du recuit en métallurgie, où un matériau est chauffé puis refroidi lentement pour augmenter la taille de ses cristaux et réduire ses défauts, cette technique algorithmique explore l’espace des solutions de manière à pouvoir échapper aux optima locaux, un piège courant pour de nombreuses autres méthodes d’optimisation.
Les concepts fondamentaux du Recuit Simulé reposent sur une analogie directe avec le recuit physique. La fonction objectif, que l’on cherche généralement à minimiser, est assimilée à l’énergie (E) d’un système physique. Une solution candidate au problème d’optimisation correspond à un état du système. Un paramètre clé, appelé température (T), contrôle la probabilité d’accepter des solutions qui dégradent la fonction objectif. Au début du processus, la température est élevée, permettant à l’algorithme d’explorer largement l’espace des solutions, y compris en acceptant des solutions moins bonnes. Progressivement, la température est abaissée selon un schéma de refroidissement, réduisant la probabilité d’accepter de mauvaises solutions et focalisant la recherche vers des régions prometteuses, favorisant ainsi l’exploitation.
Le principe essentiel du Recuit Simulé réside dans son mécanisme d’acceptation des solutions voisines. À chaque itération, une solution voisine de la solution courante est générée. Si cette nouvelle solution est meilleure (c’est-à-dire qu’elle a une énergie plus faible), elle est toujours acceptée. Si elle est moins bonne (énergie plus élevée), elle peut quand même être acceptée avec une certaine probabilité, donnée par la formule de Metropolis : P(accepter) = exp(-delta_E / T), où delta_E est l’augmentation de l’énergie (positive) et T est la température actuelle. Cette capacité à accepter temporairement des solutions de moins bonne qualité est ce qui permet au Recuit Simulé d’échapper aux optima locaux. Le choix du schéma de refroidissement, c’est-à-dire la manière dont T diminue au fil des itérations (par exemple, géométrique, linéaire, logarithmique), est crucial pour l’efficacité de l’algorithme. L’algorithme s’arrête généralement après un certain nombre d’itérations, lorsque la température atteint un seuil très bas, ou lorsque la solution ne s’améliore plus significativement.
L’importance du Recuit Simulé découle de sa capacité à aborder des problèmes d’optimisation combinatoire complexes, souvent NP-difficiles, pour lesquels les méthodes exactes sont impraticables en raison du temps de calcul exponentiel. Sa pertinence est grande dans des domaines où l’on recherche des solutions de haute qualité sans nécessairement garantir l’optimum global, mais en un temps de calcul raisonnable. L’impact du Recuit Simulé est significatif car il a fourni une approche robuste et flexible pour une vaste gamme de problèmes d’ingénierie, de recherche opérationnelle et d’intelligence artificielle. Il ne requiert pas d’informations sur les dérivées de la fonction objectif, ce qui le rend applicable même lorsque cette fonction est non différentiable, discontinue ou bruitée.
Les applications pratiques du Recuit Simulé sont nombreuses et variées. Un exemple classique est le problème du voyageur de commerce (TSP), qui consiste à trouver le plus court chemin passant par un ensemble de villes une seule fois avant de revenir au point de départ. Dans la conception de circuits intégrés à très grande échelle (VLSI), il est utilisé pour le placement optimal des composants sur une puce et pour le routage des interconnexions. D’autres applications incluent l’allocation de ressources, la planification d’horaires (scheduling) dans la production ou les services, l’optimisation des hyperparamètres en apprentissage automatique, le repliement des protéines en bioinformatique, où la conformation d’une protéine est recherchée pour minimiser son énergie, ou encore la restauration et la segmentation d’images en traitement d’images.
Il existe plusieurs nuances et variations du Recuit Simulé. Le Recuit Simulé Adaptatif (Adaptive Simulated Annealing, ASA) ajuste dynamiquement ses paramètres, comme le schéma de refroidissement ou la manière de générer les voisins, en fonction de la progression de la recherche. Des versions parallèles ont été développées pour exploiter la puissance des architectures multi-cœurs ou distribuées, exécutant plusieurs chaînes de recuit simultanément. Le Recuit Simulé Rapide (Fast Simulated Annealing, FSA), ou Recuit de Cauchy, utilise une distribution de probabilité de Cauchy pour générer les nouveaux états et un schéma de refroidissement plus rapide, permettant théoriquement une convergence plus véloce. Une variante simplifiée est l’algorithme du « Threshold Accepting », où une solution moins bonne est acceptée si la dégradation de la fonction objectif est inférieure à un seuil qui diminue progressivement, à l’instar de la température. Il est aussi important de distinguer le Recuit Simulé du Recuit Quantique, ce dernier étant un processus d’optimisation qui utilise les fluctuations quantiques pour explorer l’espace des solutions, souvent implémenté sur du matériel spécialisé.
Plusieurs concepts sont étroitement liés au Recuit Simulé. Il appartient à la famille des métaheuristiques, qui comprend également la recherche tabou, les algorithmes génétiques, l’optimisation par essaim particulaire et les algorithmes de colonie de fourmis. Il s’agit d’une forme d’optimisation stochastique et peut être vu comme une instance des méthodes de Monte Carlo par chaînes de Markov (MCMC). Le Recuit Simulé est une amélioration significative de l’algorithme de « hill climbing » (ou montée de gradient, ou descente de gradient dans le cas d’une minimisation), car ce dernier se bloque systématiquement dans le premier optimum local rencontré. Il n’y a pas de synonymes parfaits, bien que « Annealing simulé » soit parfois utilisé. Les antonymes, au sens de stratégies opposées, seraient les méthodes exactes (comme la programmation dynamique ou les algorithmes de type « branch and bound ») qui garantissent l’optimalité mais sont souvent trop lentes, ou les algorithmes gloutons (greedy) qui prennent des décisions localement optimales sans possibilité de retour en arrière.
L’origine du Recuit Simulé remonte aux travaux de Metropolis et ses collaborateurs en 1953, qui ont développé un algorithme (l’algorithme de Metropolis-Hastings) pour simuler l’évolution d’un système de particules vers l’équilibre thermique. L’idée d’utiliser cette approche pour l’optimisation combinatoire a été proposée indépendamment par Scott Kirkpatrick, C. Daniel Gelatt Jr. et Mario P. Vecchi en 1983, et par Vlado Černý en 1985. Ils ont tous deux établi l’analogie entre la minimisation d’une fonction de coût et le refroidissement lent d’un système physique. Depuis son introduction, le Recuit Simulé a connu un développement rapide et a été appliqué avec succès à une multitude de problèmes. Il continue d’être une technique de référence et est souvent intégré dans des approches hybrides plus sophistiquées.
Le Recuit Simulé présente plusieurs avantages. Sa simplicité conceptuelle et sa relative facilité d’implémentation en font un outil accessible. Il est capable de trouver des solutions de très bonne qualité, souvent proches de l’optimum global, pour des problèmes d’optimisation complexes où d’autres méthodes échouent ou sont trop coûteuses. Sous certaines conditions théoriques strictes (notamment un schéma de refroidissement infiniment lent), il est prouvé qu’il converge vers l’optimum global, bien que ces conditions soient rarement réalisables en pratique. Sa robustesse lui permet de s’adapter à divers types de problèmes sans nécessiter une connaissance approfondie de la structure de la fonction objectif. Cependant, le Recuit Simulé a aussi des inconvénients et des limitations. Il peut être relativement lent, nécessitant un grand nombre d’évaluations de la fonction objectif, surtout si un refroidissement très progressif est utilisé pour assurer une bonne exploration. Ses performances sont très sensibles au choix des paramètres : la température initiale, le schéma de refroidissement, la fonction de génération des voisins, et les critères d’arrêt. Le réglage de ces paramètres est souvent empirique et peut s’avérer fastidieux. Il n’offre aucune garantie d’atteindre l’optimum global en un temps fini dans ses implémentations pratiques. De plus, si le refroidissement est trop rapide ou si la structure de voisinage est mal définie, l’algorithme peut toujours se retrouver piégé dans des régions sous-optimales, bien que généralement meilleures que celles atteintes par des méthodes purement gloutonnes. Les défis majeurs résident donc dans la conception d’un schéma de refroidissement efficace, la définition d’une fonction de voisinage pertinente pour le problème traité, et la détermination de critères d’arrêt judicieux. La parallélisation efficace du Recuit Simulé reste également un sujet de recherche actif.