• Choose a category
• All
• Classic-Fiction

By Root 413 0

candidate is supported by the majority of yard signs among you and your local neighbors. However, this “local majority vote” cellular automaton doesn’t work, as illustrated by the space-time diagram in figure 11.1. The initial configuration has a majority of black cells, and each cell updates its state according to the local majority vote rule over 200 time steps. You can see that the lattice quickly settles into a stable pattern of black and white regions. The boundaries between regions are at locations where majority black neighborhoods overlap with majority white neighborhoods. The final configuration, containing both white and black cells, does not give the desired answer to the majority classification task. The problem is that there is no way, using this rule, for one black region, say, to communicate its length to the other black regions, so that collectively they can determine whether or not they are in the majority.

FIGURE 11.1. Space-time behavior of the “local majority vote” cellular automaton starting from a majority black initial configuration. (Figure adapted from Mitchell, M., Crutchfield, J. P., and Das, R., Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA ’96). Moscow, Russia: Russian Academy of Sciences, 1996.)

It’s not immediately obvious how to design a rule for this task, so in the spirit of Robby the Robot from chapter 9 we ran a genetic algorithm in order to see if it could produce a successful rule on its own.

In our genetic algorithm, cellular automaton rules are encoded as strings of 0s and 1s. These bits give the state-update values for each possible neighborhood configuration (figure 11.2).

The genetic algorithm starts out with a population of randomly generated cellular automaton rules. To calculate the fitness of a rule, the GA tests it on many different initial lattice configurations. The rule’s fitness is the fraction of times it produces the correct final configuration: all cells on for initial majority on or all cells off for initial majority off (figure 11.3). We ran the GA for many generations, and by the end of the run the GA had designed some rules that could do this task fairly well.

As we saw with Robby the Robot, a solution evolved by the genetic algorithm is typically impossible to understand at the level of its “genome.” The cellular automata that we evolved for the majority classification task were no different. The genome of one of the highest-performing cellular automata designed by the GA is the following (split into two lines of text):

0000010100000110000101011000011100000111000001000001010101010111 0110010001110111000001010000000101111101111111111011011101111111

Recall that the first bit is the update state for the center cell in the all 0s neighborhood, the second bit is the update state for center cell in the neighborhood 0000001, and so forth. Since there are 128 possible neighborhoods, this genome consists of 128 bits. Looking at this bit string, there is nothing obvious that gives us a hint as to how this rule will behave, or why it obtained high fitness on the majority classification task.

FIGURE 11.2. Illustration of how a cellular automaton rule is encoded as an individual in the genetic algorithm’s population. The 128 possible neighborhood configurations are listed in a fixed order. The update state for the center cell of each neighborhood configuration is encoded as a 0 (off) or a 1 (on). An individual in the genetic algorithm’s population is a string of 128 bits, encoding the update states in their fixed ordering.

FIGURE 11.3. To calculate its fitness, each rule is tested on many random initial configurations. The fitness of a rule is the fraction of initial configurations on which the rule produces the correct answer within some number of time steps.

Figure 11.4 gives two space-time diagrams that display the behavior of this rule on two different initial configurations: with (a) a majority of black cells