Why does Simulated Annealing not take worse solution if the energy difference becomes higher?

Question

In Simulated Annealing, a worse solution is accepted with this probability:

$$p=e^{-\frac{E(y)-E(x)}{kT}}.$$

If that understanding is correct: Why is this probability function used? This means that, the bigger the energy difference, the smaller the probability of accepting the new solution. I would say the bigger the difference the more we want to escape a local minimum. I plotted that function in Matlab in two dimensions:

Answer 1

Note that you can't really predict whether your escape from a local minimum will work or not - you might just wind up in another, worse local minimum. The probability function you describe increases the likelihood of this happening. By upweighting the likelihood of allowing small energy differences, you allow for the possibility of escaping local minima, while ensuring that whatever new minimum you find can't be that much worse that where you started. If you make the acceptance of large energy differences more likely, you can escape local minima more often, but you increase the likelihood that you'll just wind up in a region with an even higher local minimum.

Answer 2

Nice question!

My guess is that, if the probability of acceptance increases the bigger the difference between the current and new solutions is, then there's the risk that you need to search a lot again to find a good solution, i.e. you may oscillate between different subspaces or you could actually often end up in subspaces where there are only bad solutions. Your reasoning probably makes sense at the beginning of the search when the initial solutions may not be good enough or maybe if you have parallel searches (and you want to explore the search space at different search subspaces), but once you have a good solution, you don't want to completely discard it and replace it with a quite worse solution.

If you perform some experiments with your idea, I would like to see the results.