Source:
Genetic Programming 1996: Proceedings of the First Annual Conference, MIT Press, Stanford University, CA, USA, p.3--11 (1996)
URL:
http://www.genetic-programming.com/jkpdf/gp1996gkl.pdf
Keywords:
genetic algorithms;
genetic programming
Abstract:
It is difficult to program cellular automata. This is
especially true when the desired computation requires
global communication and global integration of
information across great distances in the cellular
space. Various human- written algorithms have appeared
in the past two decades for the vexatious majority
classification task for one-dimensional two-state
cellular automata. This paper describes how genetic
programming with automatically defined functions
evolved a rule for this task with an accuracy of
82.326%. This level of accuracy exceeds that of the
original 1978 Gacs-Kurdyumov-Levin (GKL) rule, all
other known human-written rules, and all other known
rules produced by automated methods. The rule evolved
by genetic programming is qualitatively different from
all previous rules in that it employs a larger and more
intricate repertoire of domains and particles to
represent and communicate information across the
cellular space.