Cellular Automata and Fractal Evolution

Genetic Algorithms and Artificial Evolution of Cellular Automata

One of the first tests of genetic algorithms on cellular automata was the density of live cells problem:

if the initial generation has more live cells than dead cells, the CA should (eventually) produce all live cells;

if the initial generation has more dead cells than live cells, the CA should (eventually) produce all dead cells.

This problem was proposed as a method of evolving Class IV CA. The density of live cells is a global property, but CA rules are local. To solve this problem, a CA must transmit information across space and time, and remember results of previous generations. These are the characteristics of Class IV CA.

Here are the basic steps of the Genetic Algorithm approach to solving Density of Live Cells Problem.

The initial population consists of randomly distributed CA rules.

Each CA is tested against the same set of random initial generations with different densities of live cells.

The fitnness of each CA is the average of how close to the target state it comes for each initial generation.

More fit CA survive and reproduce by crossover and occasional mutation; less fit are removed from the population.

Here is an example.

Return to Genetic Algorithms.