Developmental plasticity in linear genetic programming

ABSTRACT

Biological organisms exhibit numerous types of plasticity, where they respond both developmentally and behaviorally to environmental factors. In some organisms, for example, environmental conditions can lead to the developmental expression of genes that would otherwise remain dormant, leading to significant phenotypic variation and allowing selection to act on these otherwise "invisible" genes. In contrast to biological plasticity, the vast majority of evolutionary computation systems, including genetic programming, are rigid and can only adapt to very limited external changes. In this paper we extend the N-gram GP system, a recently introduced estimation of distribution algorithm for program evolution, using Incremental Fitness-based Development (IFD), a novel technique which allows for developmental plasticity in the generation of linear-GP style programs. Tests with a large set of problems show that the new system outperforms the original N-gram GP system and is competitive with standard GP. Analysis of the evolved programs indicates that IFD allows for the generation of more complex programs than standard N-gram GP, with the generated programs often containing several separate sequences of instructions that are reused multiple times, often with variations.

REFERENCES

• 1: Frédéric Gruau , Darrell Whitley , Larry Pyeatt, A comparison between cellular encoding and direct encoding for genetic neural networks, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
• 2: T.-H. Hoang, D. Essam, R. I. B. McKay, and X. H. Nguyen. Building on success in genetic programming: Adaptive variation&developmental evaluation. In Proceedings of the 2007 International Symposium on Intelligent Computation and Applications (ISICA), Wuhan, China, Sept. 21--23 2007. China University of Geosciences Press.
• 3: J. Koza, F. H. Bennett III, D. Andre, and M. A. Keane. The design of analog circuits by means of genetic programming. In P. Bentley, editor, Evolutionary Design by Computers, chapter 16, pages 365--385. Morgan Kaufmann, San Francisco, USA, 1999.
• 4: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 5: S. Luke. Genetic programming produced competitive soccer softbot teams for RoboCup97. In J. R. Koza, phet al, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 214--222, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.
• 6: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 7: Nicholas Freitag McPhee , Riccardo Poli, Memory with memory: soft assignment in genetic programming, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389336]
• 8: A compiling genetic programming system that directly manipulates the machine code, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 9: M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in a Arbitrary Language, volume 4 of Genetic programming. Kluwer Academic Publishers, 2003.
• 10: R. Poli. Tinygp, 2009. Available at http://cswww.essex.ac.uk/staff/rpoli/TinyGP/.
• 11: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
• 12: R. Poli and N. McPhee. A linear estimation-of-distribution GP system. In M. O'Neill, phet al, editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 206--217, Naples, 26-28 Mar. 2008. Springer.
• 13: T. D. Price, A. Qvarnström, and D. E. Irwin. The role of phenotypic plasticity in driving genetic evolution. Proceedings of the Royal Society of Biological Sciences, 270(1523):1433--1440, July 2003.
• 14: M. Sipper, Y. Azaria, A. Hauptman, and Y. Shichel. Designing an evolutionary strategizing machine for game playing and beyond. Systems, Man and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 37(4):583--593, 2007.
• 15: C. Y. Suen. n-gram statistics for natural language understanding and text processing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(2):164--172, Apr. 1979.
• 16: Y. Suzuki and F. H. Nijhout. Evolution of a polyphenism by genetic accommodation. Science, 311(5761):650--652, February 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming

General Terms:
Algorithms

Keywords:
development, genetic programming, n-grams, plasticity