HS-Model: a hierarchical statistical subtree-generating model for genetic programming

ABSTRACT

In genetic programming with subtrees, two issues are crucial: how to acquire promising subtrees efficiently and how to keep these subtrees to be used repeatedly in the evolutional process. In this paper, we propose a hierarchical statistical model for program trees, named HS-Model, to deal with both the above issues. The HS-Model conducts statistic analysis of the current population and generates superior subtrees automatically with efficiency. The HS-Model leaves out the tedious operations to keep the promising subtrees for reusing and also omits updating the subtree library according to certain criterion. Experimental results on solving the classical artificial ant problem proved the effectiveness and the efficiency of our proposed method.

REFERENCES

• 1: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 2: P. Angeline and J. Pollack. Coevolving High-Level Representations. Proceedings of the Third Artificial Life Meeting, C. Langton, (ed.), pages 55--71. Addison-Wesley, 1994.
• 3: D. Howard. Modularization by multi-run frequency driven subtree encapsulation. Genetic Programming Theory and Practise, pages 155--172. Kluwer, 2003.
• 4: Justinian P. Rosca , Dana H. Ballard, Discovery of subroutines in genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
• 5: T. Haynes. On-line adaptation of search via knowledge reuse. Proceedings of the Second Annual Conference, pages 156--161, Stanford University, CA, USA, 1997.
• 6: G. Seront. External concepts reuse in genetic programming. Working Notes for the AAAI Symposium on Genetic Programming, pages 94--98. AAAI Press, Menlo Park, CA, 1995.
• 7: Yoshitaka Kameya , Junichi Kumagai , Yoshiaki Kurata, Accelerating genetic programming by frequent subtree mining, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389332]
• 8: Steffen Christensen , Franz Oppacher, Solving the artificial ant on the Santa Fe trail problem in 20,696 fitness evaluations, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277275]
• 9: W. B. Langdon and R. Poli. Why Ants Are Hard. Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 193--201. Morgan Kaufmann, Madison, USA.1998
• 10: M. Looks. Competent Program Evolution. PhD thesis, pages 17--35, Washington University in St.Louis, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
subroutine