7
$\begingroup$

Suppose one is performing Gibbs sampling with a Boltzmann distribution (or if you prefer, simulated annealing) at finite temperature. In general we would want to anneal: as the sampler converges to equilibrium, the temperature should be decreased.

If the sampler's rate of convergence (local in time) does not vary, there is no real reason to vary the temperature. On the other hand, if the convergence rate decreases, then the temperature should be decreased as well. This naturally leads to a heuristic that sets the temperature as (proportional to) the convergence rate.

Has this heuristic (or one like it) been explored in the literature? Specific references and/or buzzwords are most welcome.

$\endgroup$
  • $\begingroup$ This is related (not the same) as fast simulated annealing (Szu and Hartley). $\endgroup$ – S Huntsman Feb 18 '12 at 14:26
  • $\begingroup$ One potential issue is that this would make it even harder to escape from local optima. The convergence rate will decline when converging to a local optimum just as much as when converging to the global one (if it exists), and reducing the temperature in this case will make the system exponentially less likely to climb back out of the local optimum and find a better one. $\endgroup$ – Nathaniel Apr 20 '14 at 7:56
2
$\begingroup$

In my work creating a simulated annealing course scheduler (bottom of that page), I came across a good paper:

Huang, M., F. Romeo, and A. Sangiovanni-Vincentelli, "An efficient general cooling schedule for simulated annealing," Proc. of the IEEE International Conference on Computer Aided Design (ICCAD), pp. 381-384, 1986.

This work outlines some adaptive cooling schedules for simulated annealing, where the recent variance of the "scores" is taken into account to dampen or accelerate the temperature change as needed. ("Score" means the Boltzmann distribution evaluated at the accepted proposal locations.)

They investigate a 'phase transition' property of simulated annealing problems: cooling tends to proceed steadily, goes through a phase change with large temperature drop, then continues steadily. This phase change helps quantify the complexity of the optimization problem.

$\endgroup$
  • $\begingroup$ Our report is linked here. It's just a course project summary, but it goes into the details of several different heuristic methods that we used, such as adaptive cooling and re-heating as a function of cost. $\endgroup$ – ely Feb 17 '12 at 3:54

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.