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:

  1. Make a move and evaluate energy.
  2. If:
    • Energy goes down -> Accept.
    • Energy doesn't go down -> Reject if temperature is low.
  3. 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)