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. Blacksmith
s 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 quench
ing) 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.
- 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)