Issues of Local/Global Minimum

A main concern in optimization problems is whether the solution obtained by the algorithm is a local minimum or a global one. The simulated annealing (SA) algorithm is typically used to search for the global minimum in a high-dimensional space, by allowing up-hill moves in the iteration to avoid getting stuck by a local minimum. SA mimics the annealing process in metallurgy, in which the temperature is carefully controlled to decrease slowly so that the material reaches a state with minimum free energy.

The way the SA method avoids getting stuck at a local minimum is to allow the iteration steps to go up-hill. Specifically, the objective function $f({\bf x})$ evaluated at ${\bf x}_n$ is treated as the energy at ${\bf x}_n$ , and an up-hill move corresponding to an energy increase $\Delta E=f({\bf x}_{n+1})-f({\bf x}_n)_0$ can be accepted if some probability function is greater than a random threshold value $Th$ within a certain range comparable with $P$ :

$\displaystyle P(\Delta E, T)=e^{-\Delta E/T} > Th$

(171)

Obviously smaller $\Delta E$ and higher $T$

will cause higher $P$

, it is more probable for a move to be accepted.

During the entire search process, the temperature $T$ gradually reduces so that the probability of accepting an up-hill move also gradually reduces. In the early stage of the search, it is more probable to go up-hill, thereby getting out of a local minimum; but toward the later part of the search process, such a move is less likely to happen, as presumably in this late stage of the search, the energy level is already low, not likely to be at a local minimum with high energy level. Through out the search, the best result corresponding to he lowest energy level is always updated, to be returned as the final solution at the end of the process.

Further information can be found at wikipedia and mathworld.

A c program for AS can be found here.