Generating child keys for a hill climb algorithm 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
My experience is that hill climbing is very efficient for solving substitution ciphers. As I understand there are two topics now.


How to generate the child keysSwapping characters of the key randomly (stochastic hill climbing) as well as trying all possible swap combinations is reasonable.  But for solving a substitution cipher I believe trying all possible character swaps per parent is more efficient. First, trying the same key more than once is avoided (at least for one parent), secondly it provides a clear condition when to stop the hill climbing: If none of the childs provide a better result than the parent.  Using the stochastic hill climbing and keeping track of the tried keys would be overkill, and I think effectively it turns this into trying all possible key swaps.
How to avoid a local maximumOne option is to use the Random-restart hill climbing (or Shotgun hill climbing, see http://en.wikipedia.org/wiki/Hill_climbing#Variants). It simply repeats the hill climbing using different random initial conditions and it works very well for breaking substitution ciphers.


Resources:


http://www.guballa.de/crypto/substitution.html
A substitution cipher solver, using the Random-restart hill climbing algorithm choosing always the first better key (called "simple hill climbing"). It uses Javascript Webworkers, so it will not run on some older browsers.
http://www.guballa.de/crypto/substitution_breaker.js
The related Javascript implementation