Abstract
Self-modifying Cartesian Genetic Programming (SMCGP) is a general purpose, graph-based, developmental form of Genetic Programming founded on Cartesian Genetic Programming. In addition to the usual computational functions, it includes functions that can modify the program encoded in the genotype. This means that programs can be iterated to produce an infinite sequence of programs (phenotypes) from a single evolved genotype. It also allows programs to acquire more inputs and produce more outputs during this iteration. We discuss how SMCGP can be used and the results obtained in several different problem domains, including digital circuits, generation of patterns and sequences, and mathematical problems. We find that SMCGP can efficiently solve all the problems studied. In addition, we prove mathematically that evolved programs can provide general solutions to a number of problems: n-input even-parity, n-input adder, and sequence approximation to π.
Similar content being viewed by others
Notes
With the exception of recent work in AVIDA, which takes a more utilitarian approach [37].
In this model, if a node wishes to connect to a negative address, a default value is returned. For binary problems this value is FALSE, for numeric problems the default value is 0. INP, INPP and SKIPINP are all terminal functions with no inputs. So connection genes are ignored
Tested using the mpmath library for Python: http://www.code.google.com/p/mpmath/.
References
C. Adami, C. Brown, Evolutionary learning in the 2d artificial life system AVIDA, in Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems (MIT Press, 1994), pp. 377–381
I. Aleksander, Neural Computing Architectures: The Design of Brain-Like Machines (MIT Press, Cambridge, 1989)
M. Arnold, S. Fink, D. Grove, M. Hind, P. Sweeney, A survey of adaptive optimization in virtual machines. Proc. IEEE 93, 449–466 (2005)
J. Aycock, A brief history of just-in-time. ACM Comput. Surv. (CSUR) 35, 97–113 (2003)
W. Banzhaf, G. Beslon, S. Christensen, J.A. Foster, F. Képès, V. Lefort, J.F. Miller, M. Radman, J.J. Ramsden, From artificial evolution to computational evolution: a research agenda. Nat. Rev. Genet. 7, 729–735 (2006)
W. Banzhaf, J. Miller, The challenge of complexity, in Frontiers in Evolutionary Computation, ed. by A. Menon (Kluwer Academic, Boston, MA, 2004), pp. 243–260
P. Bentley, Fractal proteins. Genet. Program. Evol. Mach. 5(1), 71–101 (2004)
P. Bentley, S. Kumar, Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem in Proceedings of the Genetic and Evolutionary Computation Conference, ed. by W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith, vol 1 (Morgan Kaufmann, Orlando, 13–17 1999), pp. 35–43
J. Borwein, D. Bailey, R. Girgensohn, Experimentation in Mathematics—Computational Paths to Discovery (A. K. Peters, Ltd, Ellesley, MA, 2003)
J. Clune, B.E. Beckmann, C. Ofria, R.T. Pennock, Evolving coordinated quadruped gaits with the hyperneat generative encoding in Proceedings of the IEEE Congress on Evolutionary Computing (2009), pp. 2764–2771
N. Doidge, The Brain that Changes Itself: Stories of Personal Triumph from the Frontiers of Brain Science (Penguin Group, USA, 2007)
A. Donlin, Self modifying circuitry—a platform for tractable virtual circuitry in FPL ’98: Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm (Springer, London, 1998), pp. 199–208
T.G. Gordon, P.J. Bentley, Development brings scalability to hardware evolution in EH ’05: Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware (IEEE Computer Society, Washington, DC, 2005), pp. 272–279
F. Gruau, Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm. PhD thesis, Laboratoire de l’Informatique du Parallilisme, Ecole Normale Supirieure de Lyon, France, 1994
F. Gruau, D. Whitley, L. Pyeatt, A comparison between cellular encoding and direct encoding for genetic neural networks in Genetic Programming 1996: Proceedings of the First Annual Conference, ed. by J.R. Koza, D.E. Goldberg, D.B. Fogel, R.L. Riolo. (MIT Press, Stanford University, CA, 28–31 1996), pp. 81–89
S. Harding, J.F. Miller, W. Banzhaf, Self-modifying cartesian genetic programming in GECCO, ed. by H. Lipson (ACM, 2007), pp. 1021–1028
S. Harding, J.F. Miller, W. Banzhaf, Evolution, development and learning with self modifying cartesian genetic programming in Genetic and Evolutionary Computation Conference, GECCO 2009. Accepted for publication. (2009)
S. Harding, J.F. Miller, W. Banzhaf, Self modifying cartesian genetic programming: Fibonacci, squares, regression and summing in EuroGP ’09: Proceedings of the 12th European Conference on Genetic Programming (Springer, Berlin, 2009), pp. 133–144
S. Harding, J.F. Miller, W. Banzhaf, Self modifying cartesian genetic programming: parity in 2009 IEEE Congress on Evolutionary Computation, ed. by A. Tyrrell (IEEE Computational Intelligence Society, IEEE Press, Trondheim, Norway, 18–21 May 2009), pp. 285–292
G.S. Hornby, J.B. Pollack,The advantages of generative grammatical encodings for physical design in Proceedings of the 2001 Congress on Evolutionary Computation CEC2001 (IEEE Press, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27–30 2001), pp. 600–607
P.E. Hotz, Comparing direct and developmental encoding schemes in artificial evolution: a case study in evolving lens shapes in Congress on Evolutionary Computation, CEC 2004 (2004)
L. Huelsbergen, Finding general solutions to the parity problem by evolving machine-language representations in Genetic Programming 1998: Proceedings of the Third Annual Conference, ed. by J.R. Koza, W. Banzhaf et al (Morgan Kaufmann, University of Wisconsin, Madison, 22–25 July 1998), pp. 158–166
IEEE Computer Society, Keywords, http://www.computer.org/portal/web/publications/acmtaxonomy
G. Kampis, Self-Modifying Systems in Biology and Cognitive Science: A New Framework for Dynamics, Information, and Complexity (Pergamon, Oxford, 1991)
G. Kampis, Life-Like Computing Beyond the Machine Metaphor (Chapman and Hall, London, 1993)
G. Kampis, Self-modifying systems: a model for the constructive origin of information. BioSystems 38, 119–125 (1996)
Y. Kanzaki, A. Monden, M. Nakamura, K. Matsumoto, Exploiting self-modification mechanism for program protection in Computer Software and Applications Conference, 2003. COMPSAC 2003. Proceedings of 27th Annual International (2003), pp. 170–179
R. Kicinger, Evolutionary development system for structural design in AAAI Fall Symposium in Developmental Systems (2006)
H. Kitano, Designing neural networks using genetic algorithms with graph generation system. Complex Syst. 4(4), 461–476 (1990)
J. Koza, Genetic Programming: On the Programming of Computers by Natural Selection (MIT Press, Cambridge, 1992)
J. Koza, J. Rice, Genetic Programming (MIT Press, Cambridge, 1992)
J.R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs (MIT Press, Cambridge, 1994)
J. Krohn, P.J. Bentley, H. Shayani, The challenge of irrationality: fractal protein recipes for pi in GECCO, ed. by F. Rothlauf (ACM, 2009), pp. 715–722
S. Kumar, P. Bentley, On Growth, Form and Computers (Academic Press, London, 2003)
W.B. Langdon, W. Banzhaf, Repeated sequences in linear genetic programming genomes. Complex Syst. 15(4), 285–306 (2005)
H. Maturana, F. Varela, Autopoiesis and Cognition: The Realization of the Living (Springer, New York, 1980)
P. McKinley, B. Cheng, C. Ofria, D. Knoester, B. Beckmann, H. Goldsby, Harnessing digital evolution. IEEE Comput. 41(1), 54 (2008)
N.F. McPhee, E.F. Crane, S.E. Lahr, R. Poli, Developmental plasticity in linear genetic programming (ACM, Nominated for best paper award in the GP track in GECCO ’09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, ed. by G. Raidl, F. Rothlauf, G. Squillero, R. Drechsler, T. Stuetzle, M. Birattari, C.B. Congdon, M. Middendorf, C. Blum, C. Cotta, P. Bosman, J. Grahl, J. Knowles, D. Corne, H.-G. Beyer, K. Stanley, J.F. Miller, J. van Hemert, T. Lenaerts, M. Ebner, J. Bacardit, M. O’Neill, M. Di Penta, B. Doerr, T. Jansen, R. Poli, E. Alba. (Montreal, 8–12 July 2009), pp. 1019–1026
J.F. Miller, An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach in Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO) (Morgan Kaufmann, Orlando, 1999), pp. 1135–1142
J.F. Miller, D. Job, V.K. Vassilev, Principles in the evolutionary design of digital circuits—part I. Genet. Program. Evol. Mach. 1(1), 8–35 (2000)
J.F. Miller, S.L. Smith, Redundancy and computational efficiency in cartesian genetic programming in IEEE Transactions on Evoluationary Computation, vol 10 (2006), pp. 167–174
J.F. Miller, P. Thomson, in Proceedings of EuroGP 2000, ed. by R. Poli, W. Banzhaf et al. Cartesian genetic programming. LNCS, vol 1802 (Springer, 2000), pp. 121–132
J.F. Miller, P. Thomson, Lecture Notes in Computer Science in ICES, ed. by A.M. Tyrrell, P.C. Haddow, J. Torresen. A developmental method for growing graphs and circuits, vol 2606 (Springer, 2003), pp. 93–104
P. Nordin, W. Banzhaf, Evolving turing-complete programs for a register machine with self-modifying code in Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95). (1995), pp. 318–325
R. Poli, J. Page, Solving high-order boolean parity problems with smooth uniform crossover, sub-machine code gp and demes. Genet. Program. Evol. Mach. 1(1/2), 37–56 (2000)
S. Rasmussen, C. Knudsen, R. Feldberg, M. Hindsholm, The coreworld: emergence and evolution of cooperative structures in a computational chemistry. Phys. D Nonlinear Phenom. 42(1–3), 111–134 (1990)
T. Ray, An evolutionary approach to synthetic biology: zen and the art of creating life. Artif. Life 1(1–2), 179–209 (1993)
D. Roggen, D. Federici Multi-cellular development: is there scalability and robustness to gain?, in Proceedings of Parallel Problem Solving from Nature 8, PPSN 2004, ed. by X. Yao, E. Burke, J. Lozano et al. (2004), pp. 391–400
R. Rubinstein, J. Shutt, Self-modifying finite automata: an introduction. Inf. Process. Lett. 56(4), 185–190 (1995)
J. Schmidhuber, J. Zhao, N. Schraudolph, Reinforcement learning with self-modifying policies, in Learning to learn, ed. by S. Thrun, L. Pratt (Kluwer, 1997), pp. 293–309
L. Sekanina, M. Bidlo, Evolutionary design of arbitrarily large sorting networks using development. Genet. Program. Evol. Mach. 6(3), 319–347 (2005)
A. Siddiqi, S. Lucas. A comparison of matrix rewriting versus direct encoding for evolving neural networks (1998)
L. Spector, A. Robinson, Genetic programming and autoconstructive evolution with the push programming language. Genet. Program. Evol. Mach. 3, 7–40 (2002)
L. Spector, K. Stoffel, Ontogenetic programming in Genetic Programming 1996: Proceedings of the First Annual Conference, ed. by J.R. Koza, D.E. Goldberg et al. (MIT Press, Stanford University, CA, 28–31 1996), pp. 394–399
K.O. Stanley, Compositional pattern producing networks: a novel abstraction of development. Genet. Program. Evol. Mach. 8, 131–162 (2007)
V.K. Vassilev, J.F. Miller, The advantages of landscape neutrality in digital circuit evolution in Proceedings of ICES, vol 1801 (Springer, 2000), pp. 252–263
J.A. Walker, J.F. Miller, in Proceedings of the 7th European Conference on Genetic Programming (EuroGP). Evolution and acquisition of modules in cartesian genetic programming. Lecture Notes in Computer Science, vol 3003 (Springer, 2004), pp. 187–197
J.A. Walker, J.F. Miller, Automatic acquisition, evolution and re-use of modules in cartesian genetic programming. IEEE Trans. Evol. Comput. 12, 397–417 (2008)
G.C. Wilson, W. Banzhaf, A comparison of cartesian genetic programming and linear genetic programming in Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, ed. by M. O’Neill, L. Vanneschi, S. Gustafson, A.I. Esparcia Alcazar, I. De Falco, A. Della Cioppa, E. Tarantino. Lecture Notes in Computer Science, vol 4971 (Springer, Naples, 26–28 Mar 2008), pp. 182–193
M.L. Wong, Evolving recursive programs by using adaptive grammar based genetic programming. Genet. Program. Evol. Mach. 6(4), 421–455 (2005)
M.L. Wong, K.S. Leung, Evolving recursive functions for the even-parity problem using genetic programming in Advances in Genetic Programming 2, ed. by P.J. Angeline, K.E.E. Kinnear Jr., chapter 11 (MIT Press, Cambridge, 1996), pp. 221–240
M.L. Wong, T. Mun, Evolving recursive programs by using adaptive grammar based genetic programming. Genet. Program. Evol. Mach. 6(4), 421–455 (2005)
T. Yu, Hierachical processing for evolving recursive and modular programs using higher order functions and lambda abstractions. Genet. Program. Evol. Mach. 2(4), 345–380 (2001)
T. Yu, J. Miller, Neutrality and the evolvability of boolean function landscape in Proceedings of EuroGP 2001, ed. by J.F. Miller, M. Tomassini et al. LNCS, vol 2038 (Springer, 2001), pp. 204–217
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Harding, S., Miller, J.F. & Banzhaf, W. Developments in Cartesian Genetic Programming: self-modifying CGP. Genet Program Evolvable Mach 11, 397–439 (2010). https://doi.org/10.1007/s10710-010-9114-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10710-010-9114-1