A computational technique similar in some ways to
Monte Carlo Algorithms. Used to find the global
energy minimum of a system, by applying heat. To
anneal something is to heat it up and let it cool slowly.
Blacksmiths use this to reduce the grain size in forged iron - it works because the high temperature loosens everything up, and the slow cooling avoids trapping the structure in a higher energy state - or
local minimum. If the system is cooled
too rapidly (analagous to
quenching) it may not reach the lowest energy state.
To do this computationally, involves an annealing schedule; a sequence of times and temperatures. For example, a molecular dynamics simulation of a protein might involve heating to overcome energy barriers then cooling to trap the folded state. The rough algorithm goes as follows:
- Make a move and evaluate energy.
- If:
- Energy goes down -> Accept.
- Energy doesn't go down -> Reject if temperature is low.
- Reduce the temperature and go to (1).
The middle bit is the trickiest; it basically says that energetically poor moves can be accepted at high temperatures. As the temperature drops, the
probability that a bad move will be accepted falls - limiting the system to energy lowering manoevres.
Note that the algorithm below uses a
geometric annealing schedule (which is fast) rather than the theoretically better
logarithmic schedule (which is guarenteed not to get trapped, but is very sloooow). The logarithmic schedule is:
t := K / log(t)