GEP Rules for the
Density-Classification Problem

  CA rules for the density-classification problem evolved by GEP

  GEP evolved two new rules (GEP1 and GEP2) for this difficult problem that are better than any human-written rule and better than the rule evolved by GP. To discover GEP1, 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 GEP1 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).

  GEP2, slightly better than GEP1, 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 GEP2 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

***


Last update: 23/July/2013
 
© Candida Ferreira
All rights reserved.