human
Veuillez expliquer ce qu'est le "recuit simulé"
gpt
Le recuit simulé (SA) est une technique probabiliste pour se rapprocher de l'optimum global d'une fonction donnée.Plus précisément, il s'agit d'un métaheuristique pour approximer 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 des vendeurs itinérants, le problème de satisfaction booléen, la prédiction de la structure des protéines et la planification de l'emploi).Pour les problèmes où trouver un optimum global approximatif est plus important que de trouver un optimum local précis dans une durée fixe, le recuit simulé peut être préférable aux algorithmes exacts tels que la descente ou la branche de gradient et liés.
Le nom de l'algorithme provient du recuit dans la métallurgie, une technique impliquant le chauffage et le refroidissement contrôlé d'un matériau pour modifier ses propriétés physiques.Les deux sont des attributs du matériau qui dépendent de leur énergie libre thermodynamique.Chauffage et refroidissement Le matériau affecte à la fois la température et l'énergie libre thermodynamique ou l'énergie de Gibbs.
Le recuit simulé peut être utilisé pour des problèmes d'optimisation de calcul très durs où les algorithmes exacts échouent;Même si cela atteint généralement une solution approximative au minimum global, cela pourrait être suffisant pour de nombreux problèmes pratiques.
Les problèmes résolus par SA sont actuellement formulés par une fonction objective de nombreuses variables, sous réserve de plusieurs contraintes.En pratique, la contrainte peut être pénalisée dans le cadre de la fonction objectif.
Des techniques similaires ont été introduites indépendamment à plusieurs reprises, notamment Pincus (1970), Khachaturyan et al (1979, 1981), Kirkpatrick, Gelatt et Vecchi (1983) et Cerny (1985).En 1983, cette approche a été utilisée par Kirkpatrick, Gelatt Jr., Vecchi, pour une solution du problème des vendeurs itinérants.Ils ont également proposé son nom actuel, un recuit simulé.
Cette notion de refroidissement lent implémenté 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 solution est exploré.Accepter de pires solutions permet une recherche plus approfondie de la solution optimale globale.En général, les algorithmes de recuit simulés fonctionnent comme suit.La température diminue progressivement d'une valeur positive initiale à zéro.À chaque pas de temps, l'algorithme sélectionne au hasard une solution proche de celle actuelle, mesure sa qualité et s'y installe en fonction des probabilités dépendantes de la température de sélectionner des solutions meilleures ou pires, qui pendant la recherche restent respectivement à 1 (ou positif) et diminuer vers 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 Monte Carlo pour générer des états d'échantillonnage d'un système thermodynamique, publié par N. Metropolis et al.en 1953.