TDD and Genetic Programming
Listen to this article
TADAIMA!
It's been sometime since my last entry (feels like the start of a confession) but I've been in Japan for the past 2 weeks. For various reasons I really needed to get away from computers for a bit (no pun intended) and what better way than to emerse myself in my other passion.
As I was sitting in the plane on the 9 hour leg from Sydney to Tokyo, I was thinking about genetic programming (GP) and good old fashioned artificial intelligence (AI). I remember being fascinated by AI when I was a kid only to discover that in essence it was all about fitting a curve to a line. In more recent years, I stumbled on GP which sparked my interest once again especially when I read about people taking out patents on the basis of genetic algorithms (GA) they had developed specifically for the purpose of producing patentable designs.
So anyway, I started to think back to simple (and not so simple) neural nets that I had worked with. The kind where you create a back propogating net, feed it the expected inputs and outputs and watch it reconfigure the weights, etc. accordingly.
This got me to thinking about my old friend test driven development (TDD). Neural nets "evolve" by reconfiguring themselves to satisfy the old requirements AND the new requirements. TDD encourages a similar behaviour.
One of the criticisms of neural nets is they can be quite brittle. That is, they may very well solve the problems they have trained for but can often fail dismally on problems that to us seem almost exactly the same yet obviously differ enough to "confuse" the net. Usually it's just a matter of re-training the 'net with all the old data AND the new data (just like running your tests!). The trick is to understand the problem sufficiently to create useful training data.
One of the criticisims of TDD has been that it creates brittle applications. Now my personal experience is that is just rubbish. If anything, it encourages designs that are more flexible/extensible in the long run. But, it is true to say that a purely TDD application may not cope with a scenario that hasn't been tested for. In fact I argue that anything that hasn't been tested for is by definition not a feature of the system. Not only is it not a feature of the system now, it is definitely not guranteed to work in any future release even if it does work by coincidence now.
But the real thing I liked about comparing TDD with AI is that it's evolutionary. The system is continually adapted to suit the changing needs. This naturally lead me to think about GP and wondered if it was possible or even practical (let alone useful) to write a GA that could take a suite of failing JUnit tests and generate an application that would make the tests pass? Then we would simply add some more tests and re-run the GA to produce a new system adapted to the new requirements.
As I've already stated, I'm not sure how practical this is let alone useful even if it is possible. But it was the last thought on computers I had until I arrived back in Melbourne.
Now to find a good Japanese restaurant...
Comments
Would certainly generate code that would confuse the hell out of the reverse engineering guys ;-)
Posted by: Brett Morgan | February 28, 2004 07:07 PM
HAHAHA this is true ;-)
Posted by: Simon Harris | February 28, 2004 11:05 PM
assertTrue(algorithm.canComplete());
Posted by: fletch | February 29, 2004 02:01 AM
It might not be hard to write a stupid version of this. Imagine TDD without the "eliminate duplication" step...
The code runs the tests, sees what the input conditions were and then sees what fails... it generates code like this:
if (input1.equals("foo") && input2.equals("bar"))
{
return baz;
}
and it just keeps building up if statements. Now that *would* be brittle code!
Posted by: Kevin Dangoor | February 29, 2004 11:27 AM
Yes that would indeed be brittle. I was really thinking along the lines of true GP where we take essentially random instructions and "breed" the "most" successfull ones.
Posted by: Simon Harris | February 29, 2004 11:32 AM
I was joking, of course :)
I have a suspicion that it would be very, very computationally intensive to generate Java programs genetically. Another couple orders of magnitude performance increase in our machines, and it may not be unreasonable to do just that, though. And, of course, this is a reasonably distributable problem.
It would be very interesting to see what code looks like when it's created this way. The latest Wired has a picture of an antenna that NASA developed using genetic algorithms. It's pretty wacky looking but apparently has great performance characteristics.
Who needs to worry about offshoring when we can worry about the computers writing the programs for us? :)
Posted by: Kevin Dangoor | March 1, 2004 03:41 AM
You're talking about using a test suite as a fitness function - presumably the fitness of a particular candidate 'solution program' would be the number of test cases that passed?
Nice idea but the parallels really stop there. TDD is not evolutionary, it is simply incremental (assuming you're following an agile 'many-iterations' method, otherwise it's not even that). There is a huge guiding influence which is the brain of the developer - with an evolutionary approach you're only using the fitness function and some randomness to drive change.
Your big problem would be simply that initially all your solutions, assuming you had a library of primitives good enough to even express the desired functionality, would have a fitness function of precisely zero. You would need to supply a whole set of primitives, custom written, to give the initial population a snowflakes-chance of getting non-zero, by which time you'd have specified most of the solution yourself and the GP side would be uninteresting.
You'd either spend an eternity looking for a solution, or solve 99% of the problem yourself writing primitives specific to the domain.
As for what the code looks like, the answer would be 'bloated spaghetti' - unless they've managed to totally solve the bloat problem since I stopped working in the field.
Posted by: Chris Harris | March 1, 2004 06:51 PM
Chris, thanks for posting your thoughts. I had pretty much guessed most of what you were saying but it is nice to have it confirmed by someone who clearly knows much more about this kind of stuff than me. Much appreciated - Simon
Posted by: Simon Harris | March 9, 2004 10:03 PM
You might consider co-evolution GA's. One GA would be evolving a solution that can score highly on a set of test situations. The other GA would try to evolve a set of test cases that make the solutions (generated by the first GA) score the lowest. There has been a good deal of research into co-evolution. Check out (if you haven't already) Melanie Mitchell's book "Introduction to Genetic Algorithms"; it's a concise, streamlined survey of the field.
Posted by: Westquote | March 18, 2004 10:54 AM
I came up with a similar concept, which I tried to express as humor a few years back:
http://www.youell.com/matt/brain_dump/omaps.shtml
I actually got contacted by a lady in Canada who wanted my random text generator. =)
- Matt
Posted by: Matt Youell | March 20, 2004 01:10 PM
I've been thinking about starting a SourceForge for GP based on JUnit as fitness.
One problem I've thought of is this: if you design tests according to a certain object model, the resulting code will follow your object model. This means we get a GP algorithm, but not a GP object model.
If, on the other hand, we want to let the GP algorithm create the classes and methods in addition to the algorithms, it will be VERY hard to match the tests with pieces of code.
It would be very difficult to find a happy middle ground. That is, telling a computer to do "separation of concerns" and "separate your data model from your actions" without specifically giving it the classes/methods to use would be pretty hard.
-James (j3rosen shift-2 homtail dot com)
Posted by: James | February 23, 2005 10:04 AM