ABSTRACT
In this paper we present a new technique for evolving modular programs with genetic programming. The technique is based on the use of "tags" that evolving programs may use to label and later to refer to code fragments. Tags may refer inexactly, permitting the labeling and use of code fragments to co-evolve in an incremental way. The technique can be implemented as a minor modification to an existing, general purpose genetic programming system, and it does not require pre-specification of the module architecture of evolved programs. We demonstrate that tag-based modules readily evolve and that this allows problem solving effort to scale well with problem size. We also show that the tag-based module technique is effective even in complex, non-uniform problem environments for which previous techniques perform poorly. We demonstrate the technique in the context of the stack-based genetic programming system PushGP, but we also briefly discuss ways in which it may be used with other kinds of genetic programming systems.
- P. J. Angeline and J. B. Pollack. Evolutionary module acquisition. In D. Fogel and W. Atmar, editors, Proceedings of the Second Annual Conference on Evolutionary Programming, pages 154--163, La Jolla, CA, USA, 1993.Google Scholar
- W. S. Bruce. The lawnmower problem revisited: Stack-based genetic programming and automatically defined functions. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 52--57. Morgan Kaufmann, 1997.Google Scholar
- H. Curry and R. Feys. Combinatory Logic, 1, 1958.Google Scholar
- D. Hales. Evolving specialisation, altruism, and group-level optimisation using tags. In Proceedings of the 3rd international conference on Multi-agent-based simulation II, MABS'02, pages 26--35, Berlin, Heidelberg, 2003. Springer-Verlag. Google ScholarDigital Library
- E. Hemberg, C. Gilligan, M. O'Neill, and A. Brabazon. A grammatical genetic programming approach to modularity in genetic algorithms. In Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 1--11. Springer, 2007. Google ScholarDigital Library
- J. Holland. The effect of labels (tags) on social interactions. Technical Report Working Paper 93--10-064, Santa Fe Institute, Santa Fe, NM, 1993.Google Scholar
- J. H. Holland. Hidden Order: How Adaptation Builds Complexity. Perseus Books, 1995. Google ScholarDigital Library
- I. Jonyer and A. Himes. Improving modularity in genetic programming using graph-based data mining. In G. C. J. Sutcliffe and R. G. Goebel, editors, Proceedings of the Nineteenth International Florida Artificial Intelligence Research Society Conference, pages 556--561. American Association for Artificial Intelligence, 2006.Google Scholar
- M. Keijzer, C. Ryan, G. Murphy, and M. Cattolico. Undirected training of run transferable libraries. In Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 361--370. Springer, 2005. Google ScholarDigital Library
- K. E. Kinnear, Jr. Alternatives in automatic function definition: A comparison of performance. In K. E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 6, pages 119--141. MIT Press, 1994. Google ScholarDigital Library
- J. Koza. Genetic programming: A paradigm for genetically breeding populations of computer programs to solve problems. Technical Report STAN-CS-90--1314, Dept. of Computer Science, Stanford University, June 1990. Google ScholarDigital Library
- J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. Google ScholarDigital Library
- J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994. Google ScholarDigital Library
- J. R. Koza, David Andre, F. H. Bennett III, and M. Keane. Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufman, Apr. 1999. Google ScholarDigital Library
- X. Li, C. Zhou, W. Xiao, and P. C. Nelson. Direct evolution of hierarchical solutions with self-emergent substructures. In The Fourth International Conference on Machine Learning and Applications (ICMLA'05), pages 337--342. IEEE press, 2005. Google ScholarDigital Library
- T. Perkis. Stack-based genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 148--153. IEEE Press, 1994.Google ScholarCross Ref
- A. Racine, M. Schoenauer, and P. Dague. A dynamic lattice to evolve hierarchically shared subroutines: DL'GP. In W. Banzhaf, R. Poli, M. Schoenauer, and T. C. Fogarty, editors, Proceedings of the First European Workshop on Genetic Programming, volume 1391 of LNCS, pages 220--232. Springer-Verlag, 1998. Google ScholarDigital Library
- R. L. Riolo, M. D. Cohen, and R. Axelrod. Evolution of cooperation without reciprocity. Nature, 414:441--443, 2001.Google ScholarCross Ref
- S. C. Roberts, D. Howard, and J. R. Koza. Evolving modules in genetic programming by subtree encapsulation. In Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 160--175. Springer-Verlag, 2001. Google ScholarDigital Library
- C. Ryan, M. Keijzer, and M. Cattolico. Favorable biasing of function sets using run transferable libraries. In U.-M. O'Reilly, T. Yu, R. L. Riolo, and B. Worzel, editors, Genetic Programming Theory and Practice II, chapter 7, pages 103--120. Springer, 2004.Google Scholar
- M. Schönfinkel. Über die bausteine der mathematischen logik. Mathematische Annalen, 92:307--316, 1924.Google ScholarCross Ref
- S. Shirakawa and T. Nagao. Graph structured program evolution with automatically defined nodes. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1107--1114. ACM, 2009. Google ScholarDigital Library
- H. Simon. The architecture of complexity. In H. A. Simon, editor, The Sciences of the Artificial, pages 84--118. The MIT Press, 1969.Google Scholar
- L. Spector. Simultaneous evolution of programs and their control structures. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 7, pages 137--154. MIT Press, Cambridge, MA, USA, 1996. Google ScholarDigital Library
- L. Spector. Autoconstructive evolution: Push, pushGP, and pushpop. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 137--146. Morgan Kaufmann, 2001.Google Scholar
- L. Spector. Automatic Quantum Computer Programming: A Genetic Programming Approach, volume 7 of Genetic Programming. Kluwer Academic Publishers, Boston/Dordrecht/New York/London, 2004. Google ScholarDigital Library
- L. Spector, D. M. Clark, I. Lindsay, B. Barr, and J. Klein. Genetic programming for finite algebras. In GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1291--1298. ACM, 2008. Google ScholarDigital Library
- L. Spector and J. Klein. Genetic stability and territorial structure facilitate the evolution of tag-mediated altruism. Artificial Life, 12(4):1--8, 2006. Google ScholarDigital Library
- L. Spector, J. Klein, and M. Keijzer. The Push3 execution stack and the evolution of control. In GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 2, pages 1689--1696. ACM Press, 2005. Google ScholarDigital Library
- L. Spector, C. Perry, J. Klein, and M. Keijzer. Push 3.0 programming language description. Technical Report HC-CSTR-2004-02, School of Cognitive Science, Hampshire College, USA, 10 Sept. 2004.Google Scholar
- L. Spector and A. Robinson. Genetic programming and autoconstructive evolution with the Push programming language. Genetic Programming and Evolvable Machines, 3(1):7--40, Mar. 2002. Google ScholarDigital Library
- L. Spector and A. Robinson. Multi-type, self-adaptive genetic programming as an agent creation tool. In A. M. Barry, editor, GECCO 2002: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pages 73--80. AAAI, 2002.Google Scholar
- J. A. Walker and J. F. Miller. The automatic acquisition, evolution and reuse of modules in cartesian genetic programming. IEEE Transactions on Evolutionary Computation, 12(4):397--417, Aug. 2008. Google ScholarDigital Library
- R. P. Wiegand, G. Anil, I. I. Garibay, O. O. Garibay, and A. S. Wu. On the performance effects of unbiased module encapsulation. In GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1729--1736. ACM, 2009. Google ScholarDigital Library
- G. Wijesinghe and V. Ciesielski. Evolving programs with parameters and loops. In IEEE Congress on Evolutionary Computation (CEC 2010). IEEE Press, 2010.Google ScholarCross Ref
Index Terms
Tag-based modules in genetic programming
Recommendations
Modularity metrics for genetic programming
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference CompanionWith improvements in selection methods and genetic operators, Genetic Programming (GP) has been able to solve many software synthesis problems. However, so far, the primary focus of GP has been on improving success rates (fraction of the runs that ...
Tag-based modularity in tree-based genetic programming
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computationSeveral techniques have been developed for allowing genetic programming systems to produce programs that make use of subroutines, macros, and other modular program structures. A recently proposed technique, based on the "tagging" and tag-based retrieval ...
Expressive genetic programming: tutorial: 2012 genetic and evolutionary computation conference (GECCO-2012)
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationThe language in which evolving programs are expressed can have significant impacts on the problem-solving capabilities of a genetic programming system. These impacts stem both from the absolute computational power of the languages that are used, as ...
Comments