Josh On Design

For some reason the concept of Genetic Programming got stuck in my head the other evening. At midnight, after spending about four hours reading up on the topic around the web, I came away disappointed. The concept of evolving code the way genes do is fascinating but the results in the field seem to be very narrow and limiting. Thus began this rant.

This article called Genetic Programming: A Novel Failure probably sums up my thoughts best. Genetic programming is only a slight variation on solution searching algorithms. Based on my reading, most work in the field has focused on how to make systems converge on a solution more quickly, i.e.: improving efficiency. This seems wrong, or at best premature.

We live in the 21st century. We have more CPU cycles than we know what do with. Where are the systems that are wide but shallow? The ones that are really non-determinstic and will generate truly surprising results? We should be wasting cycles exploring new possibilities, not generating new solutions for known problems.

The free ebook, A Field Guide to Genetic Programming, is a great primer in the topic. I read through most of it the other night. My biggest frustration is that almost all genetic programing systems focus on evolving syntax trees, usually some form of Lisp or it's semantic equivalent. I see why people would do this. Lisp code is easy to manipulate programmatically, so evolving it should be simple as well. There are other kinds of systems using different gene encoding, such as image arrays and direct byte code. However, these appear to be far in the minority. The Field Guide has a chapter on the topic, listing several alternate systems. The fact that these systems receive a single slender chapter while the rest of the book covers syntax trees gives you an idea of how under-explored the topic is.

When I first heard of genetic programming I imagined having a sequence of simple instructions that could be mutated. The instructions would be extremely simple and limited, perhaps more simple than most assembly languages. Evolving syntax trees certainly does let you make progress quicker, but the generated solutions will be limited to the underlying tree language. Our genetic beasties will never evolve novel flow control systems, or invent a crazy kind of memory register. ASTs are great if we want to produce a human readable program as the result, but it still feels limiting.

I would like to see a system that is as open ended as possible. Create a system of small instructions of uniform length that can only manipulate basic storage and do simple math. Then give them as much freedom as possible. Let them live in a wide fitness landscape. A digital environment with a huge number of potential ecological niches. Ideally we could take this to the next step and give our digital creations physical bodies so that they may evolve targeting real world constraints. Evolving a robot's brain seems far more interesting than figuring out how to gain 10 milliseconds trading stocks. Of course we lose rapid iterations by running them in the real world, so it my be better to run them in a simulation of the real world at many times normal speed. I imagine we could build self driving cars this way, starting with bots that play racing games then upgrade them to working with real world footage from actual self driving cars.

Am I wrong? Is there cutting edge genetic programming that is truly open ended? What successes have they made?

Please send feedback and comments to my twitter account @joshmarinacci instead of on the blog. Thanks!