The Result

Genetic programming evolved a cellular automata rule for the majority classification problem that is better than the Gacs-Kurdyumov-Levin (GKL) rule and all other known rules written by humans as described in Andre, Bennett, and Koza (1996) and section 58.4 of Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999).

The table below shows the genetically evolved cellular automata rule.

Rule	State Transition Rule	Accuracy
Gacs-Kurdyumov-Levin (GKL) 1978 human-written	00000000 01011111 00000000 01011111 00000000 01011111 00000000 01011111 00000000 01011111 11111111 01011111 00000000 01011111 11111111 01011111	8l.6%
Davis 1995 human-written	00000000 00101111 00000011 01011111 00000000 00011111 11001111 00011111 00000000 00101111 11111100 01011111 00000000 00011111 11111111 00011111	81.800%.
Das (1995) human-written	00000111 00000000 00000111 11111111 00001111 00000000 00001111 11111111 00001111 00000000 00000111 11111111 00001111 00110001 00001111 11111111	82.178%
Best rule evolved by genetic programming (1999)	00000101 00000000 01010101 00000101 00000101 00000000 01010101 00000101 01010101 11111111 01010101 11111111 01010101 11111111 01010101 11111111	82.326%

Basis for Claim of Human-Competitiveness

The out-of-sample error rates for all four algorithms created by genetic programming are better than the error rates for the three human-written algorithms (the first three rows of table 16.5 of Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999).

Referring to the eight criteria in chapter 1 of Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999) for establishing that an automatically created result is competitive with a human-produced result, the automatic synthesis of a cellular automata rule for the majority classification problem that is better than the Gacs-Kurdyumov-Levin (GKL) rule and all other known rules written by humans satisfies the following two criteria:

(D) The result is publishable in its own right as a new scientific result (independent of the fact that the result was mechanically created).

(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions.

References

Andre, David; Bennett, Forrest H, III; and Koza, John R. 1996a. Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem. In Koza, John R.; Goldberg, David E.; Fogel, David B.; and Riolo, Rick L. (eds.). Genetic Programming 1996: Proceedings of the First Annual Conference, July 28-31, 1996, Stanford University. Cambridge, MA: MIT Press. pp.3-11.

Das, Rajarshi; Crutchfield, J. P.; Mitchell, Melanie; and Hanson, J. E. 1995. Evolving globally synchronized cellular automata. In Eshelman, Larry J. (ed.). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann.

Gacs, Peter; Kurdyumov, G. L.; and Levin, L. A. 1978. One dimensional uniform arrays that wash out finite islands. Problemy Peredachi Informatsii 12:92-98.

Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A. 1999a. Genetic Programming III: Darwinian Invention and Problem Solving. San Francisco, CA: Morgan Kaufmann.

· The home page of Genetic Programming Inc. at www.genetic-programming.com.

· For information about the field of genetic programming and the field of genetic and evolutionary computation, visit www.genetic-programming.org

· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most published papers) and the home page of John R. Koza at Stanford University

· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University

· Information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection, the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs, the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving, and the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic Programming IV book in PDF format.

· 3,440 published papers on genetic programming (as of November 28, 2003) in a searchable bibliography (with many on-line versions of papers) by over 880 authors maintained by William Langdon’s and Steven M. Gustafson.

· For information on the Genetic Programming and Evolvable Machines journal published by Kluwer Academic Publishers

· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals

· For information about the annual Genetic and Evolutionary Computation (GECCO) conference (which includes the annual GP conference) to be held on June 26–30, 2004 (Saturday – Wednesday) in Seattle and its sponsoring organization, the International Society for Genetic and Evolutionary Computation (ISGEC). For information about the annual Euro-Genetic-Programming Conference to be held on April 5-7, 2004 (Monday – Wednesday) at the University of Coimbra in Coimbra Portugal. For information about the 2003 and 2004 Genetic Programming Theory and Practice (GPTP) workshops held at the University of Michigan in Ann Arbor. For information about Asia-Pacific Workshop on Genetic Programming (ASPGP03) held in Canberra, Australia on December 8, 2003. For information about the annual NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle.

Last updated on December 28, 2003