Discovery of Cellular Automata Rules Using Cases

Ken-ichi Maeda and Chiaki Sakama

Proceedings of the 6th International Conference on Discovery Science (DS'03), Lecture Notes in Artificial Intelligence 2843, pages 360-368, Springer-Verlag, 2003.


Cellular automata (CAs) are used for modeling the problem of adaptation in natural and artificial systems, but it is hard to design CAs having desired behavior. To support the task of designing CAs, this paper proposes a method for automatic discovery of cellular automata rules (CA-rules). Given a sequence of CA configurations, we first collect cellular changes of states as cases. The collected cases are then classified using a decision tree, which is used for constructing CA-rules. Conditions for classifying cases in a decision tree are computed using genetic programming. We perform experiments using several types of CAs and verify that the proposed method successfully finds correct CA-rules.

Full Paper (gzipped postscript 576K) Slide (pdf 304K) © Springer-Verlag