Cultured Perl: Genetic Algorithms Applied with Perl

By Teodor Zlatanov
2004-11-03

A Simple Example

The code in Listing 1 uses a single byte as DNA (value between 0 and 255, 8 bits). The fitness formula is applied once to every new individual, taking the byte value of the DNA and dividing it by 256. This means that the fitness formula will always return a number between 0 and 255/256, so it can never reach 1. What do you think the fittest DNA will be?

numbers.pl source

There are several interesting things about Listing 1. Its main loop is at the beginning, and you should understand all the pieces and how they work together on the population (and yet they are separate, so we can reuse them in the next example). You can execute Listing 1 with numbers.pl.

We build the weights array in the select_parents() function by stacking map() on top of grep(). While it could have been written as a loop, the one-line solution is much cleaner that way, and does not slow the program down significantly.

my @weights = map { $_->{fitness} } grep { $_->{survived} } @$population;

The $population array reference is de-referenced. Then, only elements of the array with the "survived" field (set earlier by the survive() function) get through the grep. The survivors are then distilled to their fitness numbers, which get put in their places in the weights array.

The population size was chosen to be 256, because that way it was easy to initialize every individual to a number equal to its index. Feel free to start with different population sizes.

Mutation rates of more than 1% caused the maximum and minimum fitness to fluctuate wildly. The population never stabilized towards high fitness. Low mutation rates cause the population to reach high fitness as a whole much slower. In the end, 1% was about right for our population size.

The breeding selection algorithm picks one parent by looking at the weights - in effect, every individual gets a chance to be a parent, but the number of parent slots is finite. The second parent is picked at random from the parent population. Why? Well, we could have used weights to determine the second parent as well, but this way we ensure every parenting individual has a chance to participate in the breeding process.

The actual breeding is accomplished with a random 8-bit bitmask. We just AND the bitmask to the first parent's DNA (remember, it's just a byte) and AND the inverted bitmask to the second parent's DNA. The effect is that we pick random bits from one parent, and then the rest of the bits come from the other parent.

The mutation is accomplished by AND and OR of individual DNA with random 8-bit bitmasks.

Oh, and by the way, the most fit DNA was 255, of course. You don't need to wait 100,000 generations. Just hit Ctrl-C when you are done admiring the status line.

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