Ever since coding up my first “biomorphs” program on a friend’s BBC micro in 1987, I’ve loved the idea of genetic programming.
The idea is akin to how our DNA works and is aimed to solve the problem of not having enough years in the universe to write a program big enough to do some really complex tasks. So, you don’t directly construct the final product itself, you first make a framework mechanism for making stuff and then you write a big list of stuff for it to make on your behalf. In the DNA example, the stuff is mostly protein, the list is the DNA and the mechanism is gene expression.
If the final product isn’t what you wanted, no biggie. Just tinker with the meta-list of instructions, feed it into the machine again, top up the hopper of stuff-source, and out pops a better one? Hmm, maybe not yet. Well evolution may have billions of years, but we’re in a hurry!
So, we’ve just shifted the problem from one of making the right product, to one of choosing the best variant from loads of prototypes – still impracticable. In real life the automated selection process is basic survival – so perhaps we need a similar automated survival test for an evolved program? Sounds fair enough, but what are the survival criteria?
Presumably every program has been created for a purpose, and that purpose can be defined in some way, for example in a requirements or functional specification, or perhaps a more mechanised input/output matrix. More recently there’s been a lot of process in Behaviour Driven Development (BDD) which blurs the line between high-level, soft and vague requirements and the more concrete test fixture data. As long as we can somehow assess if a program is getting its job done properly, we can select from a number of variants and choose the best one.
So how do we make it better? Randomly changing bits of a piece of computer code will completely break it 99.999% of the time, as every developer is painfully aware. But remember we are not modifying the code itself, we are modifying the list of instructions which assemble the final code. The instructions need to have some variables in them which can inject some behavioural flexibility into the final system. The tricky part is figuring out what those variants might be, without over-contriving them, and balancing the levels of variation so the system is relatively stable.
This Dusted Off episode, presents an experiment I did as a really visual example of this method, combining the biomorphs idea with a relatively new phenomena in casual coding at the time: the physics engine!
The original biomorphs concept was a relatively contrived example: you have an insect with X wings, Y legs, Z body components. The wings are X2 long, X3 wide, the legs are Y2 hairy, Y3 colour… you get the idea. So there are bunch of variables controlling the look of the animal.
The biomorph process presented 9 children insects which were subtle mutations of the parent. Your job was to think of something you wanted to achieve – like a wasp – and keep choosing the child that looked most like a wasp. After 5 or 10 generations of choosing stripy things with the right number of wings etc., you usually had something looking pretty close to a wasp.
My implemenation, of course, is only half-finished, but the idea was to create living-breathing digital creatures which could actually do something well or badly, perhaps in an animat / AI world together. So my biomorphs have physics engine components: wheels, a caterpillar track and a main body. The variables are pretty basic: how tight the track is, how many segments it has, how many wheels, how long the body is etc. The code was written in a completely scalable framework, so allow pretty much any type of creature to be created, with extensible “DNA” descriptors of the features.
So load it up, think of an idea and keep choosing the creature that fulfils your wish and breed from that one.
Examples I’ve actually achieved:
“Jail Breaker”: choose the first to escape from its pen.
“Tiny Dancer”: choose the one which hops around the most.
“Dawn of Man”: get one to stand on it’s end unsupported.
“Self-destructor”: choose the quickest to destroy itself.
View Evolute SWF File / full screen
The physics engine here is the awesome Box2D by Erin Catto and Boris the Brave.
I’d love to get back into this project, if only I could (be bothered to) get Flex working on my Mac…