Article

Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat

Authors:

Stephen Dignum,

Riccardo PoliAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1588 - 1595

https://doi.org/10.1145/1276958.1277277

Published: 07 July 2007 Publication History

Get Access

Abstract

Recent research [1] has found that standard sub-tree crossover with uniform selection of crossover points, in the absence of fitness pressure, pushes a population of GP trees towards a Lagrange distribution of tree sizes. However, the result applied to the case of single arity function plus leaf node combinations, e.g., unary, binary, ternary, etc trees only. In this paper we extend those findings and show that the same distribution is also applicable to the more general case where the function set includes functions of mixed arities. We also provide empirical evidence that strongly corroborates this generalisation. Both predicted and observed results show a distinct bias towards the sampling of shorter programs irrespective of the mix of function arities used. Practical applications and implications of this knowledge are investigated with regard to search efficiency and program bloat. Work is also presented regarding the applicability of the theory to the traditional 90%-function 10%-terminal crossover node selection policy.

References

[1]

Riccardo Poli, William B. Langdon, and Stephen Dignum. On the limiting distribution of program sizes in tree-based genetic programming. In Proceedings of the 10th European Conference on Genetic Programming, Lecture Notes in Computer Science, Valencia, Spain, 11--13 April 2007. Forthcoming.

Digital Library

Google Scholar

[2]

Riccardo Poli and Nicholas Freitag McPhee. 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 Julian F. Miller, Marco Tomassini, Pier Luca Lanzi, Conor Ryan, Andrea G. B. Tettamanzi, and William B. Langdon, editors, Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 126--142, Lake Como, Italy, 18--20 April 2001. Springer-Verlag.

Digital Library

Google Scholar

[3]

Riccardo Poli and Nicholas Freitag McPhee. General schema theory for genetic programming with subtree-swapping crossover: Part II. Evolutionary Computation, 11(2):169--206, June 2003.

Digital Library

Google Scholar

[4]

Riccardo Poli and Nicholas Freitag McPhee. General schema theory for genetic programming with subtree-swapping crossover: Part I. Evolutionary Computation, 11(1):53--66, March 2003.

Digital Library

Google Scholar

[5]

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

Digital Library

Google Scholar

[6]

Saeed Ghahramani. Fundamentals of Probability. Prentice-Hall Inc, Upper Saddle River, NJ 07458, 1996.

Google Scholar

[7]

John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

Google Scholar

[8]

W. B. Langdon and Riccardo Poli. Foundations of Genetic Programming. Springer-Verlag, 2002.

Digital Library

Google Scholar

[9]

Sean Luke. ECJ 13: A Java evolutionary computation library. http://cs.gmu.edu/~eclab/projects/ecj/, 2005.

Google Scholar

[10]

Riccardo Poli. A simple but theoretically-motivated method to control bloat in genetic programming. In Conor Ryan, Terence Soule, Maarten Keijzer, Edward Tsang, Riccardo Poli, and Ernesto Costa, editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 204--217, Essex, 14--16 April 2003. Springer-Verlag.

Digital Library

Google Scholar

Cited By

View all

Banzhaf WBakurov ILi XHandl J(2024)On the Nature of the Phenotype in Tree Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654129(868-877)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654129
Zhang HChen QXue BBanzhaf WZhang M(2024)A Semantic-Based Hoist Mutation Operator for Evolutionary Feature Construction in RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.333123428:6(1689-1703)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3331234
Morales GSheppard J(2024)Univariate Skeleton Prediction in Multivariate Systems Using TransformersMachine Learning and Knowledge Discovery in Databases. Research Track and Demo Track10.1007/978-3-031-70371-3_7(107-125)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70371-3_7
Show More Cited By

Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Operator equalisation for bloat free genetic programming and a survey of bloat control methods

Bloat can be defined as an excess of code growth without a corresponding improvement in fitness. This problem has been one of the most intensively studied subjects since the beginnings of Genetic Programming. This paper begins by briefly reviewing the ...
Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control
Special issue on advances in computational intelligence and bioinformatics

Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, because GP uses a variable length representation, the ...
Impact of Crossover Bias in Genetic Programming
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

In tree-based genetic programming (GP) with sub-tree crossover, the parent contributing the root portion of the tree (the root parent) often contributes more to the semantics of the resulting child than the non-root parent. Previous research ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

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: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
225
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Banzhaf WBakurov ILi XHandl J(2024)On the Nature of the Phenotype in Tree Genetic ProgrammingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654129(868-877)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654129
Zhang HChen QXue BBanzhaf WZhang M(2024)A Semantic-Based Hoist Mutation Operator for Evolutionary Feature Construction in RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.333123428:6(1689-1703)Online publication date: Dec-2024
https://doi.org/10.1109/TEVC.2023.3331234
Morales GSheppard J(2024)Univariate Skeleton Prediction in Multivariate Systems Using TransformersMachine Learning and Knowledge Discovery in Databases. Research Track and Demo Track10.1007/978-3-031-70371-3_7(107-125)Online publication date: 22-Aug-2024
https://doi.org/10.1007/978-3-031-70371-3_7
Zhang HChen QXue BBanzhaf WZhang MSilva SPaquete L(2023)A Double Lexicase Selection Operator for Bloat Control in Evolutionary Feature Construction for RegressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590365(1194-1202)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590365
Mei YChen QLensen AXue BZhang M(2023)Explainable Artificial Intelligence by Genetic Programming: A SurveyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322550927:3(621-641)Online publication date: Jun-2023
https://doi.org/10.1109/TEVC.2022.3225509
O'Neill MBrabazon A(2021)An Exploration of Asocial and Social Learning in the Evolution of Variable-length Structures2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504900(2307-2314)Online publication date: 28-Jun-2021
https://doi.org/10.1109/CEC45853.2021.9504900
Fernandez de Vega FOlague GLanza DChavez de la O FBanzhaf WGoodman EMenendez-Clavijo JMartinez A(2020)Time and Individual Duration in Genetic ProgrammingIEEE Access10.1109/ACCESS.2020.29757538(38692-38713)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2975753
Nicolau MMcDermott J(2020)Genetic Programming Symbolic Regression: What Is the Prior on the Prediction?Genetic Programming Theory and Practice XVII10.1007/978-3-030-39958-0_11(201-225)Online publication date: 8-May-2020
https://doi.org/10.1007/978-3-030-39958-0_11
O'Neill MBrabazon A(2019)Mutational Robustness and Structural Complexity in Grammatical Evolution2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790010(1338-1344)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790010
Sotto LMelo V(2016)Studying bloat control and maintenance of effective code in linear genetic programming for symbolic regressionNeurocomputing10.1016/j.neucom.2015.10.109180:C(79-93)Online publication date: 5-Mar-2016
https://dl.acm.org/doi/10.1016/j.neucom.2015.10.109
Show More Cited By

View Options

Login options

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

Cited By

Recommendations

Operator equalisation for bloat free genetic programming and a survey of bloat control methods

Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control

Impact of Crossover Bias in Genetic Programming