simulated annealing

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)

Simulated Annealing is a class of heuristic approaches to solving computationally intractable problems (ie, NP-Hard problems).

Below is a template for simulated annealing programs:

Start with initial state si;
t := T0;   //initial temperature

REPEAT
	REPEAT
		choose neighbor state sj
		compute DeltaC = C(si) - C(sj); 
		IF tDeltaC > ran(0,1) THEN si := sj 
	UNTIL equilibrium();

	t := alpha * t; //reduce temperature
UNTIL frozen();

The important bits here are: C() which is a "cost function" that evaluates how good a given solution is. equilibrium() determines how long the SA runs at a given temperature. T₀ is the initial temperature, while alpha is a value that decreases the temperature at every iteration.

Simulated annealing is similar to Hill Climbing approaches in that it is a local search strategy. However, unlike hill climbing (also called Directed Walk), simulated annealing allows you to "escape" local optima.

---

Reference: Distributed Combinatorial Optimization, Diekman et al.

In the biosciences, this refers to using computers to model how complementary strands of DNA or RNA will link via hydrogen bonds to form a double-stranded molecule, or how a protein sequence will fold up and make hydrogen bonds with itself to form a more convoluted molecule.

---

From the BioTech Dictionary at http://biotech.icmb.utexas.edu/. For further information see the BioTech homenode.

Consider, if you will, a duck in a thunderstorm. Now this particular duck can't fly and doesn't really want to swim, so as the rain pours down and the water level starts to rise the duck starts walking up the nearest hill. Eventually the duck reaches a plateau and somebody comes along and gives the duck a kick and that's simulated annealing.

(Paraphrased from Rhys Price-Jones' computer algorithms class)