skip to main content
10.1145/2001576.2001767acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Tag-based modules in genetic programming

Published:12 July 2011Publication History

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.

References

  1. 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 ScholarGoogle Scholar
  2. 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 ScholarGoogle Scholar
  3. H. Curry and R. Feys. Combinatory Logic, 1, 1958.Google ScholarGoogle Scholar
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  6. 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 ScholarGoogle Scholar
  7. J. H. Holland. Hidden Order: How Adaptation Builds Complexity. Perseus Books, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle Scholar
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. 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 ScholarGoogle ScholarCross RefCross Ref
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. R. L. Riolo, M. D. Cohen, and R. Axelrod. Evolution of cooperation without reciprocity. Nature, 414:441--443, 2001.Google ScholarGoogle ScholarCross RefCross Ref
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle Scholar
  21. M. Schönfinkel. Über die bausteine der mathematischen logik. Mathematische Annalen, 92:307--316, 1924.Google ScholarGoogle ScholarCross RefCross Ref
  22. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  23. H. Simon. The architecture of complexity. In H. A. Simon, editor, The Sciences of the Artificial, pages 84--118. The MIT Press, 1969.Google ScholarGoogle Scholar
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. 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 ScholarGoogle Scholar
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  30. 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 ScholarGoogle Scholar
  31. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  32. 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 ScholarGoogle Scholar
  33. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  34. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  35. G. Wijesinghe and V. Ciesielski. Evolving programs with parameters and loops. In IEEE Congress on Evolutionary Computation (CEC 2010). IEEE Press, 2010.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Tag-based modules in genetic programming

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation
      July 2011
      2140 pages
      ISBN:9781450305570
      DOI:10.1145/2001576

      Copyright © 2011 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 12 July 2011

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate1,669of4,410submissions,38%

      Upcoming Conference

      GECCO '24
      Genetic and Evolutionary Computation Conference
      July 14 - 18, 2024
      Melbourne , VIC , Australia

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader