Timeline for Metropolis, simulated annealing and proposal distributions
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2016 at 10:58 | comment | added | filippo | uhm no, I was wrong, scipy uses $\sqrt{T}$, I feel like I'm missing something pretty obvious | |
| Mar 3, 2016 at 9:29 | comment | added | filippo | I finally had a little time to look into this again. $\sigma = \sqrt{T}$ actually leads to roughly constant acceptance rates as expected. This is not what Szu, Geman and Geman, and a lot of other literature on Bolzmann and Cauchy machines, use though: they use $\sigma = T$ with steps $\propto \exp{-x^2 / T^2}$ or $\propto T/(x^2+T^2)$. Same for Scipy annealing implementation (not that it really proves anything...) | |
| Feb 28, 2016 at 19:01 | comment | added | Florian Hartig | better methods - not a big secret - just check if you still get better with time (by some epsilon), if not stop. | |
| Feb 28, 2016 at 8:04 | vote | accept | filippo | ||
| Feb 28, 2016 at 8:04 | comment | added | filippo | In my practical experience with $\sigma = T$ the acceptance ratio grows again at small temperatures (small steps, small $\Delta E$, small $T$, proposal $\rightarrow 1$). Using $\sigma \propto T$ with a proper, big enough, constant, this effect is mitigated, but I didn't see any real gain (e.g. faster or better convergence) over constant $\sigma$ steps. If I may go a little off-topic, could you give me some pointers about this better methods of checking convergence? right now I'm monitoring energy variance but it's not that different in behaviour from acceptance rate. | |
| Feb 27, 2016 at 17:38 | comment | added | Florian Hartig | Yes, OK, but the first part of the practical experience may also be because you haven't reached the optimum yet - in the code above I assume you are proposing to go away from the optimum. It's also my experience that acceptance goes to zero, but this may also be because people tune the proposal to shrink slower than the acceptance (which is what your $\sigma$ = T suggests to me). I wonder about the sense of that though, because there would be other ways to check convergence, so why would you waste your computation time on all these rejections. | |
| Feb 27, 2016 at 15:15 | comment | added | filippo | Thanks, I'll have to think about it, but it seems a promising and simple enough approach.About constant acceptance rates, I agree it should be a sensible goal but... Tipical rates start with a plateau at high temperatures, go roughly linearly as the annealing goes on, and reach a constant plateau $\sim 0$ at low temperatures. This is often used as a stopping criterion (IIRC Kirkpatrick used this very same criterion in his paper), so it doesn't seem a goal much shared in the Annealing literature. | |
| Feb 27, 2016 at 13:29 | history | answered | Florian Hartig | CC BY-SA 3.0 |