Bluenome
Two bluenome patterns evolved to optimize different objectives.
Bluenome is an algorithm for growing patterns on a grid. It is inspired by embryogenesis, or the biological phenomenon where a single cell grows into an organism.
We start with a "petri dish", or a two-dimensional grid of cell locations. A single cell is placed into the centre of the space. Next, over time, each cell in the space queries its genome for what to do next, then executes a cell action: divide, specialize, etc. Over time, the single cell becomes a multi-cellular pattern. By optimizing the genome, we can control what pattern is produced,
Initial experiments showed that results were evolvable, that is, the we could control the algorithm via a machine learning technique, and after some reasonable amount of experimentation, find good genomes (programs).
At first, we showed that Bluenome images could be grown which maximize certain functional constraints. For instance, images which were very noisy (maximizing an entropy-like function), or images which generated disconnected but similar regions, etc.
An evolved genome re-expressed under environmental perturbations. Left: original petri dish. Middle: different sized petri dish. Right: growth around an obstacle (black square).
Interestingly, a resistance to environmental perturbation was discovered: by changing the size of the petri dish, or by placing "obstacles" in the space, small changes were made to the environment of development for the genomes. As measured by several distinct objective functions, growth managed to achieve good results despite these changes.
Perhaps the simplest Bluenome agent capable of finding food.
Next we defined a simulated 2D robotics task. An organism was taken to be a collection of "cells", each of which played a role in conjunction with its local neighbours. Cells were of type: Eye, Nerve, Foot, and Transport. Eye cells would bing if food were visible, nerve cells would pass transformed inputs from senders to receivers, foot cells would contribute some forward vector or radial vector to overall motion, and transport cells would absorb food directly underneath them, and pass that food to neighbouring cells. The task of any organism was to see food, move to place its transport cells over top of the source, and transmit that food throughout the body.
Through a genetic algorithm, and several different worlds (placements of food in an otherwise empty space), many successful agents were discovered. It was shown that Bluenome was more evolvable than a direct encoding at larger sizes.
One agent genome expressed at size 8 and size 20.
Several distinct strategies were identified: for instance, the most successful strategy was the "rotate-then-forward" strategy. Here, an agent rotates applying a minor forward motion, until food is seen by one of few eye cells at the agent's front. This causes the agent to search the space in a outward spiral. Once food is seen, the rotation stops, and the agent moves directly forward to the food source. Once over top of the food source, the agent no longer has food in its sight lines, and restarts the rotation movement, which both tends to place mouth cells over top of the food, and begins the search for the next food source.
We next re-grew some successful agents at different sizes, showing that genomes could be regrown at larger or smaller scales while still retaining much of their functional abilities.
For more information, see our GECCO 2004 paper or my M.Sc. thesis.