Definition
Simulated Annealing
Simulated annealing is a modified version of hill-climbing that allows some “bad” moves to escape local extremes, but gradually decreases their size and frequency.
It corresponds to “cooling off” process of materials (value = energy , schedule of temperatures). See Boltzman distribution.
Pseudo Code
function SIMULATED-ANNEALING(problem, schedule) returns a solution state
current problem.INITIAL
for t = 1 to do
T schedule(t)
if T = 0 then return current
next a randomly selected successor of current
VALUE(current) - VALUE(next)
if then current next
else current next only with probability
Metropolis Criterion
The metropolis criterion is the criterion to determine whether a “bad” solution is accepted.
Let
- a the -th random number of a random number generator,
- denote the difference of quality between the current state and it’s successor / neighbouring state , and
- be the temperature at iteration .
If the following condition holds, the “bad” solution is accepted.
After an iteration , the temperature is updated , where is called the cooling factor.