cristobal baray
s100+ pages

Last edited - March / 99


-- Hear and forget; see and remember; do and understand...

1 dimensional cellular automata

(yaca == yet another cellular automata)

A 1-D Cellular Automata that I've hacked up for the Macintosh (it was my first fat app...), via Codewarrior. It was written mainly in order to visualize the rule sets. I was evolving rule sets with a genetic algorithm, but hey, why not put it up here? Most people use a synchronous update rule on their CA's and I wanted to explore the effects of different update rules (mainly asynchronous updates) on the CA's "problem solving" ability. This work was started after listening to Melanie Mitchell talk about her Cellular Automata experiments.

This was all originally written in Scheme, and the GA segment of the work remains in Scheme...sorry about that.

That was written in 1995/6. I was torn between the quick and efficient development environment that scheme gave me and the speed and GUI that C and C++ had to offer. Then came Java. Then came genetic algorithms as virtual user managers. Then came this web-site update, where I was reading what I wrote and I realized that I couldn't let it stay like that. Especially after being touched by my GAVUM architecture. This is exactly what the GAVUM architecture is trying to get rid of.

All too often, we're stuck with just trusting people's stories about their work, unable to reproduce or extend it on our own as questions pop up. I'm trying to make an effort to avoid doing that to others - but this stuff I was writing in 95/96 - I was doing the same thing everyone else was doing. So instead of staying a punk, I re-wrote it in Java.

Here's the applet - if you can't run 1.1 in your browser or if you just prefer a standalone application, grab this .jar file and use the "edu.indiana.cs.cbaray.yaca.CAMain" class to start it up.

This cellular automata is one dimensional, with two states (0 == white, and 1 == black). Each site decides what its next state will be via a lookup table, which relates its current neighborhood (it's own states and itself) to a new value. For instance, a neighborhood of size 3 could have this lookup table :

0 0 0 : 1
0 0 1 : 1
0 1 0 : 0
0 1 1 : 0
1 0 0 : 1
1 0 1 : 1
1 1 0 : 0
1 1 1 : 0
which would toggle the site's state. Regardless of the neighboring sites' states, the new value would be opposite of the current value (middle bit value). This has been a quick and dirty description of the CA - the ECVA group has more on them if you're looking for an intro.

This CA is supposed to calculate the density of the initial conditions. That is, the system is trying to calculate a global characteristic (are there more 1's than 0's?) using only local information (each site can only see 3 neighbors on either side). If there are more 1's than 0's, the system should converge upon all sites being 1. The default rule in the applet works well for the synchronous case, but not so well for any of the asynchronous cases.

Without changing any of the initial conditions, look at the differences that the different updates cause. Immediately it should be clear that the behavior is tied to the update rules. The undeterministic nature of the asynchronous updates illustrates just one of the types of problems one can run into when trying to coordinate behavior with only local information.

The synchronous system takes advantage of the global clock that makes each site update simultaneously. Yet these global clocks are rare in the real world - pushing me to investigate the asynchronous model. Since the previously evolved rules don't perform well in an asynchronous model, the question became, can I evolve new rules to perform well in the asynchronous world. The short answer is a qualified yes...more complete notes of this are in the (lost?) writeup).

Usage notes : Since this was specifically addressing the EVCA models, the neighborhood isn't adjustable - it is set at 7 (3 neighbors on either side). So the rule should stay 128 bits long - or 32 hex characters long. The initial state is 149 bits, or 38 hex characters long. The translation from hex to bits works left to right (zero index is on the left) and will be limited appropriately for the non-multiple of 4 case (149 bits for the initial state), so :

5 A 3 C with a limit of 10 would result in

Explore the effects of the rules on behavior on your own, or evolve your own. To evolve your own, you'll need to write the glue between the GA and the CA. I'd do it for you, except that I think it's a good learning experience and shows the benefits outright of the GAVUM architecture and that I've also got this thesis thing that I'm trying to finish up.

Here's the tar'd and gzip'd source so you can play with it. The GAVUM docs should help one figure out how to write the glue - the basic idea is very similar to the GAVUM example with the resource allocation model. If you get stuck, e-mail me.