• The density-classification task
• Two new rules discovered by GEP

The density-classification task is a challenging problem, and different adaptive algorithms, namely, GAs and GP, have been used to try to evolve better than human-written rules. Gene expression programming was also used to evolve better rules for this task (Ferreira 2001), and two new rules were discovered which are not only better than any human-written rule but also better than the rules discovered both by the GA or GP. In this section, I describe these two GEP rules and how they were discovered.

The starting point for the density-classification task was the Gacs-Kurdyumov-Levin (GKL) rule, designed in 1978 by hand to study reliable computation and phase transitions in one-dimensional spatially extended systems (Mitchell 1996). Although not especially designed for the density-classification task, the GKL rule was for some time the rule with the best performance on this task. Its unbiased performance is shown in Table 4.23. In 1993, Lawrence Davis obtained a new rule modifying the GKL rule (Koza et al. 1999). This new rule, Davis rule, achieved an accuracy slightly better than the GKL rule (Table 4.23). Similarly, Rajarshi Das cleverly modified rules discovered by the GA, obtaining a new rule (Das rule) that performed slightly better than the GKL rule and Davis rule (Koza et al. 1999). Genetic programming discovered a new rule (GP rule) slightly better than the previous rules (Koza et al. 1999). Gene expression programming discovered two new rules (GEP₁ and GEP₂ rules) better than all the previous rules (Ferreira 2001). And finally, Juillé and Pollack (1998), using coevolutionary learning, discovered two new rules (Coevolution₁ and Coevolution₂) significantly better than all the previous rules. Their performances are also shown in Table 4.23.

Table 4.23
Accuracies measured at N = 149.

Cellular automata (CA) have been studied widely as they are idealized versions of massively parallel, decentralized computing systems capable of emergent behaviors (for overviews of CA theory and applications see, e.g., Toffoli and Margolus 1987 and Wolfram 1986). These complex behaviors result from the simultaneous execution of simple rules at multiple local sites. In the density-classification task, a simple rule involving a small neighborhood and operating simultaneously in all the cells of a one-dimensional cellular automaton, should be capable of making the CA converge into a state of all 1’s if the initial configuration (IC) has a higher density of 1’s, or into a state of all 0’s if the IC has a higher density of 0’s.