research-article

Parsimony pressure made easy

Authors:

Nicholas Freitag McPheeAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1267 - 1274

https://doi.org/10.1145/1389095.1389340

Published: 12 July 2008 Publication History

Abstract

The parsimony pressure method is perhaps the simplest and most frequently used method to control bloat in genetic programming. In this paper we first reconsider the size evolution equation for genetic programming developed in [26] and rewrite it in a form that shows its direct relationship to Price's theorem. We then use this new formulation to derive theoretical results that show how to practically and optimally set the parsimony coefficient dynamically during a run so as to achieve complete control over the growth of the programs in a population. Experimental results confirm the effectiveness of the method, as we are able to tightly control the average program size under a variety of conditions. These include such unusual cases as dynamically varying target sizes such that the mean program size is allowed to grow during some phases of a run, while being forced to shrink in others.

References

[1]

L. Altenberg. The Schema Theorem and Price's Theorem. In L. D. Whitley and M. D. Vose, editors, Foundations of Genetic Algorithms 3, Estes Park, Colorado, USA, 31 July-2 Aug. 1994. Morgan Kaufmann. Published 1995.

[2]

P. J. Angeline. An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover. In J. R. Koza, et al., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 21--29, Stanford University, CA, USA, 28-31 July 1996. MIT Press.

Digital Library

[3]

W. Banzhaf and W. B. Langdon. Some considerations on the reason for bloat. Genetic Programming and Evolvable Machines, 3(1):81--91, Mar. 2002.

Digital Library

[4]

R. Crawford-Marks and L. Spector. Size control via size fair genetic operators in the PushGP genetic programming system. In W. B. Langdon, et al., editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 733--739, New York, 9-13 July 2002. Morgan Kaufmann Publishers.

Digital Library

[5]

S. Dignum and R. Poli. Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1588--1595, London, 7-11 July 2007. ACM Press.

Digital Library

[6]

A. Ekart and S. Z. Nemeth. Selection based on the pareto nondomination criterion for controlling code growth in genetic programming. Genetic Programming and Evolvable Machines, 2(1):61--73, Mar. 2001.

Digital Library

[7]

H. Iba. Complexity-based fitness evaluation for variable length representation. Position paper at the Workshop on Evolutionary Computation with Variable Size Representation at ICGA-97, 20 July 1997.

[8]

H. Iba, H. de Garis, and T. Sato. Genetic programming using a minimum description length principle. In K. E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 12, pages 265--284. MIT Press, 1994.

Digital Library

[9]

H. Iba, H. de Garis, and T. Sato. Temporal data processing using genetic programming. In L. Eshelman, editor, Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), pages 279--286, Pittsburgh, PA, USA, 15-19 July 1995. Morgan Kaufmann.

Digital Library

[10]

K. E. Kinnear, Jr. Evolving a sort: Lessons in genetic programming. In Proceedings of the 1993 International Conference on Neural Networks, volume 2, pages 881--888, San Francisco, USA, 28 Mar.-1 Apr. 1993. IEEE Press.

[11]

K. E. Kinnear, Jr. Fitness landscapes and difficulty in genetic programming. In Proceedings of the 1994 IEEE World Conference on Computational Intelligence, volume 1, pages 142--147, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.

[12]

M. Kotanchek, G. Smits, and E. Vladislavleva. Pursuing the pareto paradigm tournaments, algorithm variations & ordinal optimization. In R. L. Riolo, et al., editors, Genetic Programming Theory and Practice IV, volume 5 of Genetic and Evolutionary Computation, chapter 3. Springer, Ann Arbor, 11-13 May 2006.

[13]

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

Digital Library

[14]

W. B. Langdon. The evolution of size in variable length representations. In 1998 IEEE International Conference on Evolutionary Computation, pages 633--638, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.

[15]

W. B. Langdon. Size fair and homologous tree genetic programming crossovers. Genetic Programming and Evolvable Machines, 1(1/2):95--119, Apr. 2000.

Digital Library

[16]

