GEP evolved two new rules (GEP₁ and GEP₂) for this difficult problem that are better than any human-written rule and better than the rule evolved by GP. To discover GEP₁, an initial population of 30 individuals evolved for 50 generations, and their fitness was evaluated against 25 initial configurations (ICs). It has an accuracy of 0.82513 tested over 100,000 unbiased ICs in a 149x298 lattice, thus better than the 0.824 of the GP rule tested in a 149x320 lattice [1]. Some space-time diagrams are shown in the GEP₁ gallery.

  As a comparison, GP used populations of 51,200 individuals and 1000 ICs for 51 generations [2], thus a total of 51,200 x 1000 x 51 = 2,611,200,000 fitness evaluations, whereas GEP only made 30 x 25 x 50 = 37,500 fitness evaluations.
Therefore GEP outperforms GP in more than 4 orders of magnitude (69,632 times).

  GEP₂, slightly better than GEP₁, was discovered using population sizes of 50, 50 generations, and 100 ICs. It has an accuracy of 0.82513, again tested over 100,000 unbiased ICs in a 149x298 lattice. Some space-time diagrams are shown in the GEP₂ gallery.

Bibliography:
1. Juillé, H., and Pollack, J. B. (1998). Coevolving the “ideal” trainer: Application to the discovery of cellular automata rules. In J. R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. L. Riolo, eds., Genetic Programming 1998: Proceedings of the Third Annual Conference. Morgan Kaufmann, San Francisco, CA.

2. Koza, J. R., Bennett III, F. H., Andre, D., and Keane, M. A. (1999). Genetic Programming III: Darwinian Invention and Problem Solving. San Francisco: Morgan Kaufmann Publishers.

Back

***