Introduction to Complexity: Evolving Cellular Automata with Genetic Algorithms Part 3


Here is a picture of the behavior of one evolved cellular automaton that had high fitness. You can see it’s behavior. Here is a majority black initial configuration. Here is the one dimensional lattice… and then over time we see these patterns start to emerge and then finally down here at the bottom, we get an all black configuration. So it had correct behavior. Similarly, it had correct behavior on a different initial configuration with majority white. A question is, how exactly is it doing this computation? How is it transferring and processing information in a collective way without any central control to decide a property of the entire initial lattice? And this turns out to be an important question in general. How is it that decentralized systems, complex systems with no central control … simple components and so on, how is it that they process information? We’ll talk more about that in the next unit on self organization in nature. But I want to tell you about how we ourselves thought about this in the cellular automaton case. The bigger question is, how do we describe information processing in complex systems? In these cellular automata, we notice that there are some simple looking patterns. There’s an all black pattern There’s an all white pattern. and there’s this kind of grayish pattern which turns out to be a checker board like pattern with alternating black and white cells. Those are the three kinds of patterns we see after the initial transient behavior. Now we know that those patterns themselves are too simple to actually be performing this computation of deciding whether black or white is in the majority… so what we do is that we can filter them out. So I filtered out the checker board, the black and the white pattern… and all we are left with are the boundaries between those patterns. What we were able to show in our work is that these boundaries are what are performing the computation. So we call these particles in analogy with particles in physics or particles I showed you in rule 110. They are consistent localized patterns that are long lived. We give them Greek letter labels which is what you do for particles and what we can now do is make a catalog… of all the types of particles we see with this cellular automata given different initial configurations and what their interactions are. But I’m not going into detail in this table. I’ve put a paper of ours on the course materials website… and you can download it if you are interested in reading about the details of this project. But you can see that we have particle reactions where a beta particle meets a gamma particle, there’s a beta particle meets a gamma particle, they collide and the result is an eta particle. And each of these particles have a specific signature of a pattern, a kind of pattern in this, so you see this eta particle here, this Greek letter eta… has the same pattern as this eta particle, the same velocity and so on. What we do with this is that we were able to show that these laws of particle physics, if you will, in this little world of this cellular automata… give rise to the computation of majority black or white in the whole lattice. It’s these particles that carry the information about different regions and when they collide the information is combined or processed… and the new particle that results carries the information that has been processed. It carries the result of that information processing until finally we get the particles annihilating and the final answer to the question posed by the initial configuration. As we explain in out paper, we can get an explanation at this level of particles that’s hard to get at the level of the black or white cells of the cellular automaton. We can explain why one cellular automaton is fitter than another, what mistakes they make… and how it was that the genetic algorithm produced the observed series of innovations that we saw in order to reach our high fitness cellular automata. In short, the particles give an information processing description of the collective behavior. And we believe this type of information processing description in terms of these kind of particles is actually more general than just to the cellular automata. Let me give one example of this. I’m going to show you a few generations from one run of the genetic algorithm. At generation 8, the strategy was always turn black no matter what the initial configuration. Well, if half of the initial configurations have a majority of black, which they did and half have a majority of white… this got a fitness of one half (1/2) which is better than the random cellular automata in the initial configuration, I’m sorry, in the initial population which got fitnesses of zero (0). So this was a big innovation. So it’s like always saying “yes”. You got 50% of the yes or no questions right. So the genetic algorithm discovered that. It went on to make gradual improvements to its strategy but I’m going to focus on one particular improvement. At generation 17, the best individual in the population looked a lot like that one that I showed you a few slides ago… where we have this checker board pattern and these regions of black and white. However, its fitness was much lower than its child at generation 18. And in fact, this pattern, this initial pattern has a majority of white cells so generation 17 is getting it wrong whereas generation 18 is getting it right. So what’s the difference? Well, it’s hard to figure out the difference by looking at the strings of ones and zeroes. It’s very difficult to figure out how the strings of ones and zeroes making up the rule table map onto this behavior. But we can look at this in terms of particles and understand that here the black to white boundary, this particle, beta in my previous diagram, here it has a slope. Whereas here, it’s vertical. So here, it’s the slope is giving unfair advantage to the black region. It’s letting the black region grow and cutting off the white region. Whereas here, black and white have no advantage over one another and correctly, the white region gets to win out. So this is an example where the levels of particles lets us understand an information processing improvement from one step to another. And you can think of the genetic algorithm as crossing over and mutating bits in the rule table string but at a higher level what it’s doing is changing the shapes and velocities of particles. So this is all I’m going to say about this for now. You can read our paper on this topic and it will tell you a lot more details about what we did if you’re interested. Now it’s time to go on to the homework and after that, we’ll start on self organization in nature. Subtitles by the Amara.org community

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *