I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand here is that, if with temperature $0$, the stationary distribution will be distributed among optimal solutions, so why we need to have initially large temperature and reduce it slowly, so that at each temperature, the algorithm reaches the thermal equilibrium? Why do not we set the temperature to $0$ at the start of the algorithm and iterating until reaching thermal equilibrium for temperature $0$.

Form physical point of view, i know that, if in the annealing process, the temperature reduced quickly, the meta-stable amorphous structures will be reached rather than the low energy crystalline lattice structure. But from theoretical point of view, i can not understand the depth of the subject.

  • $\begingroup$ The problem is you don't know what the stationary distribution is, you have to reach it somehow. Still, I find the sentence you quoted a bit problematic, since at zero temperature, a distribution centered on a local minimum is stationary, so perhaps more context is necessary. $\endgroup$ – Ariel Aug 25 '17 at 10:39
  • $\begingroup$ The algorithm you suggest is very common, and goes by the name local search. Simulated annealing is an improvement, which helps the algorithm get unstuck from local minima. $\endgroup$ – Yuval Filmus Aug 25 '17 at 10:53
  • $\begingroup$ i know what stationary distribution is, and i know for each temperature, based on metropolis acceptance ratio, with large enough iterations, algorithm can reach stationary distribution for that temperature. What i want to know is that, whether the algorithm can reach optimal solution or not if we set initial temperature to zero and run the algorithm for infinity. $\endgroup$ – Payam Abdy Aug 25 '17 at 11:08
  • $\begingroup$ When you set the initial temperature to zero, you are running local search. Simulated annealing is supposed to be an improvement over local search. $\endgroup$ – Yuval Filmus Aug 25 '17 at 15:30

At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to overcome this difficulty by letting the algorithm sometimes make moves that temporarily deteriorate the value of the current solution.

| cite | improve this answer | |
  • $\begingroup$ I know this answers the question's text, but I'm wondering if you could comment on the question title as well, since that's what comes up in my searches. What is meant for a particular iteration of temperature T to be in "thermal equilibrium"? And why is it necessary for SA to reach this condition before decreasing T? $\endgroup$ – Azmisov Apr 21 '19 at 0:01

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.