Genetic algorithms

Another type of stochastic algorithm is the evolutionary or genetic algorithm. I have found it particularly useful for solving ciphers that have repeated characters in their key. The idea here is to make a large number of keys at random, perhaps 30,000 of them. This is called the ‘population’.

Then begins a continuous cycle of ‘reproduction’ with ‘survival of the fittest’. Two ‘parent’ keys are chosen at random from the population and from them is made a new key we call the ‘child’. This is done by taking the first ‘n’ characters from the 1st parent and the remainder from the 2nd parent – where ‘n’ is a random number, shorter than the key length. Scores from all three keys are compared – if the child is better than one of the parents, then it replaces that parent in the population.

As this cycle proceeds, the population gets fitter and fitter, the plaintexts get better and better until
either the solution appears;
or, the solution is not found, and the average score of the population approaches the best score seen to date. In this case the run has failed and must be repeated.

There are numerous modifications that can be made to the algorithm as described above, including a mutation step, but what I have described gives the essence of the genetic approach – ‘red in tooth and claw’ as it is.

I have found the genetic algorithm of use when there are numerous repeated letters, or integers, in the key. Example are Baconian, Myszkowski, Slidefair.