Genetic programming is about mimicking the process of natural evolution to create programs. The main idea is that you don't code the solution to your problem; instead, you:
- Create a fitness function that will tell how close a program is to solving your problem
- Create a large number of random programs (your population)
- See how well or how poorly they perform against your fitness function
- Let the best performers "survive"
- Mate them (that is, create offspring with features of their parents)
- Mutate the offspring by introducing random variations
- And pit your new population against the fitness function again, repeating the cycle until, hopefully, you reach a satisfactory solution.
It's a neat idea, in theory at least, but it's a bit tough to apply it without departing from your language of choice. Genetic programs are best created using tree structures, and so unless you want to switch to a LISP-style language, there are some hoops to jump.
In my case, I wanted to see how easy or difficult would it be to play with genetic programs in Python. Luckily there is a pretty good package for Python evolutionary algorithms, DEAP, which makes heavy use of Python functool's partials, and I decided to tinker with it during a couple of our lab days at Limbic. I wanted to make something just a step more complicated than DEAP's implementation of the Artificial Ant problem, and my mind went to Robot Turtles, a boardgame inspired by the classic Turtle program that I had been playing with my daughter.
In Robot Turtles, kids play cards to move their turtle around the board, trying to reach a gem. There are several kinds of obstacles: towers, pushable boxes, blocks of ice that you can melt with a blaster gun. The first thing that is interesting about it as a pedagogical game is that though the kids play the cards, a grownup, acting as the computer, is the one actually moving the turtles. They don't always move in the direction the player wanted or expected (though they always move in the direction the player ordered them to move) and helping kids figure out why and what to do about it is what you're after. Later, as these first lessons are better understood, you can move towards other goals: having kids give you sequences of cards instead of playing one card at a time, reducing the number of cards they can use to reach their gems, and using "functions" to help reduce the numbers of cards they use.
I did not set out to replicate the game entirely, but merely its obstacles, the turtle's goal, and the means to achieve it. This was pretty fun. The two main challenges were to come up with good ways to give the turtles a "sense" of their surroundings, and to have a fitness function that would help them reach their gems more efficiently.
In the end, my simulated turtles could "play" the same cards as in the game (move forward, turn left, turn right, shoot blasters), and they could also find their current distance to the gem, know if the gem is ahead of them, and a few other things (all the code is available here). As for the fitness function, I settled on a combination of reaching the gem (the greatest factor), number of moves to get there (lower is better), and distance to the gem in the end (lower is better; for the common case where a turtle never reaches its goal).
After a run, the code generates a graph visualization of the most efficient program, which can be enlightening on a simple case (apologies, but graphviz tends to crowd the nodes)...
...or puzzling in more complex ones.
There was a big gotcha in this implementation: since the execution of the genetic code is performed recursively, our Python implementation is constrained by the size of the function stack. For complicated scenarios, some generated programs would easily go beyond this size, causing the execution to blow up. This turns out to be a common problem in genetic programming, and there are standard ways to address it, but I did not need to implement them for my toy examples.
I enjoyed playing with DEAP and genetic programming quite a bit, as if I was watching monkeys trying to reproduce the works of Shakespeare by random typing, though I am torn about its overall approach to problem-solving: it is often inefficient, it has zero guarantees of reaching an optimal solution, and it is heavily dependent on giving the code the right tools to navigate through the problem, which involves reasoning about the problem to such an extent that it may often make more sense to just code the solution yourself, rather than have an army of bumbling mutants find it for you. Its application may not be useful yet beyond some niches, but when the setting is right, it's a beautiful thing to watch. Again, the code is all available on GitHub if you want to follow along.