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. T0 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.