To the Ministry's main lobby The Ministry Blog
concert setlists

10 December, 2008

Survival of the least unfit

This is a really important tool: a demonstration of evolution as an abstract process, independent of real-world examples; without directly challenging anyone's religious beliefs, it simply shows that evolution works, and how it operates.

The genetic algorithm generates a simple vehicle, which then attempts to traverse a predetermined terrain. The vehicle has two wheels, a springy quadrilateral frame with cross-bracing, and two circular 'passenger compartments'. Success is measured as the distance travelled within a certain time, without the passengers hitting the ground. The terrain of the track is fixed, but the dimensions and properties of each vehicle are variable: the initial positions of the four circles (i.e. the shape and size of the vehicle) and length, spring constant and damping of the springs. In case you're unfamiliar with the principles of genetic algorithms (I was), evolution progresses by, according to Wikipedia:

The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm.
A lesson learned very rapidly is that evolution is extremely dumb; or rather, that there is definitely no guiding intelligence: the initial parameters are set randomly, and the process doesn't 'learn from its mistakes' (i.e. establish design principles and eliminate future iterations of variants which definitely won't work). It goes without saying that an orientation placing the passengers at the bottom and wheels at the top will fail instantly, and that a 'penny farthing' can't handle rough terrain, but, frustratingly, the algorithm generates them anyway, again and again. I was careful to use 'orientation' there, rather than 'design', as nothing is consciously planned or arranged: the algorithm itself is designed, but the output is entirely non-engineered.

Another lesson recognised rapidly but appreciated much later is that evolution is s-l-o-w. I've had an iteration running in another tab all morning, and though the line of best fit on the graph of average distance travelled by each generation is showing an upward trend, the rise is only very slight and many mutated individuals are still as wildly inappropriate as at the outset (two-seated unicycles, anyone?). In fact, the overall trend of the last twelve generations has been negative.

For a long time the seemingly optimum form strongly resembled a mountain bike, with medium-sized, equally-sized wheels and the rear 'passenger' slightly lower than the front one, like a bike's saddle being slightly lower than the handlebar. A road bike's profile, with the handlebar lower than the saddle, doesn't work. However, a much longer 'front fork' now seems to be superior – much like a classic, rear-engined dune buggy.
A less-intuitive success features a triangular frame and an alarmingly high centre of gravity. It seems to be constantly about to fall over, but every time it overbalances, a change in slope catches it. It'd probably be totally unsuited to general circumstances, but just about works in this very specific niche.

Here's another example of an evolutionary algorithm, which attempts to reproduce the Mona Lisa using fifty semi-transparent polygons. The objective was achieved remarkably well – in 904,314 generations.


[Update 11/12/08: I left a few iterations running on my office PC overnight, to see the longer-term result. Most stablised after a few hours, with no overall improvement or decline (but still with a huge amount of variability between individual generations), but one was interesting.

The algorithm wasn't optimising particularly well in the first couple of hours, but suddenly made a breakthrough – seemingly in a single generation – on which it very gradually improved for several hours. However, for some reason it went into decline over ~10 generations, its efficiency dropping to virtually baseline, before recovering to an efficiency still well below the iterations running in the 'parallel universes' of other Firefox tabs. Its current output is a very small, fast vehicle, many individuals of which perform exceptionally well, but the tolerances are tight, and are exceeded by about as many mutations as succeed, so the average efficiency of an entire generation (20 mutations) is poor.]

.
Site Home Tull Tour History Annotated Passion Play
.
Day in the life... Page design and original graphics © NRT, 2003