Evolving Cellular Automata

with Genetic Algorithms

In this subunit I'm going to talk about a project

I worked on several years ago

with Jim Crutchfield

who you've heard from before, and

Rajanhi Das who's at the IBM Research Center.

This was a project on evolving

cellular automata with genetic algorithms.

to perform collective computations.

I've linked this paper,

The Review of Recent Work,

from the course materials web page

We looked at a particular

computational task for cellular automata.

One that was originally proposed

by Norman Packard.

The task is to design a cellular automaton

that decides whether or not

the initial configuration of cells has

a majority of black cells

So here's the picture,

here's an initial configuration on

on a one dimensional cellular automaton

were there's one, two, three, four, five, six,

seven, eight, nine, ten, eleven cells

and six of them are black,

so there's a majority of black cells.

The desired behavior would be after

some number of time steps for

the whole lattice to turn black.

Similarly, If you started with a majority of

white cells you'd like the whole lattice

to turn white at the next time step

This is a simple to describe

computational task, but variations of it have

important applications in computing,

particularly in the field of distributed computing

So the question is

"how do we design a cellular automaton

to do this. Well, one point to make is that

if you have a standard or traditional

computer that has a central processing unit

and random access memory

it's not hard to design a program to

figure out if you have a majority of black

or a majority of white cells stored

somewhere in memory.

All you would do is write a program that

would go to those memory locations,

count up the number of black cells

using a centralized counter,

and a centralized place in memory to keep

the count, and figure out which is greater

But recall that cellular automata

doesn't have any centralized control

it doesn't have any random access memory.

All it has are the individual cells

which are connected to their neighbors

so it's not immediately clear

how to design a cellular automaton

to perform this task

As I discussed before, there are

256 elementary cellular automata.

We know what all of them do,

what their behavior is, and we know

that none of them perform this task

As it turns out, the cellular automata

where each cell has four neighbors

the two nearest neighbors on either side

also don't perform this task.

So we looked at cellular automata

in which each cell has six neighbors,

the three nearest neighbors on each side.

The rule table for this kind

of cellular automata gives all

the possible configurations of neighborhoods

of seven cells, and specifies for

each configuration what the update state

should be of the center cell at the

next time step.

A quick quiz,

our quiz has two questions,

they're both counting questions and I hope

you are iind of getting used to these.

The first question is

For a cellular automata like this

with the seven cell neighborhood,

how many possible

neighborhood configurations are there?

and the second question is

How many different cellular automata

rule tables are there for seven cell

neighborhood cellular automata?