Self-modifying cartesian genetic programming

ABSTRACT

In nature, systems with enormous numbers of components (i.e. cells) are evolved from a relatively small genotype. It has not yet been demonstrated that artificial evolution is sufficient to make such a system evolvable. Consequently researchers have been investigating forms of computational development that may allow more evolvable systems. The approaches taken have largely used re-writing, multi- cellularity, or genetic regulation. In many cases it has been difficult to produce general purpose computation from such systems.In this paper we introduce computational development using a form of Cartesian Genetic Programming that includes self-modification operations. One advantage of this approach is that ab initio the system can be used to solve computational problems. We present results on a number of problems and demonstrate the characteristics and advantages that self-modification brings.

REFERENCES

• 1: W. Banzhaf, G. Beslon, S. Christensen, J. A. Foster, F. Kps, V. Lefort, J. F. Miller, M. Radman, and J. J. Ramsden. From artificial evolution to computational evolution: A research agenda. Nature Reviews Genetics, 7:729--735, 2006.
• 2: W. Banzhaf and J. Miller. The challenge of complexity. In A. Menon, editor, Frontiers in Evolutionary Computation, pages 243--260. Kluwer Academic, 2004.
• 3: P. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 1, pages 35--43, Orlando, Florida, USA, 13-17 1999. Morgan Kaufmann.
• 4: Development Brings Scalability to Hardware Evolution, Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, p.272-279, June 29-July 01, 2005 [doi>10.1109/EH.2005.18]
• 5: F. Gruau. Neural Network Synthesis using Cellular Encoding and the Genetic Algorithm. PhD thesis, Laboratoire de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, France, 1994.
• 6: F. Gruau, D. Whitley, and L. Pyeatt. A comparison between cellular encoding and direct encoding for genetic neural networks. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 81--89, Stanford University, CA, USA, 28-31 1996. MIT Press.
• 7: G. S. Hornby and J. B. Pollack. The advantages of generative grammatical encodings for physical design. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 600-607, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27--30 2001. IEEE Press.
• 8: 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.
• 9: G. Kampis. Self-modifying systems in biology and cognitive science, 1991.
• 10: R. Kicinger. Evolutionary development system for structural design. In AAAI Fall Symposium in Developmental Systems, 2006.
• 11: H. Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex Systems, 4(4):461--476, 1990.
• 12: S. Kumar and P. J. Bentley. On Growth, Form and Computers. Academic Press Inc., US, 2003.
• 13: Lukáš Sekanina , Michal Bidlo, Evolutionary Design of Arbitrarily Large Sorting Networks Using Development, Genetic Programming and Evolvable Machines, v.6 n.3, p.319-347, September 2005 [doi>10.1007/s10710-005-2987-8]
• 14: Julian F. Miller , Peter Thomson, Cartesian Genetic Programming, Proceedings of the European Conference on Genetic Programming, p.121-132, April 15-16, 2000
• 15: J. F. Miller and P. Thomson. A developmental method for growing graphs and circuits. In Proceedings of the 5th International Conference on Evolvable Systems: From Biology to Hardware, volume 2606 of Lecture Notes in Computer Science, pages 93--104. Springer, 2003.
• 16: D. Roggen and D. Federici. Multi-cellular development: is there scalability and robustness to gain? In X. Yao, E. Burke, and J. L. et al., editors, proceedings of Parallel Problem Solving from Nature 8, Parallel Problem Solving from Nature (PPSN) 2004, pages 391--400, 2004.
• 17: A. Siddiqi and S. Lucas. A comparison of matrix rewriting versus direct encoding for evolving neural networks. In Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, (Piscataway, NJ, USA), pages 392--397. IEEE Press, 1998.
• 18: L. Spector and K. Stoffel. Ontogenetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 394--399, Stanford University, CA, USA, 28-31 1996. MIT Press.
• 19: James Alfred Walker , Julian Francis Miller, Investigating the performance of module acquisition in cartesian genetic programming, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068287]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms

Keywords:
developmental systems, evolution, genetic programming, self modification