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 s_{i};
t := T_{0}; //initial temperature
REPEAT
REPEAT
choose neighbor state s_{j}
compute DeltaC = C(s_{i}) - C(s_{j});
IF t^{DeltaC} > ran(0,1) THEN s_{i} := s_{j}
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_{0} 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.