Automatic discovery of Interesting Cellular Automata with Genetic Algorithms

Nelson Castillo - Automatic discovery of Interesting Cellular Automata with Genetic Algorithms

"Cellular automata are interesting when their global behavior is more than the sum of the behaviors of their individual parts: the cells. Thus, the individual cells in interesting CA must interact cooperatively in some fashion in support of the global dynamics. In order to do so, cells must communicate information between themselves in a meaningful manner." Gutowitz H., Langton C. [1].

Fractal breeder

Introduction
Here I would like to describe some work I've been doing evolving CA. I've been able to get Interesting CA, although analyzing them is not a trivial task. I wonder whether judging whether a CA is interesting (or beautiful) is a non-computable task. I'll talk about this later. To be honest this project started as an accident and because by the ending of the year 2000 I didn't know that non-uniform cellular automata were better than the uniform ones for random number generation. I had read it, but I wanted to convince myself. I was interested in evolving one-dimensional, k=2, r=2 uniform CA for Random Number Generation. I noticed that sometimes CA with a complex structure (far from random) were obtained. So I started a new project aside from R.N.G. drawing the evolved rules from a few different initial configurations.

Abstract
Genetic Algorithms have been used to evolve Cellular Automata with a desired behavior. An appropriate fitness function is required. Entropy has been used as a fitness function for the evolution of Cellular Automata in order to use them as pseudo random number generators [2]. Here I will describe how a few interesting uniform (k=2,r=2) CA could be evolved using Entropy as a fitness function.

Fitness
Entropy was measured on the Central Cell [2]. The CA was initialized with a constant configuration distributing the bit sequences (1, 11, 101, 111, 1111, 11011, 11111) through the N=50 CA cells. The CA is iterated N/2 time-steps before computing the entropy through 1024*h time-steps.

Genome
A 32-bit string represented each rule. All the possible 2^32 values mapped to a valid rule, therefore some CA rules did not have a quiescent state and the Lambda parameter could not be computed.

Results
Well, here are some of the more interesting CA evolved with this method.

Click on the images to enlarge.
Rules: 3137169065, 2792888933, 3099420589 and 3148502933.

These self-similar fractal-like structures were not uncommon and the GA found many different ways of drawing Sierpinsky-like triangles. Note that 2792888933, 3099420589 and 3148502933 (CA rules) are prime numbers. I still don't know if this is just a coincidence.

Click on the image to enlarge. Rule 2868868760.
There are two progressions in this rule, one (2,3,6,12...) is shown in red and the other is shown in green (2,4,8...). I wonder whether one can demonstrate if that these progressions continue ad infinitum or not. There's something remarkable about this rule: it's one-dimensional but when its two-dimensional space-time diagram is drawn, an illusion of a third dimension appears (as vertical pipes).

Click on the image to enlarge. Rule 3133097257.
This is the most complex rule that the program has been able to evolve. I like to call it "fractal breeder". This rule generates lines of fractals (Sierpinsky triangles) in rows of increasing height. The hypotenuse of the fractals grows according to the progression 1,2,4,8... I wonder if it ever loses this structure. I've drawn big images with this rule and this behavior continues.

To Do : Maybe...

Test whether is more probable to obtain prime rules when maximizing entropy. I think one could run N GAs, count the number of obtained prime rules and then compare it against the theoretical prime number probability (density) of obtaining one between 1 and 2^32 at random.
It would be interesting if one could classify CA rules automatically. I had trouble because I had to analyze many images (7 per GA run). If the rules could be analyzed automatically one could be able to test more initial configurations and more rules per GA run. Although, there's a problem I think: How do we come to the conclusion that the "fractal breeder" is an interesting rule? For instance. Is this a computable task? Can this algorithm be written? Before going philosophical I think there's something that could be tried: use Genetic Programming in order to build a program that can rank CA images according to how interesting they look like. A program could be trained by giving it examples. Each example could be made of an image and a score assigned by a human. The evolved program would have access to a number of statistics extracted from the image. Would it work? I don't know =) I'd like to give it a try.
Is it possible to find fractal-like structures in three dimensions by drawing the space-time diagram of a two-dimensional CA once it's entropy has been maximized using a GA? There is a problem, too. We would not be able to look inside such a figure because we are three-dimensional creatures. Well, computer graphics are advances enough for this task : breaking apart three-dimensional CA.
If entropy is correlated with interesting CA one could rank all the 2^32 d=1,k=2,r=2 CA rules by entropy value. Nowadays this task is feasible and symmetry exists. Then one could analyze the CA starting from more initial configurations and with the rules that attained higher entropy values first. It's easy to use parallelism for this task.
Write a Java Applet for exploring these rules. This will provide interactivity for the user and quality to the image.

Conclusions

It's paradoxical that CA with complex structures can be obtained by maximizing entropy. I'm I wrong?
I'm still confused and I will have to study a lot.

References

[1] Gutowitz H., Langton C. "Methods for Designing 'Interesting' Cellular automata", CNLS News Letter ,1988. [online]
[2] Tomassini M., Sipper M., Zolla M., Perrenoud M, "Generating high-quality random numbers in parallel by cellular automata", Future Generation Computer Systems 16, pp. 291-205, 1999. [online]

Last modified: 22/10/2001, 18:00 PM.
Using HB and vim on GNU/ Linux.

Hosted by www.Geocities.ws