The simulated-annealing algorithm

Figure 4.5: Minimization by Simulated-annealing algorithm of a function $\sim x^4$: 130 steps.

Figure 4.6: Minimization by Simulated-annealing algorithm of a function $\sim x^6$: 200 steps.

The name of this algorithm comes from an analogy with thermodynamics: it is known that if a slow cooling is applied to a liquid, the this liquid freezes naturally to a state of minimum energy. This process is called annealing.
The numerical algorithm applies this analogy to the minimization of function: first go downhill to a minimum as far as it can go, then go slightly uphill, since the minimum just fond could be a local minimum, then again, go downhill, and so on. In thermodynamics, the probability to go from a state with energy $E_1$ to a state of energy $E_2$ is given by:

$$p=e^{\frac{-(E_1-E_2)}{kT}},$$

where $k$ is the Boltzmann constant and $T$ is the temperature of the system.

In order to apply this scheme to a function minimization, it is necessary to define the energy of the system (i.e. the objective function), the temperature of the system, and an annealing schedule (i.e. the scheduled number of annealing iterations): at each iteration the temperature defines a random fluctuation in the minimum found, to simulate the thermal fluctuations of the atoms. Also, at each iteration the temperature is decreased, to reduce the thermal fluctuations and converging, thus, to the global minimum.
The rate of the diminution of the temperature influences the rate of convergence (higher rate temperature, higher rate of convergence), but also influences the quality of the minimum (lower rate temperature, higher the probability to converge to a global minimum).
As an example, a possible annealing schedule (probably the simpler) would be: after $k$ steps, reduce the temperature $T$ by $T=(1-\epsilon )T$, where $\epsilon$ is determined by experiment.

The same function of figures 4.2, 4.3 are shown in figures 4.5, 4.6, minimized by the simulated annealing algorithm. As in the case of Powell algorithm, the simulated annealing it is not fooled by the presence of local minima, but the number of iterations is greater for both the functions: $130$ in the first case, $200$ in the second one.