next up previous
Next: About this document ... Up: 7. Decryption by Optimization Previous: 7.2 Hill-Climbing in the

   
7.3 Simulated Annealing

(Never mind the name, which is for historical reasons that many don't find helpful.) The key idea behind simulated annealing is to randomly take steps ``backwards'' every now and then. Initially, backwards steps are taken relatively frequently, but as time goes on, they are taken less frequently.

The idea is as follows. First find the biggest hill. So go up and down and all around. If it is the biggest/steepest, then chances are you'll end up near it, rather than some medium or small hill. However, on the biggest hill, there can still be local maxima that would trap hill-climbing. Therefore, on the biggest hill, you need to explore to find the true peak, rather than a distracting medium hill. Therefore, still take backwards steps occasionally, but since you want to stay on the biggest hill overall, don't go backwards too often. Once you're on the true peak, there are still perhaps small hills, and then tiny hills, and then eensy-weensy hills. Therefore, still go backwards from time to time, but with progressively rarer frequency.

If you're not clear why this should work, that is not surprising. There are reasonably good justifications for it, but they're a bit complicated.

If you're not clear on what rate to use to reduce the probability of backwards steps, that is because the answer is not known. Generally, people just try something ad hoc, which is just a fancy way of saying, they make something up. If it works, great; otherwise, they try changing the rate in a different way.


next up previous
Next: About this document ... Up: 7. Decryption by Optimization Previous: 7.2 Hill-Climbing in the
Thomas Yan
2000-05-01