0
$\begingroup$

Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below:

Let s = s0
For k = 0 through kmax (exclusive):
  T ← temperature( 1 - (k+1)/kmax )
  Pick a random neighbour, snew ← neighbour(s)
  If P(E(s), E(snew), T) ≥ random(0, 1):
    s ← snew
Output: the final state s

I am having trouble understanding how this algorithm does not get stuck in a local optima as the temperature cools. If we jump around at the start while the temp is high, and eventually only take uphill moves as the temp cools, then isn't the solution found highly dependent on where we just so happened to end up in the search space as the temperature started to cool? We may have found a better solution early on, jumped off of it while the temp was high, and then be in a worse-off position as the temp cools and we transition to hill climbing.

An often listed modification to this approach is to keep track of the best solution found so far. I see how this change mitigates the risk of "throwing away" a better solution found in the exploratory stage when the temp is high, but I don't see how this is any better than simply performing repeated random hill-climbing to sample the space, without the temperature theatrics.

Another approach that comes to mind is to combine the ideas of keeping track of the "best so far" with repeated hill climbing and beam search. For each temperature, we could perform simulated annealing and track the best 'n' solutions. Then for the next temperature, start from each of those local peaks.

$\endgroup$
3
  • 1
    $\begingroup$ In my experience with my own variant of simulated annealing, it certainly can get stuck on local optima, but in the vast majority of cases these tend to be "close" to the global optimum (as determined by other methods). In order to get closer to the global optimum, I use a self-devised method of repeated heating and cooling cycles which works well for me but significantly lengthens the time to solution. $\endgroup$
    – njuffa
    Jul 9, 2022 at 22:23
  • $\begingroup$ Yeah I agree - without modification this algorithm seems quite prone to getting stuck at a local optima. Your approach of repeated heating/cooling sounds kind of similar to the approach I was thinking of (minus the beam-search portion). $\endgroup$
    – Solaxun
    Jul 9, 2022 at 23:08
  • $\begingroup$ You can find many relevant publications if you search for "re-heating" in conjunction with "simulated annealing". The difficult part, often driven by heuristics, is to decide (1) how often to re-heat (2) how much to re-heat. The lesson I learned is that a significant (that is, more than is used in conventional implementations) amount of re-heating can be key to escaping local optima. When combined with slow cooling, this makes for a lengthy optimization process, but the results are frequently superior. $\endgroup$
    – njuffa
    Jul 9, 2022 at 23:17

1 Answer 1

1
$\begingroup$

Yes of course it can get stuck in a local optimum. The idea is that hopefully we get closer to the global optimum, and if we get stuck in a local optimum, hopefully it'll be close to the global optimum... or maybe even exactly in the global optimum.

It's important to understand that there are no guarantees. Simulated annealing is a heuristic. So, yes, it is absolutely possible that it goes awry. And it doesn't necessarily find the absolute global optimum -- even just finding a near-optimal solution might be considered a victory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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