Computer cipher solving – Lesson 4: Simulated Annealing

Hillclimbing has an inherent problem: the local maximum. I’ve described this in previous lessons. One way to deal with it is is simply to start over again with a new scrambled key repeatedly. Scryer calls that Shotgun Hillclimbing, I think because a shotgun scatters its shot randomly over a target surface.

Another approach is Simulated Annealing. If that Wikipedia description looks intimidating or unclear, I’ll simplify it as best I can. For our purposes in hillclimbing the idea is really pretty simple. When you compare a new key to the previous one, instead of swapping keys only when the new one is better, swap sometimes when it is the same or even a bit worse. At first you can do this a significant number of times, but as your loop progresses, you must gradually reduce the number of times this happens and the size of the downward gap you are willing to accept. For example you might start by randomly accepting 20% of the time swaps that score 5% worse. After a few hundred or a few thousand iterations, though, those numbers might be 3% worse 10% of the time, and so on. Eventually you will end up not accepting worse-scoring swaps at all. In other words, you will be doing straight hillclimbing at the end. The progression from many to few “bad” swaps is made by reference to a table and a variable called the Temperature (T). When T is high, many relatively large “bad” swaps are accepted, but as T is lowered, fewer such swaps are accepted. The table contains values used to specify the random breakpoint numbers for the scoring gap. Every  X number of iterations T is lowered until eventually you are just hillclimbing. You will be required to experiment to see the range from high to low of T based on your cipher type and scoring method.

This approach allows you to jump around the landscape a lot more at the beginning trying to get onto the right mountain before settling in on a steady climb up. The improvement is quite marked for some ciphers. After a while, though, if no solution comes, you will probably need to shoot that shotgun again and start over with a newly scrambled key and T boosted back to a high number.

My description of simulated annealing may not comport with a strict mathematical description. There are other, similar methods that use other terms for technical reasons but I lump them all together as simulated annealing. The concept is the same: allow your program to make some key changes that appear bad at first, but as you improve your result, limit those allowances.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.