Cultured Perl: Genetic Algorithms Applied with Perl
By Teodor Zlatanov2004-11-03
Breeding words
|
|
For this example, we will make the DNA 32 bits (5 bytes). Each byte will represent a letter or a space. We could have packed more information into each byte, but it would have obscured the purpose of the example. Every byte's value (0-255, numerically) will be either A through Z (if the value is between 65 and 90, conveniently chosen to match the ASCII set), or a space (if the value is 0 to 64, or 91 to 255).
Note how much of the example is similar to the example in Listing 1. The dictionary of words follows the program.
words.pl source
The main problem with this example was that DNA lengths greater than 32 bits were hard to manage. I started out trying to do my own bit operations, which were not only unwieldy, but also extremely slow. Then I tried the Math::BigInt package, which was extremely slow for this purpose. You can execute listing 3 with words.pl.
Finally, I settled on the vec() function -- it is quite fast, and was the right choice for handling DNA (essentially, the DNA is a bit vector, a built-in Perl data structure). Use "perldoc -f vec" to find out more about the vec() function.
It is possible to end up with 1024 individuals with 0 fitness. That's why this example has better safeguards against such an "accident" than the first example.
The init_population(), recombine(), and mutate() functions were changed to handle bit vectors instead of bytes.
The dna_to_words() function is somewhat inefficient, but is not invoked often enough to make a difference. The biggest slowdown comes from the fitness() function trying to match all the words in the dictionary, plus all the letters in the alphabet.
Fitness was calculated as: 2 for each letter in the DNA, plus the frequency of that letter in the dictionary, plus 2^N for every dictionary word of length N in the DNA. The dictionary array and letter frequencies hash were obtained only once (using a closure). Feel free to modify the fitness function and the dictionary to breed your own English words. The fitness formula shown is heavily biased towards letters, and takes a while to converge on English words (though "on" and "in" were pretty frequent visitors).
Tutorial Pages:
» Create Your Own Darwinian Breeding Grounds
» History
» So What is the Genetic Algorithm?
» A Simple Example
» Breeding words
» Conclusion
» Resources
First published by IBM DeveloperWorks
|
| Related Tutorials: » Random subroutines in Perl » Log Script Use » Creating Perl Modules for Web Sites » Bit Vector, Using Perl Vec » Build a Perl/CGI Voting System » Perl Range Operator |