Recuit simulé - Simulated annealing

Le recuit simulé peut être utilisé pour résoudre des problèmes combinatoires. Ici, il est appliqué au problème du voyageur de commerce pour minimiser la longueur d'un itinéraire qui relie les 125 points.

Problème de voyageur de commerce en 3D pour 120 points résolu avec recuit simulé.

Le recuit simulé ( SA ) est une technique probabiliste d'approximation de l' optimum global d'une fonction donnée . Plus précisément, il s'agit d'une 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 du voyageur de commerce , le problème de satisfiabilité booléenne , la prédiction de la structure des protéines et l' ordonnancement de l'atelier ). Pour les problèmes où trouver un optimum global approximatif est plus important que de trouver un optimum local précis dans un laps de temps fixe, le recuit simulé peut être préférable aux algorithmes exacts tels que la descente de gradient ou la branche et la limite .

Le nom de l'algorithme vient du recuit en 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. Le chauffage et le refroidissement du matériau affectent à la fois la température et l'énergie libre thermodynamique ou énergie de Gibbs. Le recuit simulé peut être utilisé pour des problèmes d'optimisation de calcul très difficiles où les algorithmes exacts échouent ; même s'il permet généralement d'obtenir une solution approximative du minimum global, il pourrait suffire à de nombreux problèmes pratiques.

Les problèmes résolus par SA sont actuellement formulés par une fonction objectif de nombreuses variables, soumises à 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), Khatchatourian 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 du voyageur de commerce. Ils ont également proposé son nom actuel, recuit simulé.

Cette notion de refroidissement lent implémentée dans l'algorithme de recuit simulé est interprétée comme une lente diminution de la probabilité d'accepter les pires solutions à mesure que l'espace des solutions est exploré. Accepter les pires solutions permet une recherche plus approfondie de la solution optimale globale. En général, les algorithmes de recuit simulé fonctionnent comme suit. La température décroît progressivement d'une valeur initiale positive à zéro. A chaque pas de temps, l'algorithme sélectionne aléatoirement une solution proche de la solution courante, mesure sa qualité, et s'y déplace en fonction des probabilités dépendant de la température de sélectionner les meilleures ou les pires solutions, qui lors de la recherche restent respectivement à 1 (ou positives ) et décroît 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 de Monte Carlo pour générer des échantillons d'états d'un système thermodynamique, publiée par N. Metropolis et al. en 1953.

Aperçu

L' état de certains systèmes physiques , et la fonction E ( s ) à minimiser, est analogue à l' énergie interne du système dans cet état. Le but est d'amener le système, d'un état initial arbitraire , à un état avec le minimum d'énergie possible.

Recuit simulé à la recherche d'un maximum. L'objectif ici est d'atteindre le point le plus élevé. Dans cet exemple, il ne suffit pas d'utiliser un simple algorithme de montée de côte , car il existe de nombreux maxima locaux . En refroidissant lentement la température, le maximum global est trouvé.

L'itération de base

À chaque étape, l'heuristique de recuit simulé considère un état voisin s* de l'état courant s et décide de manière probabiliste entre déplacer le système vers l'état s* ou rester dans l'état s . Ces probabilités conduisent finalement le système à passer à des états de plus faible énergie. Typiquement, cette étape est répétée jusqu'à ce que le système atteigne un état suffisamment bon pour l'application, ou jusqu'à ce qu'un budget de calcul donné soit épuisé.

Les voisins d'un état

L'optimisation d'une solution implique d'évaluer les voisins d'un état du problème, qui sont de nouveaux états produits en modifiant de manière conservatrice un état donné. Par exemple, dans le problème du voyageur de commerce, chaque état est typiquement défini comme une permutation des villes à visiter, et les voisins de n'importe quel état sont l'ensemble des permutations produites en échangeant deux quelconques de ces villes. La manière bien définie dont les états sont modifiés pour produire des états voisins s'appelle un « mouvement », et différents mouvements donnent différents ensembles d'états voisins. Ces mouvements entraînent généralement des modifications minimales du dernier état, dans le but d'améliorer progressivement la solution en améliorant itérativement ses parties (telles que les connexions avec la ville dans le problème du voyageur de commerce).

