Simulated Annealing

Simulated Annealing is a heuristic that uses probability to determine a solution. It approximates the global optimum (the best solution), in a reasonable amount of time. Its name comes from metallurgy, in which metals are heating to high temperatures, then cooled, in a process called annealing.

The process works as follows:

1. Generate a random solution.
2. Calculate its cost using a cost function, $c(x)$
3. Generate a random neighbouring (adjacent) solution.
4. Calculate the new solution’s cost using $c(x$)
5. Compare solutions:
   1. f c(new) < c(old) and temperature permits, move to the new solution.
   2. If c(new) > c(old) and temperature permits, maybe move to the new solution.
6. Repeat steps 3–4 until an acceptable solution is found or you reach some maximum number of iterations

Pseudocode §

ALGORITHM SimulatedAnnealing(temp, iterations):
	solution ← Randomly Generated Solution
	c() ←  Cost Function
	For i from 1 to iterations do:
		solution* ← Adjacent solution, generated randomly
		delta ←  c(solution*) - c(solution)
		pr ←  e^(-delta/temp) #e being euler's constant
		If pr > random_value between 0 and 1 then:
			solution ← solution*
		End if
		t ← 0.9 * t #The cooling can be any formula
	End do
	return solution, c(solution)
End Algorithm