Hillclimbing

A change to the random search procedure, first developed 50 years ago, produces a useful algorithm called hillclimbing, which can solve simple ciphers. In this method a random key is generated and its fitness is determined. Some change is made to the key and if that causes an improvement in fitness, the changed key replaces the original – otherwise the original is kept. The change cycle is repeated, until no more improvements in fitness are possible. Then a new random key is created. This algorithm can be summarised as:

1. make a key at random & determine fitness. Call it the ‘parent’;
2. make some change to the parent to produce a ‘child’ key,
and measure its fitness;
3. if the child is fitter than the parent, make the child
the new parent & dispense with the old;
4. go back to (2), unless no improvements in the last 1000
changes in which case go back to (1)

As an example, hillclimbing rapidly solves Cryptarithm puzzles such as the one below:

ABHORE + CHAINS = OIBANAC.       ABHORE - CHAINS = OAOINO 

where each of the letters stands for a different integer from zero to 9. The hillclimber makes a key at random and assesses the two differences:

difference 1 = (ABHORE + CHAINS) - OIBANAC  

difference 2 = (ABHORE - CHAINS) - OAOINO 

If the key is correct both differences will be zero. The sum of the absolute variations from zero is a measure of the 'goodness' of the key -- the smaller the variation the better is the key.

Changes are made to the key by swapping and a change is kept if it is for the better. Very quickly the hillclimber converges on the correct key. You can try this out in the example program here. The program is designed for equations of the type shown above, to any base. 

The limiting feature of hillclimbing is that it can get stuck short of the solution at a position where no further improvements are possible. In the jargon, it reaches a local maximum. The situation is easy to see if you liken the hillclimbing algorithm to climbing Mount Everest. You start in the plain and must follow the hillclimbing rule to move upwards, choosing direction at random. Now you may be lucky and follow a route direct to the summit. But you also may find yourself climbing to the top of one of the foothills, where you can go no higher and will be marooned. That is the local maximum.

As ciphers become more difficult to solve, due to greater complexity, the hillclimber takes longer and longer to solve until it takes so long that its use becomes impractical. A better mousetrap is needed.