0
$\begingroup$

I'm trying to wrap my head around it, but no matter what I read, I still can't fully understand it.
I tried to read a little bit about the annealing process in physics, but I have no background whatsoever in physics, let alone in thermodynamics, so I couldn't understand what is it exactly, and how it fits into the algorithm.
Here is the algorithm:

enter image description here

In the Hill Climbing algorithm, the reasoning can be easily described: Of all the successors of the current state - choose the highest-valued. But in Simulated Annealing... well, I can see what the algorithm does, I just don't understand the reasoning behind it:
1. It starts a timer.
2. It chooses a random successor.
3. It evaluates how "far away" the randomly chosen successor from current.
4. If the successor is indeed a "progress in the right direction" ($\Delta E > 0$) then we move ahead towards the direction of successor; otherwise, we move ahead towards the direction of successor with some (odd) probability that depends on the timer(?).

Why is randomly choosing a successor better then the Hill Climbing method?
Can someone please explain the reasoning behind it?
Do I really have to understand the annealing process? If so, can someone please explain it in layman terms?

$\endgroup$
  • $\begingroup$ What research and self-study have you done? The intuition behind simulated anneal is described in lots of resources, both textbooks and on the Internet -- not sure there's much point in repeating it here. P.S. We can't possibly answer "Do you really have to understand it?" -- ask your instructor. $\endgroup$ – D.W. Mar 28 '15 at 17:49
2
$\begingroup$

The variable $T$ is not a timer but the temperature. It starts very high, making it more likely that transitions are taken, and then slowly cools. It's called annealing due to the metallurgical technique of the same name.

Simulated annealing handles one problematic aspect of the hill climbing algorithm, namely that it can get stuck at a local optimum which is not a global optimum. Instead of getting stuck, simulated annealing offers a way out: if the proposed change only marginally deteriorates the objective function, then with some reasonable probability with make it anyway. This way we can escape local optima.

As the process proceeds, we increase the threshold of making unfavorable changes by decreasing the temperature; when the temperature is zero, simulated annealing is the same as hill climbing (and when the temperature is infinite, it is the same as a random walk). The idea is that at first we need to escape local optima more vigorously, but eventually we settle at a good solution which does not require as much tinkering with (except for hill climbing).

You mention that hill climbing always chooses the best neighbor, but this is only one version of the algorithm, and not necessarily the best one. In other versions we choose an improving neighbor in some other fashion. I don't have much intuition which approach is better, though you are right that choosing the best neighbor sounds like a reasonable heuristic.

$\endgroup$
  • $\begingroup$ Hey Yuval. Thanks again for the help. ;) So, the more time passed (and temperature drops), the more we are strict about choosing an improvement over deterioration? $\endgroup$ – so.very.tired Mar 28 '15 at 17:53
  • $\begingroup$ Yes, this is the usual regime. $\endgroup$ – Yuval Filmus Mar 28 '15 at 17:54
  • $\begingroup$ I still fail to understand, what advantage it has to hillclimbing. Hillclimbing can get stuck in local optima, but with this, pretty much the same thing can happen, can't it? Let's say it bumped into global optima from the beginning - the the annealing can make a jump from the global optima to some other place, where I'll find only local maxima... so what is the benefit? $\endgroup$ – Novellizator Feb 20 '16 at 19:37
  • $\begingroup$ You maintain the best solution found so far. This solves the problem you mention. $\endgroup$ – Yuval Filmus Feb 20 '16 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.