There’s been a lot of buzz recently on reddit and HN about genetic algorithms. Some impressive new demos have surfaced and I’d like to take this opportunity to review some of the cool things people have done with genetic algorithms, a fascinating subfield of evolutionary computing / machine learning (which is itself a part of the broader study of artificial intelligence (ah how academics love to classify things (and nest parentheses (especially computer scientists)))).
If you’re new to genetic algorithms, don’t be put off by the awesome/scary name – you might like to check out my own modest contribution to the field of abusing science to make cool useless things; the hello world genetic algorithm tutorial. It’s written as a short genetic algorithm tutorial to help beginners understand genetic algorithms from the ground up (and it has a pretty interactive demo in JavaScript too!).
So here’s my top five evolutionary scripts:
Number Five – Evolving a Car
The earliest genetic algorithm I can remember seeing online is the original boxcar script, which evolves a car capable of traversing a landscape. It’s written in flash and source code is available which is pretty cool. It pops up on reddit etc from time to time. The earliest discussion I can find was from 2008. Here’s another thread from 2 months ago. This idea has recently been reborn at boxcar2d.com, where you get a little more control over the parameters – mutation rate, number of wheels, etc.
It’s pretty easy to see what the fitness function will be; how far the car can travel. This script also gives an answer to a common question; people often wonder what the point of a genetic algorithm is, asking things like “If you know what constitutes a good solution, why can’t you just create a good solution from scratch?”. The car evolution script demonstrates that in some cases knowing what makes a solution a good one doesn’t always imply that we know how to achieve that. We know that we want the cars to travel far, but we mightn’t know whether a short wheelbase is good, or whether large or small wheels are helpful and so on. Genetic Algorithms offer an easy way to explore the space of possible solutions.
Number Four – Lego Structures
This is a spectacular demonstration of the power of genetic algorithms – using them to evolve schematics for lego structures (which of course, the researcher then print out and create for real!). Some examples include evolving a lego bridge, a lego tree, a crane capable of carrying half a kilo, and a three dimensional table optimised for height, surface area, strength and lightness!
In the example above, candidate solutions were considered fitter the greater distance they spanned – the final bridge candidate was nearly two metres in length!
Besides combining lego and computers into a package of unbridled awesome, there are a few interesting lessons to learn from this:
1) The researchers probably couldn’t have created this length bridge by hand without a lot of effort, so the GA simulation allowed them not only to produce a decent real solution efficiently, but also allowed them to build a bridge without having any knowledge of how to build bridges (none of the humans needed to be architects). So that’s encouraging for fields where there are no existent human experts.
2) The bridge isn’t that good. I mean, it’s great, but it takes no load, and there’s probably a ‘better’ way to build a 2 metre bridge from lego – if you tasked an engineer with the problem I doubt they’d produce anything like the above structure. Which tells us that human experts, if extant, will probably be better than evolved solutions. And we also learn that it’s hugely important to get the right fitness function – the researchers didn’t add any load carrying ability to the algorithm, so it didn’t optimise for that. Perfectly understandable and expected, but something to be aware of if you’re designing your own genetic algorithm. Do you really want to assume you have an infinite supply of bricks or should the fitness function penalise a little for excessive material usage? Questions to ask yourself as a researcher.
I’m not meaning to imply that the guys who built this bridge overlooked anything – they knew exactly what they were doing – but I think their results illustrate quite nicely that even with fancy genetic algorithms, a computer will still always do exactly what it’s told to. They wanted a long bridge. That’s what they got.
Number Three – Artificial Creatures
If you thought the boxcar demo was cool, you’ll love this. While the boxcar was two dimensional and merely attached already-rotating wheels to struts to achieve motion, Nicolas Lassabe’s work involves evolving from basic building blocks creatures which are capable of interacting with a three dimensional physical environment – first walking, then climbing stairs, traversing moving objects, and finally operating in cooperation. You can watch the video below, and visit his website all about his research into artificial life.
These artificial creatures are a fascinating way to visualise the process of evolution, and offer a brilliant muse into the workings of natural selection. Moreover, I can see potential applications for resourceful robots which might scan an environment for parts it might be able to use and then use an evolutionary algorithm to find a good way of incorporating those parts into itself. Or something. Either way, I guarantee that when the robots come to cleanse the earth of organic scum, they’ll have evolved from these cute colourful critters originally. Be warned.
Number Two – Mona Lisa
This class of demo scripts are impressively visual. The task is to rearrange and re-colour some polygons in order to maximise the similarity with the Mona Lisa. It’s mesmerising to watch the triangles shuffle around on the canvas, gradually forming the face, eyes, mouth and so on.
There have been a few different Mona Lisa demos, but the earliest I can find is Roger Alsing’s Genetic Mona Lisa demo from December 2008. This demo (output pictured above) wasn’t even strictly a genetic algorithm – the solutions were represented in a chromosome and mutation occured, but there was no crossover operation (although Roger insisted it still qualified).
Since then, several authors have attempted the same using different technologies and approaches. Jacob Seidelin wrote an awesome version in Jan 2009 which is truly genetic, and furthermore works in JavaScript and html5 canvas! The awesomeness is almost too much to bear.
What strikes me about these is that you clearly see rapid progress towards the target image, but then a kind of local optimum is reached where the evolved image improves only at a very slow pace. This indicates a less-than-perfect mutation or encoding method. Indeed, perfect fitness can never be achieved using a limited set of polygons. Roger Alsing hinted at greater success with the detailed areas by using spline curves, pictured below, but no more has been heard about this.
Besides being a very fun demo to watch, there’s a strong intuitive sense that this could be applied to image compression; if you take a very fit candidate image, the chromosome will likely be a lot smaller than the original image data. Moreover, the chromosome will effectively be a vector graphic – infinitely scaleable. So there’s serious practical potential in genetic image compression and vectorisation. Neat. Encoding time is probably going to be an issue though.
Number One – Evolution IS a blind watchmaker
A clever and original demonstration of genetic algorithms. In this demo, the population starts with springs, gears, ratchets and hands, and it tries to evolve a working clock.
No shortcuts are taken; at the start the algorithm doesn’t know the correct ratios, number of teeth in the gears, correct number of components or which components fit together nicely. Watch the video as simple pendulums slowly evolve into hour, minute and second counting clocks. And even 4-handed clocks which have a 2 minute hand are unexpectedly evolved.
The presentation is framed within the wider creationism/evolution debate, and makes for an impressive demonstration of the power of evolution, and furthermore, the matlab code is made available in the video’s description! Impressive, educational and original!
If you’d like to learn more about genetic algorithms, check out my genetic algorithm tutorial with interactive demo and code, and post your go-to examples of genetic algorithms in the comments!
#1 by Nischal on March 4, 2011 - 1:59 am
Awesome info on genetics, Howard!
#2 by Valentin on March 4, 2011 - 4:15 am
Awesome. Thanks for sharing.
#3 by Trung Huynh on March 4, 2011 - 8:32 am
you should add my sample too lolzzz http://www.gregorymead.com/musichackday/
#4 by Howard Yeend on March 5, 2011 - 2:33 am
I sooo nearly added that! Don’t know why I took it out now!
#5 by ikariam on March 9, 2011 - 1:08 am
great article! my favourite are the lego structures :)
#6 by Ava on July 31, 2011 - 1:13 am
“great article! my favourite are the lego structures :)”
How on earth did they manage to ge the lego structure to balance? The tiniest load on it and the bridge would collapse!
#7 by Peter Edgerton on September 30, 2011 - 3:45 pm
I love the lego structures too! The interplay of Mona Lisa is just amazing!
#8 by Rita on January 1, 2012 - 3:22 pm
I agree, the lego structure experiment is particularly interesting. The “evolution is a blind watchmaker” video was also very clever, too. Colour me impressed.