0

The entire idea of simulated annealing is to avoid getting stuck in local optimums, which is why sometimes, a worse solution is accepted.

However, simulated annealing will automatically accept a superior solution to the current one. Thus if you are in a local optimum, then simulated annealing will get you out of it for one iteration, and then put you right back in it since it will accept the local optimum with probability 1, right?

I know that yes, if the temperature is still high, then you can escape out of that local optimum, but if the temperature has cooled and you are still at the wrong local optimum, then you are pretty much stuck there, correct??

1

If it's in a local optimum, any choice of neighbor is worse and accepted with a probability depending on the temperature, yes. Note the wording any choice of neighbor: There are typically dozens of neighbors or more, and at every iteration only one is examined. Thus the state can easily get several steps away from the previous local optimum. Since it's rather unlikely to pick the exact neighbors again and go back on the same path, it may slide towards a different minimum (the search space is usually high-dimensional, so 2D intuition underestimates the number of paths available).

And yes, even after many iterations it may still be in a local optimum rather than the global one. That's okay. SA is a meta-heuristic, it's used when an exact solution is not feasible. A local minimum found after many iterations, with good choice of parameters, will still be far better than what more simplistic approaches can produce. Perhaps its cost is only ε away from the global optimum, but extremely far removed spatially. (Of course, in other cases the solution is simply crap and different parameters or a different metaheuristic may work better.)

  • So by this logic, simulated annealing is pretty useless in one or two dimensions? – extremeaxe5 Nov 23 '14 at 11:14
  • @extremeaxe5 I would think so, but I have no experience to support that claim. For one or two dimensions, there are many other techniques that work great and only degrade in higher dimensions because they scale worse-than-linear as the dimensionality grows. – user7043 Nov 23 '14 at 11:20

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.