The impact of population size on code growth in GP: analysis and empirical validation

ABSTRACT

The crossover bias theory for bloat [18] is a recent result which predicts that bloat is caused by the sampling of short, unfit programs. This theory is clear and simple, but it has some weaknesses: (1) it implicitly assumes that the population is large enough to allow sampling of all relevant program sizes (although it does explain what to expect in the many practical cases where this is not true, e.g., because the population is small); (2) it does not explain what is meant by its assumption that short programs are unfit.

In this paper we discuss these weaknesses and propose a refined version of the crossover bias theory that clarifies the relationship between bloat and finite populations, and explains what features of the fitness landscape cause bloat to occur. The theory, in particular, predicts that smaller populations will bloat more slowly than larger ones. Additionally, the theory predicts that bloat will only be observed in problems where short programs are less fit than longer ones when looking at samples created by fitness-based importance sampling, i.e. samplings of the search space in which fitter programs have a higher probability of being sampled (e.g., the Metropolis-Hastings method). Experiments with two classical GP benchmarks fully corroborate the theory.

REFERENCES

• 1: T. Blickle and L. Thiele. Genetic programming and redundancy. In J. Hopf, editor, Genetic Algorithms within the Framework of Evolutionary Computation (Workshop at KI-94, Saarbrcken), pages 33--38, Saarbrcken, Germany, 1994. Max-Planck-Institut fr Informatik (MPI-I-94-241).
• 2: S. Chib and E. Greenberg. Understanding the metropolis-hastings algorithm. The American Statistician, 49(4):327--335, Nov. 1995.
• 3: Stephen Dignum , Riccardo Poli, Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277277]
• 4: J. R. Koza. A genetic approach to the truck backer upper problem and the inter-twined spiral problem. In Proceedings of IJCNN International Joint Conference on Neural Networks, volume IV, pages 310--318. IEEE Press, 1992.
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: William B. Langdon, Convergence Rates For The Distribution Of Program Outputs, Proceedings of the Genetic and Evolutionary Computation Conference, p.812-819, July 09-13, 2002
• 7: W. B. Langdon. How many good programs are there? How long are they? In K. A. De Jong, et al., editors, Foundations of Genetic Algorithms VII, pages 183--202, Torremolinos, Spain, 4-6 Sept. 2002. Morgan Kaufmann. Published 2003.
• 8: W. B. Langdon. Convergence of program fitness landscapes. In E. Cantú-Paz, et al., editors, Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 of LNCS, pages 1702--1714, Chicago, 12-16 July 2003. Springer-Verlag.
• 9: W. B. Langdon. The distribution of reversible functions is Normal. In R. L. Riolo and B. Worzel, editors, Genetic Programming Theory and Practise, chapter 11, pages 173--188. Kluwer, 2003.
• 10: W. B. Langdon. The distribution of amorphous computer outputs. In S. Stepney and S. Emmott, editors, The Grand Challenge in Non-Classical Computation: International Workshop, York, UK, 18-19 Apr. 2005.
• 11: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 12: W. B. Langdon and R. Poli. The halting probability in von Neumann architectures. In P. Collet, et al., editors, Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, pages 225--237, Budapest, Hungary, 10 - 12 Apr. 2006. Springer.
• 13: Nicholas Freitag McPhee , Riccardo Poli, A Schema Theory Analysis of the Evolution of Size in Genetic Programming with Linear Representations, Proceedings of the 4th European Conference on Genetic Programming, p.108-125, April 18-20, 2001
• 14: Peter Nordin , Wolfgang Banzhaf, Complexity Compression and Evolution, Proceedings of the 6th International Conference on Genetic Algorithms, p.310-317, July 15-19, 1995
• 15: Alan Piszcz , Terence Soule, Dynamics of evolutionary robustness, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144149]
• 16: Riccardo Poli, General Schema Theory for Genetic Programming with Subtree-Swapping Crossover, Proceedings of the 4th European Conference on Genetic Programming, p.143-159, April 18-20, 2001
• 17: R. Poli and W. B. Langdon. Efficient markov chain model of machine code program execution and halting. In R. L. Riolo, et al., editors, Genetic Programming Theory and Practice IV, volume 5 of Genetic and Evolutionary Computation, chapter 13. Springer, Ann Arbor, 11-13 May 2006.
• 18: R. Poli, W. B. Langdon, and S. Dignum. On the limiting distribution of program sizes in tree-based genetic programming. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 193--204, Valencia, Spain, 11 - 13 Apr. 2007. Springer.
• 19: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
• 20: Riccardo Poli , Nicholas Freitag McPhee, General schema theory for genetic programming with subtree-swapping crossover: Part II, Evolutionary Computation, v.11 n.2, p.169-206, Summer 2003 [doi>10.1162/106365603766646825]
• 21: S. Silva and J. Almeida. Dynamic maximum tree depth. In E. Cantú-Paz, et al., editors, Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 of LNCS, pages 1776--1787, Chicago, 12-16 July 2003. Springer-Verlag.
• 22: Terence Soule , James A. Foster, Effects of code growth and parsimony pressure on populations in genetic programming, Evolutionary Computation, v.6 n.4, p.293-309, Winter 1998 [doi>10.1162/evco.1998.6.4.293]
• 23: L. Vanneschi. Theory and Practice for Efficient Genetic Programming. Ph.D. thesis, Faculty of Sciences, University of Lausanne, Switzerland, 2004.
• 24: Leonardo Vanneschi , Yuri Pirola , Philippe Collard, A quantitative study of neutrality in GP boolean landscapes, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144152]

INDEX TERMS

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

General Terms:
Performance

Keywords:
bloat, genetic programming, population size