patternModerate
Initial temperature in simulated annealing algorithm
Viewed 0 times
temperaturealgorithminitialsimulatedannealing
Problem
I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.
Is there any way of calculating a good initial temperature?
Is there any way of calculating a good initial temperature?
Solution
As noted by Thomas Klimpel in the comments, a certain acceptance probability is often used, which is equal to say $0.8$. The following is a simple iterative method to find a suitable initial temperature, proposed by Ben-Ameur in 2004 [1]. In the following, $t$ is a strictly positive transition, $\max_t$ and $\min_t$ are the states after and before the transition, $\delta_t$ the cost difference $E_{\max_t} - E_{\min_t}$ and $\pi_{\min_t} \dfrac{1}{|N(\min_t)|}$ the probability to generate a transition $t$ when the energy states are distributed in conformance with the stationary distribution
$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)},$$
where $N(i)$ denotes the set of neighbors of $i$.
Finally, $\text{exp}(-\delta_t/T)$ is the probability of accepting a positive transition $t$. Now, we can have an estimation $\hat{\chi}$ of the acceptance probability $\chi(T)$ based on a "random" set $S$ of positive transitions:
\begin{eqnarray}
\hat{\chi}(T)
&=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{\text{exp}(- \delta_t / T)}{|N(\min_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}
We want to find a temperature $T_0$ such that $\chi(T_0) = \chi_0$, where $\chi_0\in]0,1[$ is the acceptance probability we desire.
$T_0$ is computed by an iterative method. Some states and a neighbor for each state is generated. This gives us a set of transitions $S$. The energies $E_{\max_t}$ and $E_{\min_t}$ corresponding with the states of the subset $S$ are stored. Then a value for $T_1$ is chosen, which can be any positive value. $T_0$ is then found with the recursive formula
$$T_{n+1} = T_n \left(\dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}\right)^{1/p},$$
where $p$ is a real number $\geq 1$.
When $\hat{\chi}(T_n)$ gets close to $\chi_0$ we can stop. $T_n$ is now a good approximation of the wanted initial temperature $T_0$. For more explanation, proofs and discussion, please see the first section of the original paper [1].
[1] Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.
$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)},$$
where $N(i)$ denotes the set of neighbors of $i$.
Finally, $\text{exp}(-\delta_t/T)$ is the probability of accepting a positive transition $t$. Now, we can have an estimation $\hat{\chi}$ of the acceptance probability $\chi(T)$ based on a "random" set $S$ of positive transitions:
\begin{eqnarray}
\hat{\chi}(T)
&=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{\text{exp}(- \delta_t / T)}{|N(\min_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}
We want to find a temperature $T_0$ such that $\chi(T_0) = \chi_0$, where $\chi_0\in]0,1[$ is the acceptance probability we desire.
$T_0$ is computed by an iterative method. Some states and a neighbor for each state is generated. This gives us a set of transitions $S$. The energies $E_{\max_t}$ and $E_{\min_t}$ corresponding with the states of the subset $S$ are stored. Then a value for $T_1$ is chosen, which can be any positive value. $T_0$ is then found with the recursive formula
$$T_{n+1} = T_n \left(\dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}\right)^{1/p},$$
where $p$ is a real number $\geq 1$.
When $\hat{\chi}(T_n)$ gets close to $\chi_0$ we can stop. $T_n$ is now a good approximation of the wanted initial temperature $T_0$. For more explanation, proofs and discussion, please see the first section of the original paper [1].
[1] Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.
Context
StackExchange Computer Science Q#11126, answer score: 10
Revisions (0)
No revisions yet.