2
$\begingroup$

In AIMA, 3rd Edition on Page 125, Simulated Annealing is described as:

Hill-climbing algorithm that never makes “downhill” moves toward states with lower value (or higher cost) is guaranteed to be incomplete, because it can get stuck on a local maximum. In contrast, a purely random walk—that is, moving to a successor chosen uniformly at random from the set of successors—is complete but extremely inefficient. Therefore, it seems reasonable to try to combine hill climbing with a random walk in some way that yields both efficiency and completeness. Simulated annealing is such an algorithm. In metallurgy, annealing is the process used to temper or harden metals and glass by heating them to a high temperature and then gradually cooling them, thus allowing the material to reach a lowenergy crystalline state. To explain simulated annealing, we switch our point of view from hill climbing to gradient descent (i.e., minimizing cost) and imagine the task of getting a ping-pong ball into the deepest crevice in a bumpy surface. If we just let the ball roll, it will come to rest at a local minimum. If we shake the surface, we can bounce the ball out of the local minimum. The trick is to shake just hard enough to bounce the ball out of local minima but not hard enough to dislodge it from the global minimum. The simulated-annealing solution is to start by shaking hard (i.e., at a high temperature) and then gradually reduce the intensity of the shaking (i.e., lower the temperature)

I know its about its example, but I just want more examples where Stimulated Annealing used in daily life

Improve this question
$\endgroup$
1
  • $\begingroup$ Can you clarify which examples you already know so that answerers get a better idea of what other examples you might be looking for? $\endgroup$
    – Peeyush Kushwaha
    Dec 12, 2018 at 7:03

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

Simulated annealing is just one of the approaches for an optimization problem:

  • Given a function f(X), you want to find an X where f(X) is optimal (has maximum or minimum value).

Shaking (a methaphor for introducing a degree of randomness to annealing process) is used to prevent the algorithm from stopping prematurely, when only a sub-optimal solution (local minimum or local maximum) has been found.

I've once used it for finding the optimal schedule of lessons for teacher. The optimization function took into consideration "time windows" between windows, so that teachers do not have to wait too much.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .