There is an objective function to be minimized as usual. But the space over which the function must be minimized is very large and discrete, such as a combinatorial configuration space. Simulated annealing starts at a random initial points and tries random steps. It can even go uphill during the exploratory phase, but eventually the probability of going up is reduced to zero as if the temperature is reduced to zero and mo more fluctuations are possible.

The process changes the configuration from one with energy (ie, objective function) E₁ to another with energy E₂ with probability

where T is the temperature. This is analogous to the Boltzmann probability for physical systems (with the Boltzmann constant k set to 1).

To implement the algorithm one needs

• an encoding of the possible configurations (physical states);
• a generator of random configuration changes;
• the objective function (energy);
• a way to control the temperature T.

Marco Corvi - Page hosted by geocities.com.