W. B. Langdon and R. Poli. Fitness causes bloat. In P. K. Chawdhry, et al., editors, Soft Computing in Engineering Design and Manufacturing, pages 13--22. Springer-Verlag London, 23-27 June 1997.

[17]

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

Digital Library

[18]

W. B. Langdon, T. Soule, R. Poli, and J. A. Foster. The evolution of size and shape. In L. Spector, et al., editors, Advances in Genetic Programming 3, chapter 8, pages 163--190. MIT Press, Cambridge, MA, USA, June 1999.

Digital Library

[19]

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

Digital Library

[20]

N. F. McPhee and J. D. Miller. Accurate replication in genetic programming. In L. Eshelman, editor, Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), pages 303--309, Pittsburgh, PA, USA, 15-19 July 1995. Morgan Kaufmann.

Digital Library

[21]

N. F. McPhee and R. Poli. Using schema theory to explore interactions of multiple operators. In W. B. Langdon, et al., editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 853--860, New York, 9-13 July 2002. Morgan Kaufmann Publishers.

Digital Library

[22]

R. Poli. General schema theory for genetic programming with subtree-swapping crossover. In Genetic Programming, Proceedings of EuroGP 2001, LNCS, Milan, 18--20 Apr. 2001. Springer-Verlag.

Digital Library

[23]

R. Poli. A simple but theoretically-motivated method to control bloat in genetic programming. In C. Ryan, et al., editors, Genetic Programming, Proceedings of the 6th European Conference, EuroGP 2003, LNCS, pages 211--223, Essex, UK, 14-16 Apr. 2003. Springer-Verlag.

Digital Library

[24]

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 LNCS, pages 193--204, Valencia, Spain, 11 - 13 Apr. 2007. Springer.

Digital Library

[25]

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).

Digital Library

[26]

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

Digital Library

[27]

G. R. Price. Selection and covariance. Nature, 227, August 1:520--521, 1970.

[28]

J. Rosca. Generality versus size in genetic programming. In J. R. Koza, et al., editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 381--387, Stanford University, CA, USA, 28-31 July 1996. MIT Press.

Digital Library

[29]

J. Rosca. A probabilistic model of size drift. In R. L. Riolo and B. Worzel, editors, Genetic Programming Theory and Practice, chapter 8, pages 119--136. Kluwer, 2003.

[30]

J. P. Rosca. Analysis of complexity drift in genetic programming. In J. R. Koza, et al., editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 286--294, Stanford University, CA, USA, 13-16 July 1997. Morgan Kaufmann.

[31]

J. P. Rosca and D. H. Ballard. Complexity drift in evolutionary computation with tree representations. Technical Report NRL5, University of Rochester, Computer Science Department, Rochester, NY, USA, Dec. 1996.

[32]

J. P. Rosca and D. H. Ballard. Rooted-tree schemata in genetic programming. In L. Spector, et al., editors, Advances in Genetic Programming 3, chapter 11, pages 243--271. MIT Press, Cambridge, MA, USA, June 1999.

Digital Library

[33]

T. Soule and J. A. Foster. Effects of code growth and parsimony pressure on populations in genetic programming. Evolutionary Computation, 6(4):293--309, Winter 1998.

Digital Library

[34]

T. Soule and J. A. Foster. Removal bias: a new cause of code growth in tree based evolutionary programming. In 1998 IEEE International Conference on Evolutionary Computation, pages 781--186, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.

[35]

B.-T. Zhang and H. Muhlenbein. Balancing accuracy and parsimony in genetic programming. Evolutionary Computation, 3(1):17--38, 1995.

Digital Library

Cited By

Chang FHuang H(2025)Exploring Genetic Programming in Image Processing: Challenges and Enhanced Techniques2025 19th International Conference on Ubiquitous Information Management and Communication (IMCOM)10.1109/IMCOM64595.2025.10857586(1-4)Online publication date: 3-Jan-2025
https://doi.org/10.1109/IMCOM64595.2025.10857586
Zhang TZhang T(2025)Symbolic RegressionAn Introduction to Materials Informatics10.1007/978-981-99-7992-9_8(229-244)Online publication date: 27-Feb-2025
https://doi.org/10.1007/978-981-99-7992-9_8
Zhang HChen QXue BBanzhaf WZhang M(2024)Modular Multitree Genetic Programming for Evolutionary Feature Construction for RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331863828:5(1455-1469)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3318638
Show More Cited By

