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.