Initial temperature in simulated annealing algorithm - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-24T16:10:23Z https://cs.stackexchange.com/feeds/question/11126 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/11126 14 Initial temperature in simulated annealing algorithm Undefined https://cs.stackexchange.com/users/7636 2013-04-08T01:23:34Z 2013-04-09T23:24:51Z <p>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.</p> <p>Is there any way of calculating a good initial temperature?</p> https://cs.stackexchange.com/questions/11126/-/11152#11152 3 Answer by vzn for Initial temperature in simulated annealing algorithm vzn https://cs.stackexchange.com/users/699 2013-04-09T04:27:01Z 2013-04-09T04:35:35Z <p>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.</p> <p>there is however at least one paper that studies the initial temperature alone. 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. </p> <p>or, even just choosing an initial temperature that gives good results is also common (it would seem to be somewhat surprising &amp; 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.</p> <p> <a href="http://www.mendeley.com/catalog/computing-initial-temperature-simulated-annealing/" rel="nofollow">Computing the Initial Temperature of Simulated Annealing</a> Ben-Ameur 2004</p> <p> <a href="http://home.comcast.net/~jimmyklam/Lam-Delosme-8816.pdf" rel="nofollow">An Efficient Simulated Annealing Schedule: Derivation</a> Lam &amp; Delosme</p> <p> <a href="http://www.phys.cs.is.nagoya-u.ac.jp/~nakamura/Old/PDF/pre64_046127.pdf" rel="nofollow">Temperature control for simulated annealing</a> Munakata &amp; Nakamura</p> https://cs.stackexchange.com/questions/11126/-/11175#11175 9 Answer by Juho for Initial temperature in simulated annealing algorithm Juho https://cs.stackexchange.com/users/472 2013-04-09T23:24:51Z 2013-04-09T23:24:51Z <p>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 . 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 </p> <p>$$\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$. </p> <p>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:</p> <p>\begin{eqnarray} \hat{\chi}(T) &amp;=&amp; \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)|}} \\ &amp;=&amp; \dfrac{ \sum_{t \in S} \text{exp}(- E_{\max_t} / T) }{ \sum_{t \in S} \text{exp}(- E_{\min_t} / T) }. \end{eqnarray}</p> <p>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. </p> <p>$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 </p> <p>$$T_{n+1} = T_n \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{1/p}$$, where $p$ is a real number $\geq 1$. </p> <p>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 .</p> <hr> <p> Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.</p>