adamcrussell

Evolving more code with AI::Genetic

In a separate entry I described the use of AI::Genetic to solve Part 2 of Perl Weekly Challenge 044. Here is a description of what I did for Part 1 of the same challenge. This ended up being slightly more complex than what was done for Part 2 so it seemed best to split them into two entries.

The Problem

You are given a string "123456789". Write a script that would insert "+" or "-" in between digits so that when you evaluate, the result should be 100.

What I Did

The code for this is much longer than the code for Part 2. What is not shown in the listing below are the definitions of the add, subtract, and no_op functions as well as get_X functions which take substrings of length X from the given string of numbers. Please click the code to be taken to the complete GitHub gist.

Although not shown here each of these functions has, for the convenience of providing a user friendly description of which function is being called, the following line:

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

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

ch-1.pl
ch-1.pl

This code ended up being more complex because more functions were required in order to express the possibilities for all genes. Well, it seems that way at first. At least one function, get_4, seems to be unnecessary given the solution that is learned by AI::Genetic. Eliminating it from consideration would certainly speed things up.

The core of any genetic programming project is the fitness function. Our function for this here has to take into account several things: substrings, substring lengths, and operands of the calculation. Still, ultimately we end of having a fairly sophisticated solution in just 132 lines! 

Sample Run

$ perl perl/ch-1.pl
123 - 45 - 67 + 89 = 100

Notes

  • In the entry for Part 2 I noted how I relied on trial and error vs mathematical specificity or even any sort of intuition for the values of the genetic programming hyper parameters of number of individuals, number of generations, crossover, etc. The same applies here.
  • In the terminate function some extra accounting is necessary to present the results in the right way. Technically the first operation is 0 + 123 but care is taken to hide this detail.
  • Multiple solutions exist. After a sufficient number of generations we could inspect more than just one top individual and be reasonably confident we captured all possibilities. I think so anyway, I am familiar enough with the literature at this point to be sure what the theory says about this! 

Comments for this post were locked by the author