Evolution of Intricate Long-Distance Communication Signals in Cellular Automata using Genetic Programming   [CA] [GP]

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: Artificial Life V: Proceedings of the Fifth International Workshop on the Synthesis and Simulation of Living Systems (Conference proceedings), 1996
Keywords:genetic algorithms, genetic programming
Abstract:
It is exceedingly 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 of time and space 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:
Alife-5 A longer version of this paper will be presented at the GP-96 conference. GP gets best solution to GKL problem "The population size used to evolve the current world's record for the GKL majority classification 1-dimensionall 2-sate 7-neighbor cellular authomata problem was 51,200. I believe Melanie Mitchell at the Santa Fe Institute has been doing continuing additional work on using GAs to evolve CA rules for various other problems."
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry




BibTex:
@InProceedings{andre:1996:GKL,
  author =       "David Andre and Forrest H {Bennett III} and John R.
                 Koza",
  title =        "Evolution of Intricate Long-Distance Communication
                 Signals in Cellular Automata using Genetic
                 Programming",
  booktitle =    "Artificial Life V: Proceedings of the Fifth
                 International Workshop on the Synthesis and Simulation
                 of Living Systems",
  year =         "1996",
  volume =       "1",
  address =      "Nara, Japan",
  publisher_address = "Cambridge, MA, USA",
  month =        "16--18 " # may,
  publisher =    "MIT Press",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://www-cs-faculty.stanford.edu/~koza/alife-gkl-96.ps",
  size =         "8 pages",
  abstract =     "It is exceedingly difficult to program cellular
                 automata. This is especially true when the desired
                 computation requires global communication and global
                 integration of information across great distances of
                 time and space 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 =        "Alife-5 A longer version of this paper will be
                 presented at the GP-96 conference. GP gets best
                 solution to GKL problem

                 {"}The population size used to evolve the current
                 world's record for the GKL majority classification
                 1-dimensionall 2-sate 7-neighbor cellular authomata
                 problem was 51,200.

                 I believe Melanie Mitchell at the Santa Fe Institute
                 has been doing continuing additional work on using GAs
                 to evolve CA rules for various other problems.{"}",
}