Examples of simulated annealing in the 2010s
These are a few examples.
Analysis of Quote in the Question
The quote in the question is from page 125 of Artificial Intelligence: A Modern Approach, Stuart Russell and Peter Norvig, 2010, 3rd Edition.
The quote begins with the statement, "A hill-climbing algorithm that never makes 'downhill' moves toward states with lower value (or higher cost) is guaranteed to be incomplete," which is not strictly true. The stated guarantee has at least two important exceptions.
- The class of hills being climbed have only one peak
- The search is executed using parallel computing architecture scaled such that search granularity includes no more than one peak per processing unit
Describing simulated annealing using the analogy of combining inverted hill climbing and random walk, as Stuart and Norvig explains it, is not as clear and technically accurate as the original analogy. It is often better to find original sources of ideas and read them than to read simplified explanations. The original ideas may be just as easy or easier to understand than the textbook paraphrases (which is why the best textbooks simply quote the originating authors).
Source of the Term
The original algorithm termed simulated annealing is introduced in Optimization by Simulated Annealing, Kirkpatrick et. al.1, which may not qualify as one one explicitly employed by AI researchers or practitioners on a daily basis. Simulating the atomic motion of metals during annealing is the first of several approaches to injecting pseudo-random perturbations into convergence mechanisms. An approximation of a ${\chi}^2$ distribution with $k$ degrees of freedom is a more progressive injection source.
These approaches share the common goal of avoiding the mistaking of a local minimum in loss surface as its global minimum. Such mistaken conclusion causes a failure to achieve an optimal learning state according to the criteria the loss function represents.
As can be seen in the below excerpts, the original article is a good read and sets a foundation of understanding. Such a foundation will assist in understanding all methods used avoid local minima using stochastic injection.
Iterative improvement consists of a search in this coordinate space for
rearrangement steps which lead downhill. Since this search usually gets stuck in a local but not a global optimum, it is customary to carry out the process several times, starting from different randomly generated configurations, and save the best result.
...
Metropolis et al 2, in the earliest days of scientific computing, introduced a simple algorithm that can be used to provide an efficient simulation of a collection of atoms in equilibrium at a given temperature.
...
Random numbers uniformly distributed in the interval (0,l) are a convenient means of implementing the random part of the algorithm.
...
Using the cost function in place of the energy and defining configurations by a set of parameters {$x_i$}, it is straightforward with the Metropolis procedure to generate a population of configurations of a given optimization problem at some effective temperature. This temperature is simply a control parameter in the same units as the cost function. The simulated annealing process consists of first "melting" the system being optimized at a high effective temperature, then lowering the temperature by slow stages until the system "freezes" and no further changes occur.
...
Simulated annealing with Z-moves improved the random routing by 57 percent, averaging results for both x and y links.
References
[1] Optimization by Simulated Annealing, Science S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science New Series, Vol. 220, No. 4598, May 1983, pp. 671-680
[2] N. Metropolis, A. Rosenbluth, M. Rosenbluth., A. Teller. E. Teller, J. Chem. Phys. 21. 1087 110511