12 ms·
As introductions go, this is not very good. For example, the first sentence "Simulated annealing is a method for finding a good (not necessarily perfect) solut
by ska 12y ago
As introductions go, this is not very good.
For example, the first sentence "Simulated annealing is a method for finding a good (not necessarily perfect) solution" is incorrect in theory, while correct in practice. I feel that it is this dichotomy that brings the most insight to the strengths and weaknesses of the approach. Further, the post doesn't give any good intuition on why it works, or how it works, or how it compares to alternatives... everything you would want to know. It also gets other details not quite right, like the origin of the Gibbs measure (the name "simulated annealing" comes from analogy to the annealing process in metallurgy, but the Gibbs formulation comes from probability theory, and the application here via the Ising model and electromagnetism). This isn't very important to a practical intro I guess, but it makes it harder to find the right places to read deeper if you wish to.
It's fairly easy to prove that simulated annealing done "properly" will converge to a uniform distribution over all global minima. The "properly" here involves a logarithmic cooling schedule and a little thought should convince you that this is in practice not going to help you any more than exhaustive search will.
It's very difficult to prove useful properties about convergence or distribution on faster cooling: therin lies the rub.
I suspect a big part of the popularity of the approach is that it is extremely easy to implement, but unfortunately naively application often doesn't work very well on complicated energy state spaces.
- carlob 12y ago> It's fairly easy to prove that simulated annealing done "properly" will converge to a uniform distribution over all global minima. The "properly" here involves a logarithmic cooling schedule and a little thought should convince you that this is in practice not going to help you any more than exhaustive search will. Are you sure this is proven? What if ergodicity is broken?
- ska 12y agoToo late to edit the parent, but you are right to call me out on this, thanks!. Clearly without some ergodicity constraint you cannot have uniform distribution. I was sloppy with terminology, sorry. The original approach to this require weak and strong ergodicity conditions on an inhomogeneous Markov chain (but not stationarity of the chain, i.e. you don't have to run it forever). This was worked out in the mid 80s by Gidas and Mitra if I recall correctly, and several interesting updates since then. There are other probabilistic arguments made as well, after that. I can dig out references if anyone asks.
- carlob 12y agoThe problem then is that proving ergodicity is extremely hard for anything that is not a Markov chain to begin with. IIRC ergodicity of hard spheres is not yet proved in full generality (n spheres, d dimensions), and that's basically the simplest physical system there is!
- deleted 12y ago[deleted]