Initial temperature in simulated annealing algorithm
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) &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}

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.