I remember seeing Karl Sims’ video Evolved Virtual Creatures a long time ago. I was completely stunned but unfortunately forgot about it for many years. I was reminded of it again last year when reading about training neural networks using genetic algorithms (Tom Mitchell’s Machine Learning is highly recommended) and decided to evolve my own creatures.

Preparation

Here is the first demo.

The task is to teach an ant to get to the end of the L-shaped corridor as fast as possible. All an ant is allowed to do (every frame) is rotate freely and turn on its forward thrust (acceleration). Ant’s behavior is encoded in its DNA consisting of several genes. Every gene prescribes what an ant does in the frame that corresponds to the index of the gene in the DNA. Specifically, each gene is a 3-bit number encoding the ant’s possible behavior:

var gene:int = dna[simulationStep];
var acceleration:Boolean = gene & 1;
var turnPositive:Boolean = gene & 2;
var turnNegative:Boolean = gene & 4;

The genetic operators used are not tuned for this particular application. What you see on the screen is one population of 100 individuals. It takes time but if you let them learn you’ll see that in the end they achieve the goal in the most optimal way.

Evolution

Encouraged by the result (also, it only took about 2 hours to code) I wanted more. Without further ado I present the walking creatures (after 300 generations).

The task here is to give physics-based (thank you, Box2D!) ragdoll figures brains to be able to move a certain distance. Following Ngo and Marks’ paper Spacetime Constrains Revisited I set out to make my own creatures in Flash. In short, I am using a genetic algorithm to train a neural network that controls motors in the creature’s joints. The fitness function is plainly how far a creature can get within a certain amount of time. The neural network used is very simple – it’s a single layer feed-forward neural network with the inputs being the angles at every joint, vertical velocity and horizontal distance traveled and the outputs the speed of the motor and the target angle of every joint.

Results

I was really happy to see results only after about 300 generations (it took a night though): a frog. Excited, I ran it again and again and interestingly, I only got frogs. I tried to change the fitness function a bit so that the creatures that touch the ground are penalized but didn’t get anything interesting. Also tried to make the torso a bit heavier and an inchworm-like creature evolved. If you like, you can try to evolve your own creatures, here’s the link to first generation (with a little bit of creativistic randomization to start with). At the end of every generation, the best DNA is traced so if you happen to get some interesting locomotion, please send it to me and I’ll post it here. (Source code to follow after a brief clean-up.)

Edit: Get the source code in the next GA post.

What’s Next

My plan is to try what behaviors will emerge with different shapes, physics set up, fitness functions or selection algorithms.