4 ms·

Intuition for Simulated Annealing

67 points by adbge 12y ago

gjm11 12y ago
Fewer pretty pictures, but much funnier and describing several different optimization algorithms (in the context of neural network training, but most of it doesn't depend on that): "Kangaroos and training neural networks". ftp://ftp.sas.com/pub/neural/kangaroos.txt
plantain 12y ago
I think 'shaking the box' is more akin to random restart hill-climbing.
- qbrass 12y ago
  You're shaking it too hard. You want to give it percussive maintenance, not kick it down a flight of stairs.
perrygeo 12y ago
To explain simulated annealing to lay audiences, I rely on a similar (inverted) example. You're at the top of the mountain. You want to find the lowest spot. If you just keep walking downhill only, you may reach the sea eventually. But you may never reach Death Valley (86m below sea level) unless you are willing to climb some mountains at the beginning of your trip. IOW you need to accept sub-optimal moves (with decreasing probability) in order to adequately explore your surroundings.
- programmer431 12y ago
  Why not monte carlo your way?
  - nradov 12y ago
    When the solution space is very large Monte Carlo may not get you anywhere useful.
joe_the_user 12y ago
I first read about simulated annealing more than thirty years ago. It's a fascinating approach. The analogy to physics is especially fascinating. I have only kept up with the literature, not seriously implemented it, so I could be wrong. But what I understand is that while simulated annealing is good for many things, it hasn't shown itself to be best for anything and the improvements on it have tended to changes that weakened the analogy with physics [1]. I find this disappointing since in its raw form, simulated annealing suggested a sort of "physics of information processing" mapping hard computation problems to states of matter. But it seems like analogies may be as misleading as they are productive sometimes. [1] for example traveling salesman, http://en.wikipedia.org/wiki/Travelling_salesman_problem http://en.wikipedia.org/wiki/Travelling_salesman_problem, the first problem I saw simulated annealing applied to [in a reprint someone tossed out in Evans Hall at UCB circa 1981].
- jasonwocky 12y ago
  > But what I understand is that while simulated annealing is good for many things, it hasn't shown itself to be best for anything That's kind of the nature of the beast, though. Approaches like Simulated Annealing and Genetic Algorithms are appropriate for situations in which you have no good heuristic for pruning a search tree. They're almost always going to be last resort approaches, but at least in the case of SA they generally approximate quickly enough to provide useful results.
mrcactu5 12y ago
unless the global maximum is much higher, how much can be benefit from moving from the local max ? in some way shape or form, I hear argument over and over - and from intelligent people. We see this kind of risk-averse behavior in social situations where nobody wants to take the "hit" of moving from their current strategy. or there many have been a time, when we identified the maximum and the entire landscape has changed around them, so the strategy is no longer optimal. this is another real situation. also, "simulated annealing" seems to be a bit of a misnomer for this type of mixed strategy.

67 points by adbge 12y ago

gjm11 12y ago

Fewer pretty pictures, but much funnier and describing several different optimization algorithms (in the context of neural network training, but most of it doesn't depend on that): "Kangaroos and training neural networks". ftp://ftp.sas.com/pub/neural/kangaroos.txt

plantain 12y ago

I think 'shaking the box' is more akin to random restart hill-climbing.

qbrass 12y ago
You're shaking it too hard. You want to give it percussive maintenance, not kick it down a flight of stairs.

perrygeo 12y ago

To explain simulated annealing to lay audiences, I rely on a similar (inverted) example. You're at the top of the mountain. You want to find the lowest spot. If you just keep walking downhill only, you may reach the sea eventually. But you may never reach Death Valley (86m below sea level) unless you are willing to climb some mountains at the beginning of your trip. IOW you need to accept sub-optimal moves (with decreasing probability) in order to adequately explore your surroundings.

programmer431 12y ago
Why not monte carlo your way?
- nradov 12y ago
  When the solution space is very large Monte Carlo may not get you anywhere useful.

joe_the_user 12y ago

I first read about simulated annealing more than thirty years ago. It's a fascinating approach. The analogy to physics is especially fascinating. I have only kept up with the literature, not seriously implemented it, so I could be wrong. But what I understand is that while simulated annealing is good for many things, it hasn't shown itself to be best for anything and the improvements on it have tended to changes that weakened the analogy with physics [1]. I find this disappointing since in its raw form, simulated annealing suggested a sort of "physics of information processing" mapping hard computation problems to states of matter. But it seems like analogies may be as misleading as they are productive sometimes. [1] for example traveling salesman, http://en.wikipedia.org/wiki/Travelling_salesman_problem http://en.wikipedia.org/wiki/Travelling_salesman_problem, the first problem I saw simulated annealing applied to [in a reprint someone tossed out in Evans Hall at UCB circa 1981].

jasonwocky 12y ago
> But what I understand is that while simulated annealing is good for many things, it hasn't shown itself to be best for anything That's kind of the nature of the beast, though. Approaches like Simulated Annealing and Genetic Algorithms are appropriate for situations in which you have no good heuristic for pruning a search tree. They're almost always going to be last resort approaches, but at least in the case of SA they generally approximate quickly enough to provide useful results.

mrcactu5 12y ago

unless the global maximum is much higher, how much can be benefit from moving from the local max ? in some way shape or form, I hear argument over and over - and from intelligent people. We see this kind of risk-averse behavior in social situations where nobody wants to take the "hit" of moving from their current strategy. or there many have been a time, when we identified the maximum and the entire landscape has changed around them, so the strategy is no longer optimal. this is another real situation. also, "simulated annealing" seems to be a bit of a misnomer for this type of mixed strategy.