adamcrussell

Evolving code with AI::Genetic

For Part 2 of this week's Perl WeeklyChallenge I took the approach of using the Artificial Intelligence technique of Genetic Programming. I will try and introduce the main concepts here but Genetic Programming is a large and complicated subject. I list some references for further reading at the end of this entry.

The Problem 

You have only $1 left at the start of the week. You have been given an opportunity to make it $200. The rule is simple: with every move you can either double what you have or add another $1. Write a script to help you get $200 with the smallest number of moves.

What I Did

ch-2.pl
ch-2.pl

Sample Run

$ perl perl/ch-2.pl
Start:  $1
Double: $2
Add One:  $3
Double: $6
Double: $12
Double: $24
Add One:  $25
Double: $50
Double: $100
Double: $200

First I define three function: add_one, double, and no_op

For convenience of providing a user friendly description of which function is being called I added the following line to each of these functions:

return (caller(0))[3] if !defined($x);

This line simply returns the name of the function being called if no arguments are being passed.

Then we define a fitness function and a terminate function.Now, looking at the main part of the code we can see we configure our AI::Genetic with fitness and terminate and setup Genetic Programming hyper parameters of population size, crossover, and mutation. Furthermore we configure our genes: we set ourselves up with 9 genes each one can take on any of three values of executing add_one, executing double, or turning itself off (no_op). Finally we invoke evolve() by providing a strategy of tournamentUniform and setting the number of generations to 1000.

AI::Genetic will then create the 5000 individuals each with the given genes. At each generation each individual's fitness will be assessed. The higher the fitness score the better. Fitter individuals will have a greater chance of reproducing their genes. In this way, after many generations, we converge on a solution which satisfies our requirements.

Interestingly multiple solutions exist which satisfy the requirements and take the same number of moves. Here is another

$ perl perl/ch-2.pl
Start:  $1
Add One:  $2
Add One:  $3
Double: $6
Double: $12
Double: $24
Add One:  $25
Double: $50
Double: $100
Double: $200

Notes

  • The source of many of these values, say, for the number of individuals, number of generations, etc is simply trial and error! I do not claim to have a large amount of genetic programming experience and I personally do not have a good instinct as to what reasonable values should be used. My only criteria is that after several iterations a solution seems to converge reasonably fast.
  • An interesting article on genetic programming in Perl is Genetic Algorithms with Perl. This goes into detail in many of the concepts encapsulated by AI::Genetic.
  • The most cited reference on Genetic Programming seems to be Koza's Genetic Programming: On the Programming of Computers by Means of Natural Selection
  • Fellow Perl Weekly Challenge contributor JJ Merelo has done extensive research work in Genetic Programming with Perl. For the purposes of this challenge I kept with the small simple framework of AI::Genetic but I suspect a more serious practitioner would want to be familiar with his work in this area. See, for example, the paper Still doing evolutionary algorithms with Perl.
  • I also used a genetic programming approach to Part 1 of Perl Weekly challenge 044. That turned out to be slightly more complex than Part 2 and is written up in its own entry.

Comments for this post were locked by the author