Recommendations

Bloat-aware GP-based methods with bloat quantification
Abstract
Genetic programming (GP) solves optimization problems by simulating the evolution procedure in nature. It has a serious problem termed as bloat, which can cost memory, hamper effective breeding and slow down the evolution process. However, there ...
Performance improvement in genetic programming using modified crossover and node mutation
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

During the evolution of solutions using Genetic Programming (GP) there is generally an increase in average tree size without a corresponding increase in fitness'a phenomenon commonly referred to as bloat. Bloating increases time to find the best ...
On the cumulative effect of bloat and genetic transposition on the efficiency of incremental evolution of snake-like robot
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We present a study on the cumulative effect of the bloat and the seeding of the initial population, inspired by genetic transposition (GT), on the efficiency of incremental evolution of simulated snake-like robot (Snakebot). In the proposed incremental ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chang FHuang H(2025)Exploring Genetic Programming in Image Processing: Challenges and Enhanced Techniques2025 19th International Conference on Ubiquitous Information Management and Communication (IMCOM)10.1109/IMCOM64595.2025.10857586(1-4)Online publication date: 3-Jan-2025
https://doi.org/10.1109/IMCOM64595.2025.10857586
Zhang TZhang T(2025)Symbolic RegressionAn Introduction to Materials Informatics10.1007/978-981-99-7992-9_8(229-244)Online publication date: 27-Feb-2025
https://doi.org/10.1007/978-981-99-7992-9_8
Zhang HChen QXue BBanzhaf WZhang M(2024)Modular Multitree Genetic Programming for Evolutionary Feature Construction for RegressionIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331863828:5(1455-1469)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3318638
Bermejo ECordón OIrurita JAlemán ISalvador Á(2024)Age-at-Death Estimation based on Symbolic Regression Ensemble Learning from Multiple Annotations2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10611921(01-08)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10611921
Anđelić N(2024)Improvement of pulsars detection using dataset balancing methods and symbolic classification ensembleAstronomy and Computing10.1016/j.ascom.2024.10080147(100801)Online publication date: Apr-2024
https://doi.org/10.1016/j.ascom.2024.100801
Kosar TKovačević ŽMernik MSlivnik B(2023)The Impact of Code Bloat on Genetic Program Comprehension: Replication of a Controlled Experiment on Semantic InferenceMathematics10.3390/math1117374411:17(3744)Online publication date: 31-Aug-2023
https://doi.org/10.3390/math11173744
de França F(2023)Alleviating overfitting in transformation-interaction-rational symbolic regression with multi-objective optimizationGenetic Programming and Evolvable Machines10.1007/s10710-023-09461-324:2Online publication date: 20-Oct-2023
https://doi.org/10.1007/s10710-023-09461-3
Slivnik BKovačević ŽMernik MKosar T(2022)On Comprehension of Genetic Programming Solutions: A Controlled Experiment on Semantic InferenceMathematics10.3390/math1018338610:18(3386)Online publication date: 18-Sep-2022
https://doi.org/10.3390/math10183386
Anđelić NBaressi Šegota SLorencin IPoljak IMrzljak VCar Z(2021)Use of Genetic Programming for the Estimation of CODLAG Propulsion System ParametersJournal of Marine Science and Engineering10.3390/jmse90606129:6(612)Online publication date: 2-Jun-2021
https://doi.org/10.3390/jmse9060612
Laibinis LIliasov ARomanovsky A(2021)Mutation Testing for Rule-Based Verification of Railway Signaling DataIEEE Transactions on Reliability10.1109/TR.2020.304746270:2(676-691)Online publication date: Jun-2021
https://doi.org/10.1109/TR.2020.3047462
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten