Recuit simulé

Le recuit simulé (SA) est une technique probabiliste permettant d’approcher l’optimum global d’une fonction donnée.

Spécifiquement, il est métaheuristique d'approcher l'optimisation globale dans un grand espace de recherche pour un problème d'optimisation. Il est souvent utilisé lorsque l'espace de recherche est discret (par exemple, le problème du vendeur voyageur). Pour les problèmes dans lesquels la recherche d'un optimum global approximatif est plus importante que la recherche d'un optimum local précis dans un laps de temps déterminé, un recuit simulé peut être préférable à des alternatives telles que la descente de gradient.

Le nom et l'inspiration viennent du recuit en métallurgie, une technique impliquant le chauffage et le refroidissement contrôlé d'un matériau pour augmenter la taille de ses cristaux et réduire leurs défauts. Les deux sont des attributs du matériau qui dépendent de son énergie thermodynamique. Le chauffage et le refroidissement du matériau affectent à la fois la température et l'énergie libre thermodynamique. La simulation de recuit peut être utilisée pour trouver une approximation d'un minimum global pour une fonction à plusieurs variables. 

Cette notion de refroidissement lent implémentée dans l'algorithme de recuit simulé est interprétée comme une diminution lente de la probabilité d'accepter des solutions pires à mesure que l'espace de la solution est exploré. L'acceptation de solutions pires est une propriété fondamentale de la métaheuristique, car elle permet une recherche plus approfondie de la solution optimale globale. En général, les algorithmes de simulation et d’annelage fonctionnent comme suit. À chaque pas de temps, l’algorithme sélectionne aléatoirement une solution proche de la solution actuelle, en mesure la qualité, puis décide de la remplacer ou de rester avec la solution actuelle en fonction de l’une des deux probabilités entre lesquelles il choisit la valeur de son choix. base de ce que la nouvelle solution est meilleure ou pire que la solution actuelle. Pendant la recherche, la température est progressivement réduite d'une valeur positive initiale à zéro et affecte les deux probabilités: à chaque étape, la probabilité de passer à une meilleure nouvelle solution est soit maintenue à 1, soit changée en une valeur positive; d'autre part, la probabilité de passer à une solution nouvelle plus dégradée change progressivement pour atteindre zéro.

La simulation peut être effectuée soit par une solution d'équations cinétiques pour les fonctions de densité  , soit en utilisant la méthode d'échantillonnage stochastique.    La méthode est une adaptation de l’algorithme Metropolis – Hastings, une méthode de Monte Carlo permettant de générer des états d'échantillonnage d'un système thermodynamique, publiée par N. Metropolis et al. en 1953.

Dans l’intelligence artificielle la recherche, l’approche située Buil agents ds qui sont conçus pour se comporter efficacement avec succès dans leur environnement. Cela nécessite de concevoir l'IA «de bas en haut» en se concentrant sur les habiletés perceptuelles et motrices de base nécessaires à la survie. L'approche située donne beaucoup moins d’importance au raisonnement abstrait ou à la résolution de problèmes.

L’approche a été proposée à l’origine comme alternative aux approches traditionnelles (c’est-à-dire aux approches populaires avant 1985 environ). Après plusieurs décennies, les technologies classiques de l’IA ont commencé à faire face à des problèmes insolubles (par exemple, une explosion combinatoire) lorsqu'elles ont été confrontées à des problèmes de modélisation dans le monde réel. Toutes les approches pour traiter ces problèmes se concentrent sur la modélisation des intelligences situées dans un environnement. Ils sont maintenant connus comme l'approche située de l'IA.