EvoCell - free software for evolving cellular automata

The goal of this talk is to present EvoCell, a free software project released under the GPL. EvoCell is all about simulating and evolving cellular automata so I'll start with a semi-formal of what a cellular automaton is:

A cellular automaton (CA) is a discrete mathematical model that has been used to explore interesting phenomenons like self organisation, emergence, self replication, artificial life and even evolution. A CA is defined by four parameters.

* a grid geometry * a finite number of states * a neighbourhood and * a transition function

The grid geometry defines how the cells are aligned. The CAs presented in the talk will have a 2D rectangular grid with a torus topology (when you leave the grid at the right/bottom side you enter it on the left/top side). At each discrete time t each cell is in one of a finite number of states. The state of each cell at time t+1 is a function of the states of the cell and some surrounding cells - the neighbourhood cells - at time t. The function that maps each possible combination of states of the neighbourhood cells to the target state in the next time step is called the transition function or transition rule.

From this description it is easy to calculate the number of possible transition functions for CAs with N neighbours and S states. Each of the cells in the neighbourhood can be in one of the S states. So there are S^N different states the neighbourhood can be in. For each of these we can assign one of S possible outcomes. This gives S^(S^N) possible different transition functions. This number gets extremely large as S and N increase. So there is a huge space of possible CAs.

EvoCell, the software project I want to introduce in the talk, allows the user to explore this huge space of possible CAs by using genetic algorithms. But why should one want to explore this space? There are a lot of spaces that are huge but nevertheless extremely uninteresting like the space of all possible COBOL programs for example. To show that CAs are worth exploration one only has to look at which interesting rules have already been found by researchers around the world during the last 50 years since John von Neumann proposed the first CA.

The most famous CA is probably Conways's game of life (9 cell neigbourhood, 2 states). The rules for game of life are extremely simple but it shows some remarkable properties like gliders, glider guns and even Turing machines.

Another interesting CA is Langton's Loop. A loop-like structure in a 5 cell neighbourhood, 9 states CA which self replicates. Eventually it self replicates on and on, filling the entire space with loops that become dysfunctional because of collisions with other loops.

A variation of Langton's Loop called the Evoloop solves this problem because it has an additional "death state", which clears the space of dysfunctional loops making space for other loops to replicate into. Due to collisions of the loops during self replication the loop structure sometimes "mutates". Some of the mutated loops are able to replicate faster thus giving rise to evolutionary effects.

So the space of possible CAs includes some interesting points and maybe it is a good idea to use software to search for even more interesting gliders and replicators then the ones described. But how do you explore such a huge space? If the space is "smooth" - that means points in space that are close together have similar properties - then evolution could work. CAs have this property. If you change the transition function only a little then the development of the cells in time will not change too much (at least in the beginning).

EvoCell allows you to do this: To mutate the transition functions of CAs and to watch how these small changes effect the development of cell patterns. A normal EvoCell session runs like this:

1. You start with a CA with some initial transition rule. This could be some simple predefined rule like every-cell-goes-to-state-zero or a rule saved during a previous EvoCell session. 2. Multiple variations of the original rule are according according to user defined mutation parameters. 3. All mutated CAs and the original CA are initialized with a random or predefined cell pattern so the difference in the transition rules can be seen as differences in the development of the cell patterns. 4. Select the most interesting rules and goto step 2.

The EvoCell engine supports arbitrary transition functions, arbitrary neighbourhoods, and arbitrary dimensions, but at this time the display functions have been implemented for 2D only.

But the most interesting part is of course playing around with the CAs :) After some time one gets a feeling for what kind of rules produce what kind of structures. How one has to mutate the get the desired effects. For example it is really easy to evolve simple gliders once you found out what kind of transition rules produce them. Because new rules are always mutated versions of old ones all the rules form an evolutionary tree. It's very interesting so go through some evolutionary line of CAs and see how the rules changed in the course of the human directed evolution. You'll see all that in the talk.