As a little pet project I'm writing some code to do a little cryptanalysis. Starting with something simple I have created a hill climbing algorithm for solving a simple substitution cipher.
So I start by generating a parent key by shuffling letters A-Z randomly. For the first iteration I am generating a child key by randomly swapping 2 characters from the parent key, and in each subsequent iteration I am shuffling two characters from the previous iteration's key.
While this approach works, it seems very inefficient, as the randomness seems to generate the same key over and over again on each attempt at a solution.
So my question is, is there a better solution for generating child keys than random? A few things I have considered but not tried:
- memorizing previous keys and checking a new random key has not already been tried
- Some other means of shuffling characters, such as swap 1-2, 1-3, 1-4 .... 2-3,2-4... etc (This feels much too much like brute force)
But both of these strike me as making the algorithm less efficient not more (ie, the overhead in doing each outweighs the gain made by using random chance).
Any particular thoughts?
Edit: As the comments have quite rightfully pointed out perhaps the problem I'm facing is not actually how to generate better child keys, but how to avoid a local maximum. Other relevant details of my algorithm are as follows:
- I am scoring based on the Sum of the Log10 probability of Quadgrams
- I am running my algorithm until 1000 iterations have not provided a better score
- I am running the entire thing until 20 tries have not produced a better score