The Spiel

As mentioned in previous posts, I was recently in Barcelona at WCCI 2010 telling people about my work.  Here is a rough version of the spiel that I developed as I was telling people about my poster.

(To follow this it may help to know that Genetic Programming (GP) is a technique for evolving computer programs where the programs are typically trees like the one shown at the top right of the poster.)

My Poster To Help Me Explain TMBL to People At WCCI CEC 2010

I’m in interested in GP and in particular I’m interested in long term fitness growth.  In GP, we tend to use big populations but relatively few generations, say a hundred or so, so it’s a bit like putting lots of GP individuals in a bag, giving it a good shake and then refining the best results.  This produces some pretty cool stuff but maybe if we could find a way to make the fitness keep improving (even if very slowly) then after, say, a million generations we could get some REALLY cool stuff.

So then the obvious question I face is why doesn’t GP do that already – why does it stagnate.  To answer this, I argue by analogy… Imagine that I give you around a hundred toy blocks with patterns on their surfaces so that there is one way to line them up to make their patterns match (see the poster).  Imagine that I ask you to solve the puzzle but only using trial and error: no pre-planning, no writing things down, just considering random changes and performing them if they improve things.

If I give you this challenge, you will almost certainly take the puzzle, lay it out flat and solve it without much difficulty.  Imagine that I then give you an equivalent set of blocks but this time I insist that you build the blocks vertically in a tower.  I argue that you’re going to find that much harder.  In fact, I argue that with around a hundred blocks, you’ll find it pretty much impossible because however much progress you make, at some point you’re going to have to grab some block near the bottom and ruin all the hard work you’ve put into all the blocks above it.

Now, I argue that if we consider a GP tree flipped upside-down (see the poster), the same principles hold: at some point we need to make changes to a node near the root of the tree to allow it to improve and that ruins all the nodes above it.  The lower blocks in the puzzle support the blocks above them physically; the lower nodes in the inverted GP tree support the nodes above functionally.

So then we need to ask what went wrong when the puzzle became vertical?  I argue that the difference is that it became hard to make changes without ruining what had already been done.  Early in an attempt, it’s pretty easy to make progress but as more is achieved, there is more to lose by adjusting more of the blocks.

I believe that what stops GP usefully evolving for many generations is that its structure makes it hard to make changes without ruining what has already been done.  I believe that to evolve programs for longer, we must do everything we can to encourage changes that can affect behaviour without ruining existing functionality.  I call these changes tweaks.

So I try to do everything I can to change tree GP to encourage tweaks.  I consider the representation and go through four major design decisions (see poster) where I reject nodes, stacks, points of execution and output overwrites (more explanation to come at some later date).

I put all these decisions together into a representation (which ends up looking pretty similar to linear GP), I call it Tweaking Mutation Behaviour Learning (TMBL, pronounced “tumble”) and then I perform an empirical comparison.

My test is a very simple, meaningless problem in which I scatter 512 points in a square, randomly assign each of them to one of two classes, positive or negative and I use a fitness measure that rewards individuals if they output a value of the correct sign at each point.

The graph on the poster shows the results for tree GP (blue), linear GP (red) and TMBL (green).  The first thing to observe is that for the length of run that we tend to use for GP (a few hundred generations), TMBL is much, much worse than the other two.  When people propose new GP representations, they typically assess it using computation effort – a measure of how much computational work it typically requires to achieve some pre-specified level of fitness.  Again, using this measure at a fitness level of 840, TMBL is really, really bad.

As you can imagine, I would argue that although computational effort is a useful measure, it isn’t the whole story; what really matters is the best fitness.  I think the initial evidence is encouraging for two reasons.  One: TMBL ends up with a fitness level that’s quite a bit higher than for tree GP or linear GP.  Two: it supports the idea that after 10000 generations, TMBL has not stagnated in the way that tree GP and linear GP appear to have.

Barcelona

I have recently got back from Barcelona where I presented my poster on TMBL on Tuesday morning – the whole scene looked rather like this:

Me presenting my poster at CEC 2010

There was a very encouraging response to the work.  Thanks to everyone I spoke to for taking the time to listen and for your support and feedback.

When not at the conference, I tried to see as much of Barcelona as possible.  For the time being, I will leave my snaps here.  I like Barcelona an awful lot and I really rather was sad to leave.