Recall that the goal is to design a
cellular automaton that will take
an initial configuration
with a majority of white and
eventually end up all white
or vice versa for black.
One solution you might think of
is do a local majority vote in
a each seven cell neighborhood
So if the majority of the cells in
a neighborhood are white
then the center cell should change to white,
and similarly for black.
However, if we actually look at the behavior
of that cellular automaton,
it doesn't actually perform the task.
Here is a one dimensional lattice
laid out across the horizontal.
time zero starting right here, and
and you can see the random
initial configuration, and very quickly
the areas with a majority of black go to black
and the areas with a majority of
white go to white
but there is a boundary between them
because here we have four blacks and
three whites next to three blacks
and four whites and that just stays black
and white boundary throughout
the rest of time.
So the problem is that there is no way for,
say, this majority black clump
to communicate with this majority black clump
and to process their combined information
say, from all the different clumps
that together they all make up a majority
of the whole lattice
So our challenge is to design
a cellular automaton that can take information
from local areas and communicate it
across the lattice,
and have that information combined
so as the whole lattice
can collectively decide whether
there is a majority, total majority,
of white or black.
That turns out to be non-trivial.
Instead of designing this ourselves,
what we are going to do is use
a genetic algorithm to evolve
cellular automata to have the desired behavior.
So this is going to look familiar to you
after having seen the Robby the Robot genetic
algorithm example because
it has a lot in common.
To summarize the genetic algorithm again,
we are going to create
a random population of candidate
cellular automata rules.
The fitness of each cellular automaton
is how well it performs
the majority classification task.
The fittest cellular automata get to reproduce
with mutations and crossovers,
and we just continue this process
for many generations.
So you've seen all this before.
Remember the DNA for Robby was his strategy
Similarly, the DNA of a cellular automaton
is an encoding of its rule table
So if we have a rule table that looks like this.
We assign each white output cell as zero,
each black output cell a one,
and this listing of 128 ones and zeros
is the DNA that is going to be evolved
So we create a population of random strings
that represent the cellular automaton
rule tables. So each one of these strings
is a list of 128 bits, or ones and zeros.
Here I have a hundred of them
but you can decide what the population size
should be yourself.
We're going to calculate the fitness of a rule,
and the way to do that is similar to Robby.
We create several different environments
and test the rule on those environments
where the environments here
are going to be
initial configurations of lattices
and the fitness of a rule is the fraction of
correct classifications.
So remember when I say rule here,
I really mean rule table where a rule
consists of those 128 update states
that tells the cellular automaton what the
center cell should be
in every possible neighborhood.
So here is a diagram that shows you
how this works.
For each cellular automaton rule
in the population, here is one of those rules
You create the rule table that corresponds to it
Here it is again, and now I'm going to run
the corresponding cellular automaton
using this rule on many random
initial lattice configurations
So here is an initial configuration
and it is updated by the rule.
We designate some number of
maximum time steps for these updates
to take place. and its
and if the behavior of the cellular automaton
at the final time step is not
the correct answer here.
If there were say, a majority
of black cells it should have been all black
but it's not. It gets classified as incorrect.
There is no partial credit given
for some number of black cells.
It's either correct or it's incorrect.
This one is incorrect.
This one is actually correct because after
a majority of white cells, and within
the maximum number of time steps
it goes to all white and so on.
Fitness is just the fraction of those
correct classifications
So the fitness is between zero and one
Now let's see how the algorithm works
We have a population of
random cellular automata rule tables.
Now suppose the fitness has been calculated
as follows.
What happens is that the fittest rules
are selected to reproduce themselves
For example, we might choose rule one and
and rule three to be parents.
We would create a new generation
via crossover and mutation
each pair of parents would
crossover at a randomly selected location
and the children would take the first part
from one parent,
and the second part
from the second parent
and vice versa.
So here we are creating two children
from every two parents.
We might do some random mutations.
If this digit was selected to mutate
it would be changed to a zero,
and now we have two children
And we continue this process
of selecting parents, and creating children
until a new generation is complete.
Then we calculate the fitness of
the new generation and so on.
keep iterating this for many generations
When the genetic algorithm is finished
we're really in the same situation
we were with the Robby Robot example.
Tthe genetic algorithm has given us
this string of bits, 128 bits,
and says it has high fitness.
But now we're left with the prospect
of trying to understand why it works.