The final two figure (figures 5 and 6) give an indication of how the convergence-time measure can be used to drive an evolutionary process. Figure 5 shows a selection of space-time patterns generated by cellular automata found during a run of the genetic algorithm. As the number of generations increases, rules with longer and longer convergence time (higher "fitness") are found. Each panel shows the most-fit individual at the corresponding generation of the genetic algorithm. These are 8-state, 1-D, nearest-neighbor CA. Convergence time is measured in 2nd-order mean field approximation.
Figure 6 shows the results of a genetic evolution similar to that of figure 5. Here, however, 2-state rules on a hexagonal lattice are used. Further, fitness is not measured using a mean-field approximation to the convergence time, but simply the empirical convergence time as measured by a Monte Carlo method. That the same kind of evolution toward increasing complex rules is found suggests that the convergence-time measure is useful for finding complex rules, independent of the number of states, number of dimensions, neighborhood size, etc. of the rules.
Figure 5. Results of a typical genetic algorithm experiment. In this experiment 8-state radius-1 rules were selected using a genetic algorithm. Fitness was proportional to the the number of iterations required for the order-2 mean field theory to converge. Using a simple genetic algorithm (population size =100), rules exhibiting qualitatively "complex" behavior were found. Each panel here shows the space-time pattern generated by the best-fit individual found at some generation of the genetic algorithm. (Every even-numbered generation up to 20, then generations 24,32,37,44, and 60) The initial population for this run was random. Similar results are obtained if the initial population has other statistics, e.g. consists of all-0 rule tables.
Figure 6. Evolution of Complex 2-D Hexagonal Rules. In this experiment 2-D, 2-state, hexagonal rules were evolved using the convergence-time fitness criterion. The convergence time was measured by tracking the density of 1's in 150 $\times$ 150 hexagonal grid. Population size 20. Shown on the left are space-time cuts through the pattern generated by the most-fit individual at several generations of a simple genetic algorithm. (Small panels, generations: 0, 2, 5, 17, 18, 33, 44, 64, 69, 73, 87, 91, 98, 106, 119. large panel: generation 175) The panel on the right shows the most-fit individual found in the experiment. These data were obtained by Patrice Simon (ESPCI, Paris).