Skip to main content
2 of 3
added 607 characters in body
Roger V.
  • 4.5k
  • 15
  • 35

From a physicist point of view simulated annealing seeks the most probable state of a system, described by the Boltzmann distribution: $$ w(p,q|T) \propto \exp\left( -\frac{H(p,q)}{T}\right) $$ where $H(p,q)$ is the Hamiltonian, also referred to as the energy of the system, whereas $T$ is temperature. Generalized momenta and coordinates, $p$ and $q$ are related via Hamiltonian evolution (heavily exploited, e.g., in the Hamiltonian Monte Carlo); these need not he continuous - e.g., they could by discrete up/down states of magnetic moments in ferromagnet or placement of atoms A and B in a binary alloy. MCMC is used to sample different variable configurations not connected via Hamiltonian evolution - physically it mostly means sampling states of different energies. This does not imply a gaussian proposal density and largely depends on the nature of the variables and the Hamiltonian.

The essential part is that at the temperature of interest, $T_0$ the system us likely to be found in its lowest energy state. Finding this state corresponds to maximizing the probability/likelihood $w(p,q|T_0)$.

In case of a multimodal likelihood we are not guaranteed to find the global maximum - physically it means that there may exist multiple global maxima (e g., corresponding to different directions of magnetization in a ferromagnet) or there may be some metastable/long-living "glass" states, the transitions from which to the global maximum are unlikely, since they require passing through highly improbable intermediate configurations.

As the probability of a state is proportional to $\exp\left( -\frac{H(p,q)}{T}\right)$, intermediate states are easier reached, if the temperature $T$ is higher. The solution is then to explore the energy states at a high temperature, and then use the result to redo the exploration at lower and lower temperature, till we reach the desired one.

Probabilistically, instead of exploring distribution $$p(x)\propto \exp\left(-l(x)\right),$$ we work with a rescaled negative log-probability $$p_\alpha(x)\propto \exp\left(-\alpha l(x)\right),\alpha \leq 1,$$ which is more easily amenable to exploration, e.g., via the Metropolis-Hastings algorithm.

One particular class of physical problems is particles undergoing diffusive/Langevin dynamic. These can be modeled as a random walk with a gaussian proposal density. They are referred to sometimes as drift-diffusion problems, but they are rather ubiquitous in science and may appear under many different names. The easy "physical" way of thinking of such systems is water on a rugged surface, which is being shaked. When the holes in the surface are deep, while the shaking is weak, the water remains where it is - the shaking explores only the surface near the minima. Shaking harder would allow the water to leak to other places. Annealing achieves it by rescaling the rugged landscape, allowing the water flow, and then gradually restoring the original size of the roughness.


References

  1. Simulated annealing: Theory and applications (1987) by Laarhoven and Aarts is an early book taking simulated annealing from physics domain to general statistical applications.
  2. Reaction rate: fifty years after Kramers (1990) by Hänggi et al. is a review article describing many physical, chemical and other systems, where diffusion-like dynamics leads to transitions between local energy minima (probability maxima).
Roger V.
  • 4.5k
  • 15
  • 35