Binary encoding for prototype tree of probabilistic model building GP

ABSTRACT

In recent years, program evolution algorithms based on the estimation of distribution algorithm (EDA) have been proposed to improve search ability of genetic programming (GP) and to overcome GP-hard problems. One such method is the probabilistic prototype tree (PPT) based algorithm. The PPT based method explores the optimal tree structure by using the full tree whose number of child nodes is maximum among possible trees. This algorithm, however, suffers from problems arising from function nodes having different number of child nodes. These function nodes cause intron nodes, which do not affect the fitness function. Moreover, the function nodes having many child nodes increase the search space and the number of samples necessary for properly constructing the probabilistic model. In order to solve this problem, we propose binary encoding for PPT. Here, we convert each function node to a subtree of binary nodes where the converted tree is correct in grammar. Our method reduces ineffectual search space, and the binary encoded tree is able to express the same tree structures as the original method. The effectiveness of the proposed method is demonstrated through the use of two computational experiments.

REFERENCES

• 1: P. A. N. Bosman and E. D. de Jong. Grammar transformations in an EDA for genetic programming. GECCO 2004 Workshop Proceedings 2004
• 2: Chris Gathercole , Peter Ross, An adverse interaction between crossover and restricted tree depth in genetic programming, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
• 3: Y. Hasegawa and H. Iba. Estimation of distribution algorithm based on probabilistic grammar with latent annotations. Proceedings of IEEE Congress of Evolutionary Computation (CEC 2007) pages 1043--1050, 2007.
• 4: Y. Hasegawa and H. Iba. A Bayesian network approach to program generation. IEEE Transactions on Evolutionary Computation Vol. 12, NO. 6:750--764, 2008.
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: Moshe Looks , Ben Goertzel , Cassio Pennachin, Learning computer programs with the bayesian optimization algorithm, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068134]
• 7: M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms:Fitness landscapes and ga performance. Proceedings of the First European Conference on Artificial Life pages 245--254, 1992.
• 8: J. Očen ášek and J. Schwarz. The parallel Bayesian optimization algorithm. Proceedings of the European Symposium on Computational Intelligence pages 61--67, 2000.
• 9: J. Očen ášek and J. Schwarz. The distributed Bayesian optimization algorithm for combinatorial optimization. In: EUROGEN 2001 - Evolutionary Methods for Design, Optimisation and Control pages 115--120, 2001.
• 10: W. F. Punch. How effective are multiple populations in genetic programming. Genetic Programming 1998: Proceedings of the Third Annual Conference: John R. Koza and Wolfgang Banzhaf and Kumar Chellapilla and Kalyanmoy Deb and Marco Dorigo and David B. Fogel and Max H. Garzon and David E. Goldberg and Hitoshi Iba and Rick Riolo, Eds pages 308-313308-313, 1998.
• 11: Alain Ratle , Michèle Sebag, Avoiding the Bloat with Stochastic Grammar-Based Genetic Programming, Selected Papers from the 5th European Conference on Artificial Evolution, p.255-266, October 29-31, 2001
• 12: E. N. Regolin and A. T. R. Pozo. Bayesian automatic programming. Genetic Programming vol. 3447, Lecture Notes in Computer Science:38--49, 2005.
• 13: K. Sastry, K. Sastry, D. E. Goldberg, and D. E. Goldberg. Probabilistic model building and competent genetic programming. Genetic Programming Theory and Practise, chapter 13 pages 205--220, 2003.
• 14: Rafal Salustowicz , Jürgen Schmidhuber, Probabilistic incremental program evolution, Evolutionary Computation, v.5 n.2, p.123-141, Summer 1997 [doi>10.1162/evco.1997.5.2.123]
• 15: Y. Shan, R. I. Mckay, H. A. Abbass, and D. Essam. Program evolution with explicit learning:a new framework for program automatic synthesis. Proceedings of the 2003 Congress on Evolutionary Computation CEC2003 pages 1639--1646, 2003.
• 16: Y. Shan, R. I. Mckay, and R. Baxter. Grammar model-based program evolution. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation pages 478--485, 2004.
• 17: K. Yanai and H. Iba. Estimation of distribution programming based on Bayesian network. Proceedings of the Congress on Evolutionary Computation 2003 pages 1618--1625, 2003.
• 18: Zhenyu Yang , Ke Tang , Xin Yao, Large scale evolutionary optimization using cooperative coevolution, Information Sciences: an International Journal, v.178 n.15, p.2985-2999, August, 2008 [doi>10.1016/j.ins.2008.02.017]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
genetic programming, probabilistic model building genetic programming, probabilistic prototype tree