peteshadbolt.co.uk

Genetic algorithm

Flash is broken: Unfortunately this project was written more than a decade ago, and the demo no longer runs in modern browsers. I am working on a way to bring it back to life without a full rewrite. In the meantime you can find a much advanced derivative of my original code (extended by multiple smart people) here.

Alex Mabee did a great job of explaining what is going on, in this video:


This program uses a genetic algorithm to design a two-dimensional car that is “optimal” for a particular terrain. The rules of the problem are as follows:

  • The car must have two wheels (blue circles) and two loads (red circles).
  • The initial positions and radii of these four masses can be freely chosen by the algorithm.
  • The masses are connected by springs whose length, damping constant and spring constant can be freely chosen by the algorithm.
  • The loads must never touch the ground.

The optimality of a particular candidate solution (the fitness function) is determined by how far it travels before a) a mass touches the ground or b) time runs out.

Note that at the beginning, the algorithm doesn’t even know that wheels belong on the bottom. It is sometimes possible to see distinct species emerge and die - for instance, “unicycles” are often quite successful in the early stages of the algorithm’s progress.

The graph shows mean and maximum fitness values as a function of generation number.

This demo inspired Boxcar2D.

The GA could converge much faster than it does here. In choosing the fitness cutoff, population size etc. I have aimed for an interesting/fun simulation rather than a fast, useful optimization.

The timeout is fixed but arbitrary. It was a quick hack to remove cars which get stuck without dropping their load. It has the side-effect of making this program extremely frustrating to watch.