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?