Température initiale dans l'algorithme de recuit simulé

14

J'ai fait quelques tests de différentes températures initiales dans mon algorithme de recuit de simulation et j'ai remarqué que la température de départ a un effet sur les performances de l'algorithme.

Existe-t-il un moyen de calculer une bonne température initiale?

optimization artificial-intelligence heuristics Indéfini
la source

2

La température initiale a beaucoup à voir avec le domaine du problème et d'autres paramètres que vous utilisez pour la partie descente de gradient de l'algorithme. Pouvez-vous donner plus de contexte?

dhj

9

Comme l'a souligné Thomas Klimpel dans les commentaires, une certaine probabilité d'acceptation est souvent utilisée, qui est égale à . Voici une méthode itérative simple pour trouver une température initiale appropriée, proposée par Ben-Ameur en 2004 [1]. Dans ce qui suit, est une transition strictement positive, et sont les états après et avant la transition, la différence de coût et la probabilité de générer une transition lorsque les états d'énergie sont distribués conformément à la distribution stationnaire $0.8$ $t$ $\max_t$ $\min_t$ $\delta_t$ $E_{\max_t} - E_{\min_t}$ $\pi_{\min_t} \dfrac{1}{|N(\min_t)|}$ $t$

π_{i} = \frac{| N (i) | exp (- E_{i} / T)}{\sum_{j} | N (j) | \exp (- E_{j} / T)}

$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)}$ , où désigne l'ensemble des voisins de .

N (i)

$N(i)$

i

$i$

Enfin, est la probabilité d'accepter une transition positive . Maintenant, nous pouvons avoir une estimation de la probabilité d'acceptation basée sur un ensemble "aléatoire" de transitions positives: $\text{exp}(-\delta_t/T)$ $t$ $\hat{\chi}$ $\chi(T)$ $S$

\begin{array}{rcl} \hat{χ} (T) & = & \frac{\sum_{t \in S} π_{min_{t}} \frac{1}{| N (min_{t}) |} exp (- δ_{t} / T)}{\sum_{t \in S} π_{min_{t}} \frac{1}{| N (min_{t}) |}} \\ = & \frac{\sum_{t \in S} exp (- E_{max_{t}} / T)}{\sum_{t \in S} exp (- E_{min_{t}} / T)} . \end{array}

$\begin{eqnarray} \hat{\chi}(T) &=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|} \text{exp}(- \delta_t / T)}{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|}} \\ &=& \dfrac{ \sum_{t \in S} \text{exp}(- E_{\max_t} / T) }{ \sum_{t \in S} \text{exp}(- E_{\min_t} / T) }. \end{eqnarray}$

Nous voulons trouver une température telle que , où est la probabilité d'acceptation que nous désirons. $T_0$ $\chi(T_0) = \chi_0$ $\chi_0 \in ] 0,1 [$

$T_0$ est calculé par une méthode itérative. Certains états et un voisin pour chaque état sont générés. Cela nous donne un ensemble de transitions . Les énergies et correspondant aux états du sous-ensemble sont stockées. Ensuite, une valeur pour est choisie, qui peut être n'importe quelle valeur positive. est alors trouvé avec la formule récursive $S$ $E_{\max_t}$ $E_{\min_t}$ $S$ $T_1$ $T_0$

T_{n + 1} = T_{n} {\frac{\ln (\hat{χ} (T_{n}))}{\ln (χ_{0})}}^{1 / p}

$T_{n+1} = T_n \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{1/p}$ , où est un nombre réel .

p

$p$

\geq 1

$\geq 1$

Lorsque se rapproche de nous pouvons arrêter. est maintenant une bonne approximation de la température initiale souhaitée . Pour plus d'explications, de preuves et de discussions, veuillez consulter la première section de l'article original [1]. $\hat{\chi}(T_n)$ $\chi_0$ $T_n$ $T_0$

[1] Ben-Ameur, Walid. "Calcul de la température initiale du recuit simulé." Optimisation informatique et applications 29, no. 3 (2004): 369-385.

Juho
la source

3

il s'agit d'un sujet très avancé concernant l'obtention d'objectifs très serrés. à ma connaissance, la température initiale est généralement considérée comme faisant partie d'une stratégie de "programme de température" pour laquelle il y a des recherches approfondies. en d'autres termes, la condition de température initiale et l'algorithme de décroissance de la température (que vous ne mentionnez pas) affectent les résultats globaux d'optimisation. des stratégies ou des heuristiques simples donnent souvent des résultats bons ou «assez bons».

il existe cependant au moins un article qui étudie la température initiale seule. [1] l'essentiel est qu'à moins que vous ne fassiez un travail très avancé, le traitement de la température initiale comme paramètre du problème et l'itération sur différentes températures initiales dans le cadre de l'optimisation globale [après avoir constaté qu'elle affecte effectivement les résultats] est très raisonnable et une pratique probablement répandue.

ou, même simplement choisir une température initiale qui donne de bons résultats est également courant (il semblerait quelque peu surprenant et il n'est pas souvent que les résultats d'optimisation d'instance de problème varient considérablement d'un "meilleur" paramètre de température initiale trouvé par essais et erreurs) . comme l'a souligné dhj, certains problèmes seront plus sensibles que d'autres à la température initiale.

[1] Calcul de la température initiale de recuit simulé Ben-Ameur 2004

[2] Un calendrier de recuit simulé efficace: dérivation Lam & Delosme

[3] Contrôle de température pour recuit simulé Munakata & Nakamura

vzn
la source

voir aussi stackexchange crossvalidated

vzn

Température initiale dans l'algorithme de recuit simulé

Réponses: