Discovery by Genetic Programming of a Cellular Automata Rule that is Better than any Known Rule for the Majority Classification Problem   [GP] [CA]

by

Andre, D., Bennett III, F., H. and Koza, J., R.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: Genetic Programming 1996: Proceedings of the First Annual Conference (Conference proceedings), 1996, p. 3-11
Keywords:Genetic Programming, Genetic Algorithms
Abstract:
It is difficult to program cellular automata. [CA] 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. [CA] This paper describes how genetic programming [GP] with automatically defined functions [ADF] 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 [GP] 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.
Notes:
GP-96
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{andre:1996:camc,
  author =       "David Andre and Forrest H {Bennett III} and John R.
                 Koza",
  title =        "Discovery by Genetic Programming of a Cellular
                 Automata Rule that is Better than any Known Rule for
                 the Majority Classification Problem",
  booktitle =    "Genetic Programming 1996: Proceedings of the First
                 Annual Conference",
  editor =       "John R. Koza and David E. Goldberg and David B. Fogel
                 and Rick L. Riolo",
  year =         "1996",
  month =        "28--31 " # jul,
  keywords =     "Genetic Programming, Genetic Algorithms",
  pages =        "3--11",
  address =      "Stanford University, CA, USA",
  publisher =    "MIT Press",
  URL =          "http://www-cs-faculty.stanford.edu/~koza/gp96.gkl.ps",
  size =         "9 pages",
  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.",
  notes =        "GP-96",
}