Des heuristiques simples comme l' escalade , qui se déplacent en trouvant meilleur voisin après meilleur voisin et s'arrêtent lorsqu'elles ont atteint une solution qui n'a pas de voisins qui soient de meilleures solutions, ne peuvent garantir de conduire à l'une des meilleures solutions existantes - leur résultat peut facilement être juste. un optimum local , alors que la meilleure solution réelle serait un optimum global qui pourrait être différent. Les métaheuristiques utilisent les voisins d'une solution comme moyen d'explorer l'espace des solutions, et bien qu'elles préfèrent les meilleurs voisins, elles acceptent également les pires voisins afin d'éviter de rester bloqués dans les optima locaux ; ils peuvent trouver l'optimum global s'ils sont exécutés pendant une durée suffisamment longue.

Probabilités d'acceptation

La probabilité de passer de l'état actuel à un nouvel état candidat est spécifiée par une fonction de probabilité d'acceptation , qui dépend des énergies et des deux états, et d'un paramètre global variable dans le temps appelé température . Les États avec une plus petite énergie sont meilleurs que ceux avec une plus grande énergie. La fonction de probabilité doit être positive même lorsque est supérieur à . Cette fonctionnalité empêche la méthode de se bloquer à un minimum local qui est pire que le global. ${\style d'affichage s}$${\displaystyle s_{\mathrm {nouveau} }}$ ${\displaystyle P(e,e_{\mathrm {nouveau} },T)}$${\style d'affichage e=E(s)}$${\displaystyle e_{\mathrm {nouveau} }=E(s_{\mathrm {nouveau} })}$${\style d'affichage T}$${\style d'affichage P}$${\displaystyle e_{\mathrm {nouveau} }}$${\style d'affichage e}$

Quand tend vers zéro, la probabilité doit tendre vers zéro si et vers une valeur positive sinon. Pour des valeurs suffisamment petites de , le système privilégiera alors de plus en plus les mouvements qui vont "en descente" (c'est-à-dire pour des valeurs d'énergie plus basses), et évitera ceux qui vont "en montée". Avec la procédure se réduit à l' algorithme glouton , qui ne fait que les transitions en descente. ${\style d'affichage T}$${\displaystyle P(e,e_{\mathrm {nouveau} },T)}$${\displaystyle e_{\mathrm {nouveau} }>e}$${\style d'affichage T}$${\style d'affichage T=0}$

Dans la description originale du recuit simulé, la probabilité était égale à 1 lorsque — c'est-à-dire que la procédure descendait toujours lorsqu'elle trouvait un moyen de le faire, quelle que soit la température. De nombreuses descriptions et implémentations de recuit simulé prennent encore cette condition dans le cadre de la définition de la méthode. Cependant, cette condition n'est pas indispensable pour que la méthode fonctionne. ${\displaystyle P(e,e_{\mathrm {nouveau} },T)}$${\displaystyle e_{\mathrm {nouveau} }<e}$

La fonction est généralement choisie de sorte que la probabilité d'accepter un mouvement diminue lorsque la différence augmente, c'est-à-dire que les petits mouvements en montée sont plus probables que les grands. Cependant, cette exigence n'est pas strictement nécessaire, à condition que les exigences ci-dessus soient remplies. ${\style d'affichage P}$${\displaystyle e_{\mathrm {nouveau} }-e}$

