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?