# Simulated Annealing - Intuition

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.

• 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. Commented Jul 9, 2022 at 22:23
• 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). Commented Jul 9, 2022 at 23:08
• 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. Commented Jul 9, 2022 at 23:17