CODEWITHSUNDEEP
simulated-annealing
Roy
Roy

Reputation: 783

Understanding simulated annealing- conceptually

i have just been introduced to simulated annealing and would like to understand it better before delving into the code again as I feel like I dont quite get it despite reading the code from the resources I have so far. So please feel free to correct my current understanding of the algorithm:

Simulated annealing algorithm has an overall goal of achieving the minimum(or maximum) score based on some predefined method of computation (like distance travelled in TSP or codon pair distribution in bioinformatics). However, to avoid being trapped in a local optima, a temporary lower (or higher) score is accepted so as to achieve a better global solution.

An additional question: How is the local optima overcome? Is it by accepting a higher score based on some probability? (quite hazy from here on)

Thank you very much for looking into this..

Upvotes: 1

Views: 1819

Answers (1)

Gareth McCaughan
Gareth McCaughan

Reputation: 19971

Your description is right but might be misleading, because "so as to achieve a better global solution" suggests that somehow the algorithm knows that the temporary worse score is going to help. It doesn't (it couldn't!), and indeed most of the time the temporary worse score is simply a temporary worse score.

Here's the idea. You're stumbling around in the dark, looking for a deep hole. If you just keep going downhill then you'll end up in the nearest hole to where you start, which may not be very deep. So you deliberately move around somewhat at random, letting yourself climb out of shallow holes if you get into them. So shallow holes are mostly invisible to you; but if you happen to fall into a really deep hole you'll likely stay in it.

Now, of course eventually you do want to find the bottom of whatever hole you're in. So you start off with a lot of randomness and gradually reduce it, so that initially you're just wandering around almost completely at random (unless you have the good fortune to fall into a really deep hole), but later on -- once you hope you've found the deepest hole you can -- you can locate its bottom more accurately.

The physical analogy is with the process of crystal formation as a liquid cools. You get bigger (lower overall energy, nearer to a global optimum) crystals by cooling slowly. Temperature = randomness, and the underlying process is rather similar to that of simulated annealing. Or, rather, simulated annealing is rather similar to a process of slow crystal growth.

As far as mechanism goes: the usual setup is that you try steps at random, always accept them if they make things better, and if they're worse accept them with probability that looks like exp(-d/T) where d is how much worse the step makes things and T, the "temperature", is a measure of how much random nonsense you're prepared to put up with at the moment for the sake of exploring the solution space more. You gradually reduce T. As T->0 the probability of accepting a step that makes things worse at all goes to zero.

The details of how you generate your random steps and how you reduce the "temperature" are where most of the actual work goes :-).

Upvotes: 5

Related Questions