Simulated Annealing

search

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.