Pseudocode
The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state s0 and continues to either a maximum of kmax steps or until a state with an energy of emax or less is found. In the process, the call neighbour(s) should generate a randomly chosen neighbour of a given state s; the call random should return a random value in the range . The annealing schedule is defined by the call temperature(r), which should yield the temperature to use, given the fraction r of the time budget that has been expended so far.
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count.
while k < kmax and e > emax // While time left & not good enough: T ← temperature(k/kmax) // Temperature calculation. snew ← neighbour(s) // Pick some neighbour. enew ← E(snew) // Compute its energy. if P(e, enew, T) > random then // Should we move to it? s ← snew; e ← enew // Yes, change state. if enew < ebest then // Is this a new best? sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'. k ← k + 1 // One more evaluation done
return sbest // Return the best solution found.
Pedantically speaking, the "pure" SA algorithm does not keep track of the best solution found so far: it does not use the variables sbest and ebest, it lacks the second if inside the loop, and, at the end, it returns the current state s instead of sbest. While remembering the best state is a standard technique in optimization that can be used in any metaheuristic, it does not have an analogy with physical annealing — since a physical system can "store" a single state only.
Even more pedantically speaking, saving the best state is not necessarily an improvement, since one may have to specify a smaller kmax in order to compensate for the higher cost per iteration and since there is a good probability that sbest equals s in the final iteration anyway. However, the step sbest ← snew happens only on a small fraction of the moves. Therefore, the optimization is usually worthwhile, even when state-copying is an expensive operation.
Read more about this topic: Simulated Annealing