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.