Solution Techniques

Simulated Annealing

Simulated Annealing (SA) is a stochastic relaxation technique, which has its origin in statistical mechanics. It is based on an analogy with the annealing process of solids, where a solid is heated to a high temperature and gradually cooled in order for it to crystallize in a low energy configuration. SA can be seen as one way of trying to allow the basic dynamics of hill-climbing to also escape local optima of poor solution quality. SA guides the original local search method in the following way. The solution S′ is accepted as the new current solution if $Δ ≤ 0$ , where $Δ = f(S′) − f(S)$ . To allow the search to escape a local optimum, moves that increase the objective function value are accepted with a probability $e^(−Δ/T)$ if $Δ > 0$ , where T is a parameter called the "temperature". The value of T varies from a relatively large value to a small value close to zero. These values are controlled by a cooling schedule, which specifies the initial temperature and the temperature values at each stage of the algorithm.

At iteration t of Simulated Annealing, a solution x is drawn randomly in $N(x(t))$ . If $f(x) < f(x(t))$ , then $x(t+1)$ is set equal to x; otherwise

$acceptance rule formula$

where $p(t)$ is usually a decreasing function of t and of $f(x) − f(x(t))$ . It is common to define $p(t)$ as $e^(−Δ/T)$ .

There are three common stopping criteria:

The value $f$ of the incumbent $x*$ has not decreased by at least $ε1$ for at least $k1$ consecutive cycles of T iterations;
The number of accepted moves has been less than $ε2$ of T for $k2$ consecutive cycles of T iterations;
$k3$ of T iterations have been executed.