Acceptance probability in the Simulated Annealing algorithm

Question

I am working on the Simulated Annealing algorithm, and I can't figure out why we choose to accept a configuration of higher energy with a probability $e^{- \Delta E / T}$.

I think I understand why we chose to accept some of these configurations (in order to avoid being stuck on a local minima, correct me if i am wrong)... But why this probability ?

I guess it has to do with Boltzmann distribution ($P(E) \propto e^{-E / T}$), but why are we dividing two of these probabilities in order to accept / reject a new configuration ?

Thanks in advance !

Answer 1

This is known as the Metropolis criterion and the algorithm that goes with it is called the Metropolis algorithm. And it allows the algorithm to escape from local minima when the temperature is high. It is known that, if the lowering of the temperature is sufficiently slow, the solid can reach thermal equilibrium at each temperature. In the Metropolis algorithm this is achieved by generating a large number of transitions at a given temperature value. And indeed, there is a link with the Boltzmann distribution, because thermal equilibrium is characterized by the Boltzmann distribution.

(edit) This gives the probability of the solid of being in a state $i$ with energy $E_i$ at temperature $T$ and which is given by $$ \frac{e^{\frac{-E_i}{k_bT}}}{\sum_{j}e^{\frac{-E_j}{k_bT}}} $$ (where $k_b$ is the Boltzmann constant)

From the original paper:

---

The probability that the configuration is accepted is $P(\Delta E) = e^{- \Delta E / T}$. Random numbers uniformly distributed in the interval $(0,1)$ are a convenient means of implementing the random part of the algorithm. One such number is selected and compared with $P(\Delta E)$. If it is less than $P(\Delta E)$, the new configuration is retained; if not, the original configuration is used to start the next step. By repeating the basic step many times, one simulates the thermal motion of atoms in thermal contact with a heat bath at temperature $T$. This choice of $P(\Delta E)$ has the consequence that the system evolves into a Boltzmann distribution.

---