Simulated Annealing (SA) is a stochastic relaxation technique, which has its origin in statistical mechanics. It is based on an analogy from 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 be able to 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 ${\Delta \le 0}$, where ${\Delta = f(x) – f(x_{i})}$. To allow the search to escape a local optimum, moves that increase the objective function value are accepted with a probability ${e^{-\Delta / T}}$ if ${\Delta > 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, and temperature values at each stage of the algorithm.
At iteration ${t}$ of Simulated Annealing, a solution ${x}$ is drawn randomly in ${N(x_{i})}$. If ${f(x) \le f(x_{i})}$, then ${x_{i+1}}$ is set equal to ${x}$; otherwise
$${x_{i+1}=\begin{cases}
x & \text{\text{with probability }}p_{i}\\
x_{i} & \text{with probability }1-p_{i}
\end{cases}
}$$
where ${p_{i}}$ is usually a decreasing function of ${t}$ and of ${f(x) – f(x_{i})}$. It is common to define ${p_{i}}$ as ${e^{-\Delta / T}}$.
There are three common stopping criteria:
- The value ${f^{*}}$ of the incumbent ${x^{*}}$ has not decreased by at least ${\pi_{1}\%}$ for at least ${k_{1}}$ consecutive cycle of ${T}$ iterations;
- The number of accepted moves has been less than ${\pi_{2}\%}$ of ${T}$ for ${k_{2}}$ consecutive cycles of ${T}$ iterations;
- ${k_{3}}$ of ${T}$ iterations have been executed.