Recuit simuléL'algorithme est un algorithme probabiliste général utilisé pour trouver la solution optimale à une proposition dans un grand espace de recherche.

principe

En appliquant la théorie de la thermodynamique aux statistiques, imaginez chaque point de l’espace de recherche comme une molécule dans l’air ; l'énergie d'une molécule est sa propre énergie cinétique ; et chaque point dans l'espace de recherche, comme une molécule d'air, transporte de « l'énergie » pour indiquer le degré d'adéquation du point à la proposition.

L'algorithme démarre avec un point arbitraire dans l'espace de recherche : à chaque étape, un « voisin » est sélectionné puis la probabilité d'atteindre le « voisin » à partir de la position actuelle est calculée.

Éléments de base

Espace d'état et fonction de génération d'état

1) L'espace de recherche est également appelé espace d'état, qui se compose de l'ensemble des solutions réalisables codées.

2) La fonction de génération d'état (fonction de voisinage) doit garantir que les solutions candidates générées sont réparties autant que possible sur l'ensemble de l'espace de solutions. Il se compose généralement de deux parties, à savoir la méthode de génération de solutions candidates et la distribution de probabilité des solutions candidates.

3) Les solutions candidates sont généralement obtenues en échantillonnant aléatoirement l'espace de solutions selon une certaine fonction de densité de probabilité.

4) La distribution de probabilité peut être une distribution uniforme, une distribution normale, une distribution exponentielle, etc. 

Probabilité de transition d'état

1) La probabilité de transition d’état fait référence à la probabilité de transition d’un état à un autre.

2) La compréhension commune est la probabilité d’accepter une nouvelle solution comme solution actuelle.

3) Il est lié au paramètre de température actuel T et diminue à mesure que la température baisse.

4) Le critère de la métropole est généralement adopté.

Critères de terminaison de la boucle interne

1) Vérifiez si la moyenne de la fonction objective est stable.

2) La valeur cible change légèrement sur plusieurs étapes consécutives.

3) Échantillonnage selon un certain nombre d'étapes.

Critères de terminaison de la boucle externe

1) Définissez le seuil de température de terminaison.

2) Définissez le nombre d'itérations de la boucle externe.

3) La valeur optimale recherchée par l’algorithme reste inchangée pendant plusieurs étapes consécutives.

4) Vérifiez si l’entropie du système est stable.

Étapes clés

Nouvelle fonction de génération d'état → Nouvelle fonction d'acceptation d'état → Critère de stabilité d'échantillonnage → Fonction de refroidissement → Critère de fin de recuit

Avantages du recuit simulé

L'algorithme de recuit simulé peut trouver rapidement la solution optimale approximative au problème. Sous réserve d’un paramétrage approprié, l’algorithme de recuit simulé présente une efficacité de recherche élevée.

Mots apparentés : algorithme d'optimisation