Compte tenu de ces propriétés, la température joue un rôle crucial dans le contrôle de l'évolution de l'état du système au regard de sa sensibilité aux variations d'énergies du système. Pour être précis, pour une grande , l'évolution de est sensible à des variations d'énergie plus grossières, alors qu'elle est sensible à des variations d'énergie plus fines lorsqu'elle est petite. ${\style d'affichage T}$${\style d'affichage s}$${\style d'affichage T}$${\style d'affichage s}$${\style d'affichage T}$

Le programme de recuit

Rapide

Lent

Exemple illustrant l'effet du programme de refroidissement sur les performances du recuit simulé. Le problème est de réorganiser les pixels d'une image de manière à minimiser une certaine fonction d' énergie potentielle , ce qui fait que des couleurs similaires s'attirent à courte distance et se repoussent à une distance légèrement plus grande. Les mouvements élémentaires permutent deux pixels adjacents. Ces images ont été obtenues avec un programme de refroidissement rapide (à gauche) et un programme de refroidissement lent (à droite), produisant des résultats similaires aux solides amorphes et cristallins , respectivement.

Le nom et l'inspiration de l'algorithme exigent une caractéristique intéressante liée à la variation de température à intégrer dans les caractéristiques opérationnelles de l'algorithme. Cela nécessite une réduction progressive de la température au fur et à mesure de la simulation. L'algorithme commence initialement avec une valeur élevée (ou l'infini), puis il est diminué à chaque étape suivant un programme de recuit - qui peut être spécifié par l'utilisateur, mais doit se terminer vers la fin du budget temporel alloué. De cette manière, le système est censé errer initialement vers une large région de l'espace de recherche contenant de bonnes solutions, ignorant les petites caractéristiques de la fonction d'énergie ; dérivent ensuite vers des régions de basse énergie qui deviennent de plus en plus étroites ; et enfin descendre selon l' heuristique de descente la plus raide . ${\style d'affichage T}$${\style d'affichage T=0}$

Pour tout problème fini donné, la probabilité que l'algorithme de recuit simulé se termine par une solution optimale globale approche 1 à mesure que le programme de recuit est étendu. Ce résultat théorique, cependant, n'est pas particulièrement utile, puisque le temps nécessaire pour assurer une probabilité de succès significative dépassera généralement le temps nécessaire pour une recherche complète de l' espace des solutions .

Pseudocode

Le pseudocode suivant présente l'heuristique de recuit simulé comme décrit ci-dessus. Il part d'un état s ₀ et se poursuit jusqu'à ce qu'un maximum de k étapes _max aient été franchies. Dans le procédé, l'appel voisin ( s ) doit générer un voisin choisi au hasard d'un état donné s ; l'appel random(0, 1) doit choisir et renvoyer une valeur dans la plage [0, 1] , uniformément au hasard . Le programme de recuit est défini par la température d' appel ( r ) , qui devrait donner la température à utiliser, étant donné la fraction r du budget temps qui a été dépensé jusqu'à présent.

Sélection des paramètres

Afin d'appliquer la méthode de recuit simulé à un problème spécifique, il faut spécifier les paramètres suivants : l'espace d'état, la fonction énergie (objectif) E(), la procédure du générateur candidat neighbour(), la fonction de probabilité d'acceptation P()et le programme de recuit temperature()ET température initiale <init temp>. Ces choix peuvent avoir un impact significatif sur l'efficacité de la méthode. Malheureusement, il n'y a pas de choix de ces paramètres qui conviendront à tous les problèmes, et il n'y a pas de moyen général de trouver les meilleurs choix pour un problème donné. Les sections suivantes donnent quelques directives générales.

Voisin suffisamment proche

Le recuit simulé peut être modélisé comme une marche aléatoire sur un graphe de recherche, dont les sommets sont tous les états possibles, et dont les arêtes sont les mouvements candidats. Une exigence essentielle pour la neighbour()fonction est qu'elle doit fournir un chemin suffisamment court sur ce graphe de l'état initial à tout état qui peut être l'optimum global - le diamètre du graphe de recherche doit être petit. Dans l'exemple du voyageur de commerce ci-dessus, par exemple, l'espace de recherche pour n = 20 villes a n ! = 2 432 902 008 176 640 000 États (2,4 quintillions) ; pourtant le nombre de voisins de chaque sommet est des arêtes (venant de n choisir 2), et le diamètre du graphe est . ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$${\style d'affichage n-1}$

Probabilités de transition

Pour étudier le comportement du recuit simulé sur un problème particulier, il peut être utile de considérer les probabilités de transition qui résultent des différents choix de conception effectués dans la mise en œuvre de l'algorithme. Pour chaque arête du graphe de recherche, la probabilité de transition est définie comme la probabilité que l'algorithme de recuit simulé passe à l'état lorsque son état actuel est . Cette probabilité dépend de la température actuelle spécifiée par , de l'ordre dans lequel les mouvements candidats sont générés par la fonction et de la fonction de probabilité d'acceptation . (Notez que la probabilité de transition n'est pas simplement , car les candidats sont testés en série.) ${\style d'affichage (s,s')}$${\style d'affichage s'}$${\style d'affichage s}$temperature()neighbour()P()${\style d'affichage P(e,e',T)}$

Probabilités d'acceptation

La spécification de neighbour(), P(), et temperature()est partiellement redondante. En pratique, il est courant d'utiliser la même fonction d'acceptation P()pour de nombreux problèmes et d'ajuster les deux autres fonctions en fonction du problème spécifique.

Dans la formulation de la méthode par Kirkpatrick et al., la fonction de probabilité d'acceptation a été définie comme 1 si , et sinon. Cette formule se justifiait superficiellement par analogie avec les transitions d'un système physique ; il correspond à l' algorithme de Metropolis–Hastings , dans le cas où T=1 et la distribution de proposition de Metropolis–Hastings est symétrique. Cependant, cette probabilité d'acceptation est souvent utilisée pour le recuit simulé même lorsque la fonction, qui est analogue à la distribution proposée dans Metropolis-Hastings, n'est pas symétrique, ou pas du tout probabiliste. En conséquence, les probabilités de transition de l'algorithme de recuit simulé ne correspondent pas aux transitions du système physique analogue, et la distribution à long terme des états à une température constante n'a pas besoin de ressembler à la distribution d'équilibre thermodynamique sur les états de ce système physique, à n'importe quelle température. Néanmoins, la plupart des descriptions de recuit simulé supposent la fonction d'acceptation d'origine, qui est probablement codée en dur dans de nombreuses implémentations de SA. ${\style d'affichage P(e,e',T)}$${\style d'affichage e'<e}$${\displaystyle \exp(-(e'-e)/T)}$neighbour()${\style d'affichage T}$

En 1990, Moscato et Fontanari, et indépendamment Dueck et Scheuer, ont proposé qu'une mise à jour déterministe (c'est-à-dire non basée sur la règle d'acceptation probabiliste) puisse accélérer le processus d'optimisation sans impacter la qualité finale. Moscato et Fontanari concluent de l'observation de l'analogue de la courbe de "chaleur spécifique" du recuit "d'actualisation de seuil" provenant de leur étude que "la stochasticité de l'actualisation de Metropolis dans l'algorithme de recuit simulé ne joue pas un rôle majeur dans la recherche de -minimums optimaux". Au lieu de cela, ils ont proposé que "le lissage du paysage de la fonction de coût à haute température et la définition progressive des minima pendant le processus de refroidissement sont les ingrédients fondamentaux du succès du recuit simulé". La méthode s'est ensuite popularisée sous la dénomination de "seuil d'acceptation" en raison de la dénomination de Dueck et Scheuer. En 2001, Franz, Hoffmann et Salamon ont montré que la stratégie de mise à jour déterministe est en effet la meilleure au sein de la grande classe d'algorithmes qui simulent une marche aléatoire sur le paysage coût/énergie.

Génération efficace de candidats

Lors du choix du générateur candidat neighbour(), il faut considérer qu'après quelques itérations de l'algorithme de recuit simulé, l'état actuel devrait avoir une énergie beaucoup plus faible qu'un état aléatoire. Par conséquent, en règle générale, il faut incliner le générateur vers les mouvements candidats où l'énergie de l'état de destination est susceptible d'être similaire à celle de l'état actuel. Cette heuristique (qui est le principe de base de l' algorithme de Metropolis-Hastings ) a tendance à exclure les "très bons" coups candidats ainsi que les "très mauvais" ; cependant, les premiers sont généralement beaucoup moins courants que les seconds, de sorte que l'heuristique est généralement assez efficace. ${\style d'affichage s'}$

Dans le problème du voyageur de commerce ci-dessus, par exemple, l'échange de deux villes consécutives dans un circuit à faible consommation d'énergie devrait avoir un effet modeste sur son énergie (durée) ; alors que l'échange de deux villes arbitraires est beaucoup plus susceptible d'augmenter sa longueur que de la diminuer. Ainsi, on s'attend à ce que le générateur de voisin à échange consécutif fonctionne mieux que celui à échange arbitraire, même si ce dernier pourrait fournir un chemin un peu plus court vers l'optimum (avec des échanges, au lieu de ). ${\style d'affichage n-1}$${\style d'affichage n(n-1)/2}$

Une déclaration plus précise de l'heuristique est que l'on devrait essayer d'abord les états candidats pour lesquels est grand. Pour la fonction d'acceptation "standard" ci-dessus, cela signifie qu'elle est de l'ordre de ou moins. Ainsi, dans l'exemple du voyageur de commerce ci-dessus, on pourrait utiliser une fonction qui échange deux villes aléatoires, où la probabilité de choisir une paire de villes s'annule à mesure que leur distance augmente au-delà de . ${\style d'affichage s'}$${\style d'affichage P(E(s),E(s'),T)}$${\style d'affichage P}$${\style d'affichage E(s')-E(s)}$${\style d'affichage T}$neighbour()${\style d'affichage T}$

Évitement des barrières

Lors du choix du générateur candidat, neighbour()il faut également essayer de réduire le nombre de minima locaux "profonds" - états (ou ensembles d'états connectés) qui ont une énergie beaucoup plus faible que tous ses états voisins. De tels « bassins versants fermés » de la fonction énergie peuvent piéger l'algorithme de recuit simulé avec une probabilité élevée (à peu près proportionnelle au nombre d'états dans le bassin) et pendant un temps très long (à peu près exponentiel sur la différence d'énergie entre les états environnants et le fond du bassin).

En règle générale, il est impossible de concevoir un générateur candidat qui satisfera cet objectif et priorisera également les candidats ayant une énergie similaire. D'un autre côté, on peut souvent améliorer considérablement l'efficacité du recuit simulé par des modifications relativement simples du générateur. Dans le problème du voyageur de commerce, par exemple, il n'est pas difficile d'exposer deux tournées , , avec des longueurs presque égales, telles que (1) est optimale, (2) chaque séquence d'échanges de paires de villes qui se convertit en passe par des tournées qui sont beaucoup plus long que les deux, et (3) peut être transformé en en retournant (inversant l'ordre de) un ensemble de villes consécutives. Dans cet exemple, et se situent dans des « bassins profonds » différents si le générateur n'effectue que des échanges de paires aléatoires ; mais ils seront dans le même bassin si le générateur effectue des retournements de segment aléatoires. ${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$${\style d'affichage A}$${\style d'affichage B}$

Programme de refroidissement

L'analogie physique utilisée pour justifier le recuit simulé suppose que la vitesse de refroidissement est suffisamment faible pour que la distribution de probabilité de l'état actuel soit proche de l'équilibre thermodynamique à tout moment. Malheureusement, le temps de relaxation — le temps qu'il faut attendre pour que l'équilibre se rétablisse après un changement de température — dépend fortement de la « topographie » de la fonction énergétique et de la température actuelle. Dans l'algorithme de recuit simulé, le temps de relaxation dépend également du générateur candidat, de manière très compliquée. Notez que tous ces paramètres sont généralement fournis sous forme de fonctions de boîte noire à l'algorithme de recuit simulé. Par conséquent, la vitesse de refroidissement idéale ne peut pas être déterminée à l'avance et doit être ajustée empiriquement pour chaque problème. Les algorithmes de recuit simulé adaptatif résolvent ce problème en connectant le programme de refroidissement à la progression de la recherche. Une autre approche adaptative comme le recuit simulé thermodynamique, ajuste automatiquement la température à chaque étape en fonction de la différence d'énergie entre les deux états, selon les lois de la thermodynamique.

Redémarre

Parfois, il est préférable de revenir à une solution qui était nettement meilleure plutôt que de toujours quitter l'état actuel. Ce processus est appelé redémarrage du recuit simulé. Pour ce faire , nous avons mis set eà sbestet ebestpeut - être redémarrer le calendrier de recuit. La décision de redémarrer pourrait reposer sur plusieurs critères. Parmi ceux-ci, citons le redémarrage basé sur un nombre fixe d'étapes, selon que l'énergie actuelle est trop élevée par rapport à la meilleure énergie obtenue jusqu'à présent, le redémarrage aléatoire, etc.

Méthodes associées

• Les algorithmes Interacting Metropolis-Hasting (alias Sequential Monte Carlo ) combinaient des mouvements de recuit simulés avec une acceptation-rejet des individus les mieux adaptés équipés d'un mécanisme de recyclage interactif.
• Le recuit quantique utilise des "fluctuations quantiques" au lieu de fluctuations thermiques pour traverser des barrières hautes mais minces dans la fonction cible.
• L'effet tunnel stochastique tente de surmonter la difficulté croissante des essais de recuit simulé à s'échapper des minima locaux lorsque la température diminue, en passant par des barrières.
• La recherche Tabou se déplace normalement vers des états voisins d'énergie inférieure, mais prendra des mouvements ascendants lorsqu'elle se trouvera bloquée dans un minimum local ; et évite les cycles en gardant une "liste taboue" des solutions déjà vues.
• L'évolution à double phase est une famille d'algorithmes et de processus (à laquelle appartient le recuit simulé) qui assurent la médiation entre la recherche locale et globale en exploitant les changements de phase dans l'espace de recherche.
• L'optimisation de la recherche réactive se concentre sur la combinaison de l'apprentissage automatique et de l'optimisation, en ajoutant une boucle de rétroaction interne pour ajuster automatiquement les paramètres libres d'un algorithme aux caractéristiques du problème, de l'instance et de la situation locale autour de la solution actuelle.
• Les algorithmes génétiques maintiennent un pool de solutions plutôt qu'une seule. De nouvelles solutions candidates sont générées non seulement par "mutation" (comme dans SA), mais aussi par "recombinaison" de deux solutions du pool. Des critères probabilistes, similaires à ceux utilisés en SA, sont utilisés pour sélectionner les candidats à la mutation ou à la combinaison, et pour éliminer les solutions en excès du pool.
• Les algorithmes mémétiques recherchent des solutions en utilisant un ensemble d'agents qui coopèrent et rivalisent dans le processus ; parfois, les stratégies des agents impliquent des procédures de recuit simulé pour obtenir des solutions de haute qualité avant de les recombiner. Le recuit a également été suggéré comme mécanisme pour augmenter la diversité de la recherche.
• L'optimisation graduée "lisse" progressivement la fonction cible tout en optimisant.
• L'optimisation des colonies de fourmis (ACO) utilise de nombreuses fourmis (ou agents) pour traverser l'espace de solution et trouver des zones localement productives.
• La méthode d'entropie croisée (CE) génère des solutions candidates via une distribution de probabilité paramétrée. Les paramètres sont mis à jour via la minimisation de l'entropie croisée, afin de générer de meilleurs échantillons à l'itération suivante.
• La recherche d'harmonie imite les musiciens dans un processus d'improvisation où chaque musicien joue une note pour trouver ensemble la meilleure harmonie.
• L'optimisation stochastique est un ensemble de méthodes qui comprend le recuit simulé et de nombreuses autres approches.
• L'optimisation de l'essaim de particules est un algorithme modélisé sur l'intelligence de l'essaim qui trouve une solution à un problème d'optimisation dans un espace de recherche, ou modélise et prédit le comportement social en présence d'objectifs.
• L'algorithme runner-root (RRA) est un algorithme d'optimisation méta-heuristique pour résoudre des problèmes unimodales et multimodaux inspirés par les coureurs et les racines des plantes dans la nature.
• Algorithme intelligent de gouttes d'eau (IWD) qui imite le comportement des gouttes d'eau naturelles pour résoudre les problèmes d'optimisation
• La trempe parallèle est une simulation de copies de modèles à différentes températures (ou hamiltoniens ) pour surmonter les barrières potentielles.
• Le recuit simulé multiobjectif a été conçu pour des problèmes ( optimisation multi-objectifs ) et peut probablement en résoudre certains avec plus de fonctions objectives que d'autres stratégies.

Voir également

Les références

Lectures complémentaires

• A. Das et BK Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods , Note de cours en physique, Vol. 679, Springer, Heidelberg (2005)
• Weinberger, E. (1990). « Paysages de fitness corrélés et non corrélés et comment faire la différence ». Cybernétique biologique . 63 (5) : 325-336. doi : 10.1007/BF00202749 . S2CID  851736 .
• Appuyez sur, WH; Teukolsky, SA; Vetterling, WT ; Flannery, BP (2007). "Section 10.12. Méthodes de recuit simulé" . Recettes numériques : L'art de l'informatique scientifique (3e éd.). New York : Cambridge University Press. ISBN 978-0-521-88068-8.
• Strobl, MAR; Barker, D. (2016). "Sur les transitions de phase de recuit simulé dans la reconstruction phylogénétique" . Phylogénétique moléculaire et évolution . 101 : 46-55. doi : 10.1016/j.ympev.2016.05.001 . PMC  4912009 . PMID  27150349 .
• V.Vassilev, A.Prahova : "L'utilisation du recuit simulé dans le contrôle des systèmes de fabrication flexibles", International Journal THÉORIES ET APPLICATIONS DE L'INFORMATION, VOLUME 6/1999

Liens externes

• Recuit simulé Une application Javascript qui vous permet d'expérimenter le recuit simulé. Code source inclus.
• "General Simulated Annealing Algorithm" Un programme MATLAB open source pour des exercices généraux de recuit simulé.
• Leçon autoguidée sur le recuit simulé Un projet de Wikiversité.
• Google en superposition de l'utilisation et non de l'utilisation de l'ordinateur quantique Ars Technica discute de la possibilité que l'ordinateur D-Wave utilisé par Google puisse, en fait, être un coprocesseur de recuit simulé efficace.
• [1] Un algorithme d'optimisation multiobjectif basé sur le recuit simulé : AMOSA.