On the Limiting Distribution of Program Sizes in Tree-Based Genetic Programming | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Limiting Distribution of Program Sizes in Tree-Based Genetic Programming

  • Conference paper
Genetic Programming (EuroGP 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4445))

Included in the following conference series:

  • 966 Accesses

Abstract

We provide strong theoretical and experimental evidence that standard sub-tree crossover with uniform selection of crossover points pushes a population of a-ary GP trees towards a distribution of tree sizes of the form:

$$ \Pr\{n\}= (1-ap_a) {a n+1 \choose n} \, (1-p_a)^{(a-1)n+1}\, p_a^{n} $$

where n is the number of internal nodes in a tree and p a is a constant. This result generalises the result previously reported for the case a = 1.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Blickle, T., Thiele, L.: A mathematical analysis of tournament selection. In: Eshelman, L.J. (ed.) Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA’95), pp. 9–16. Morgan Kaufmann Publishers, San Francisco (1995)

    Google Scholar 

  2. Blickle, T., Thiele, L.: A comparison of selection schemes used in evolutionary algorithms. Evolutionary Computation 4(4), 361–394 (1997)

    Article  Google Scholar 

  3. Consul, P.C., Shenton, L.R.: Use of Lagrange Expansion for Generating Discrete Generalized Probability Distributions. SIAM Journal on Applied Mathematics 23(2), 239–248 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  4. Geiringer, H.: On the probability theory of linkage in Mendelian heredity. Annals of Mathematical Statistics 15(1), 25–57 (1944)

    Article  MathSciNet  MATH  Google Scholar 

  5. Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins, G.J.E. (ed.) Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, San Francisco (1991)

    Google Scholar 

  6. Good, I.J.: The Lagrange Distributions and Branching Processes. SIAM Journal on Applied Mathematics 28(2), 270–275 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hilton, P., Pederson, J.: Catalan numbers, their generalization, and their uses. Mathematical Intelligencer 13, 64–75 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  8. Janardan, K.: Weighted Lagrange Distributions and Their Characterizations. SIAM Journal on Applied Mathematics 47(2), 411–415 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  9. Janardan, K., Rao, B.: Lagrange Distributions of the Second Kind and Weighted Distributions. SIAM Journal on Applied Mathematics 43(2), 302–313 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  10. Luke, S.: Two fast tree-creation algorithms for genetic programming. IEEE Transactions on Evolutionary Computation 4(3), 274–283 (2000)

    Article  Google Scholar 

  11. Motoki, T.: Calculating the expected loss of diversity of selection schemes. Evolutionary Computation 10(4), 397–422 (2002)

    Article  Google Scholar 

  12. Poli, R., McPhee, N.F.: Exact schema theorems for GP with one-point and standard crossover operating on linear structures and their application to the study of the evolution of size. In: Miller, J., Tomassini, M., Lanzi, P.L., Ryan, C., Tetamanzi, A.G.B., Langdon, W.B. (eds.) EuroGP 2001. LNCS, vol. 2038, pp. 126–142. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  13. Poli, R., McPhee, N.F.: General schema theory for genetic programming with subtree-swapping crossover: Part I. Evolutionary Computation 11(1), 53–66 (2003)

    Article  Google Scholar 

  14. Poli, R., McPhee, N.F.: General schema theory for genetic programming with subtree-swapping crossover: Part II. Evolutionary Computation 11(2), 169–206 (2003)

    Article  Google Scholar 

  15. Rowe, J.E., McPhee, N.F.: The effects of crossover and mutation operators on variable length linear structures. Technical Report CSRP-01-7, University of Birmingham, School of Computer Science (January 2001)

    Google Scholar 

  16. Vose, M.D.: The simple genetic algorithm: Foundations and theory. MIT Press, Cambridge (1999)

    MATH  Google Scholar 

  17. Watson, H.W., Galton, F.: On the Probability of the Extinction of Families. The Journal of the Anthropological Institute of Great Britain and Ireland 4, 138–144 (1875)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Essex, UK

    Riccardo Poli, William B. Langdon & Stephen Dignum

Authors
  1. Riccardo Poli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. William B. Langdon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stephen Dignum
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Marc Ebner Michael O’Neill Anikó Ekárt Leonardo Vanneschi Anna Isabel Esparcia-Alcázar

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer Berlin Heidelberg

About this paper

Cite this paper

Poli, R., Langdon, W.B., Dignum, S. (2007). On the Limiting Distribution of Program Sizes in Tree-Based Genetic Programming. In: Ebner, M., O’Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds) Genetic Programming. EuroGP 2007. Lecture Notes in Computer Science, vol 4445. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71605-1_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-71605-1_18

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-71602-0

  • Online ISBN: 978-3-540-71605-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics