14
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Initial temperature has a lot to do with the problem domain and other parameters you are using for the gradient descent part of the algorithm. Can you give more context? $\endgroup$ – dhj Apr 8 '13 at 4:16
9
$\begingroup$

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{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}

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 \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{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 explantion, 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.

$\endgroup$
3
$\begingroup$

this is a very advanced topic related to getting very tight optimums. my understanding, the initial temperature is generally considered part of a "temperature schedule" strategy for which there is some deep research. in other words both the initial temperature condition and the temperature decay algorithm (which you dont mention) affect the overall optimization results. simple strategies or heuristics for both often yield good or "good enough" results.

there is however at least one paper that studies the initial temperature alone.[1] the bottom line is that unless you are doing very advanced work, treating the initial temperature as a parameter of the problem and iterating over different initial temperatures as part of the overall optimization [after finding that it does indeed affect results] is a very reasonable and a probably widespread practice.

or, even just choosing an initial temperature that gives good results is also common (it would seem to be somewhat surprising & not be often that problem instance optimization results vary substantially from a "better" initial temperature parameter found by trial-and-error). as dhj pointed out some problems will be more sensitive than others to initial temperature.

[1] Computing the Initial Temperature of Simulated Annealing Ben-Ameur 2004

[2] An Efficient Simulated Annealing Schedule: Derivation Lam & Delosme

[3] Temperature control for simulated annealing Munakata & Nakamura

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.