Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Re: A Beginning Guide To Evolutionary Algorithms

by AssFace (Pilgrim)
on Oct 20, 2003 at 16:26 UTC ( [id://300638] : note . print w/replies, xml ) Need Help??

in reply to A Beginning Guide To Evolutionary Algorithms

One area where these are great to use is old school encryption breaking. Back when encryption was based on things such as the German Enigma or the French Vigenere, etc, they were all essentially ways of using multiple alphabets to encode a message.

If trying to brute force it by hand, this would take a lot of time as the number of alphabets used increased. People like Turning worked out ways around it with mathematical approaches that greatly reduced the search space that one would need to go through.

Even today with fast computers, if you wanted to brute force the Poe Cipher (which is how I got into Perl, during the process of breaking that - I wasn't the first though - 5th I think), it would have taken more time than we can even really grasp.

That is where evolutionary algorithms come in.
In the case of the Poe Cipher - all of his written works and many of his letters are online at the Gutenburg project - so you can download those. After which, you can scan through them all and populate a Markov Matrix with their probabilities of showing up in various patterns. Digraphs, trigraphs, etc (number of characters in a row).

After that, you can now scan over a section of text and score it with that MM - the higher the score, the more likely it is to be actual text instead of just total gibberish.

Then you simpy have a tight loop that evolves the alphabets, tests output to see what its score is - if the score is higher than the last time, then we have a better set of alphabets. Then you mate and mutate them and test the score again, etc etc.
Due to errors in the encoding (whether purposeful or not), it wasn't likely that there would be 100% completion of the decryption by the program - but if you were outputting the code to the screen, once you started seeing text that you could understand, then you knew you were close and then could eventually do the rest by hand.

There are also applications similar to this in the stock market world - which I will gladly go into detail on if anyone is interested.

There are some odd things afoot now, in the Villa Straylight.