research-article

Reassembling operator equalisation: a secret revealed

Author:

Sara SilvaAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 1395 - 1402

https://doi.org/10.1145/2001576.2001764

Published: 12 July 2011 Publication History

Abstract

The recent Crossover Bias theory has shown that bloat in Genetic Programming can be caused by the proliferation of small unfit individuals in the population. Inspired by this theory, Operator Equalisation is the most recent and successful bloat control method available. In this work we revisit two bloat control methods, the old Brood Recombination and the newer Dynamic Limits, hypothesizing that together they contain the two main ingredients that make Operator Equalisation so successful. We reassemble Operator Equalisation by joining these two ingredients in a hybrid method, and test it in a hard real world regression problem. The results are surprising. Operator Equalisation and the hybrid variants exhibit completely different behaviors, and an unexpected feature of Operator Equalisation is revealed, one that may be the true responsible for its success: a nearly flat length distribution target. We support this finding with additional results, and discuss its implications.

References

[1]

L. Altenberg. The evolution of evolvability in genetic programming. In K. E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 3, pages 47--74. MIT Press, 1994.

Digital Library

[2]

F. Archetti, S. Lanzeni, E. Messina, and L. Vanneschi. Genetic programming for human oral bioavailability of drugs. In M. Keijzer, et al., editors, GECCO 2006: Proceedings of the 8th annual conference on Genetic and evolutionary computation, volume 1, pages 255--262, Seattle, Washington, USA, 8--12 July 2006. ACM Press.

Digital Library

[3]

F. Archetti, S. Lanzeni, E. Messina, and L. Vanneschi. Genetic programming for computational pharmacokinetics in drug discovery and development. Genetic Programming and Evolvable Machines, 8(4):413--432, Dec. 2007. special issue on medical applications of Genetic and Evolutionary Computation.

Digital Library

[4]

M. Brameier and W. Banzhaf. Neutral variations cause bloat in linear GP. In C. Ryan, et al., editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 286--296, Essex, 14--16 Apr. 2003. Springer-Verlag.

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]

S. Dignum and R. Poli. Crossover, sampling, bloat and the harmful effects of size limits. In M. O'Neill, et al., editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 158--169, Naples, 26--28 Mar. 2008. Springer.

Digital Library

[7]

S. Dignum and R. Poli. Operator equalisation and bloat free GP. In M. O'Neill, et al., editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 110--121, Naples, 26--28 Mar. 2008. Springer.

Digital Library

[8]

S. Gelly, O. Teytaud, N. Bredeche, and M. Schoenauer. Universal consistency and bloat in GP. Revue d'Intelligence Artificielle, 20(6):805--827, 2006. Issue on New Methods in Machine Learning. Theory and Applications.

[9]

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

Digital Library

[10]

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

[11]

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.

Digital Library

[12]

R. Poli, N. F. McPhee, and L. Vanneschi. Analysis of the effects of elitism on bloat in linear and tree-based genetic programming. In R. L. Riolo, et al., editors, Genetic Programming Theory and Practice VI, Genetic and Evolutionary Computation, chapter 7, pages 91--111. Springer, Ann Arbor, 15--17May 2008.

[13]

R. Poli, N. F. McPhee, and L. Vanneschi. Elitism reduces bloat in genetic programming. In M. Keijzer, et al., editors, GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1343--1344, Atlanta, GA, USA, 12--16 July 2008. ACM.

Digital Library

[14]

R. Poli, N. F. McPhee, and L. Vanneschi. The impact of population size on code growth in GP: analysis and empirical validation. In M. Keijzer, et al., editors, GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1275--1282, Atlanta, GA, USA, 12--16 July 2008. ACM.

Digital Library

[15]

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.

Digital Library

[16]

S. Silva and E. Costa. Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories. Genetic Programming and Evolvable Machines, 10(2):141--179, 2009.

Digital Library

[17]

S. Silva and S. Dignum. Extending operator equalisation: Fitness based self adaptive length distribution for bloat free GP. In L. Vanneschi, et al., editors, Proceedings of the 12th European Conference on Genetic Programming, EuroGP 2009, volume 5481 of LNCS, pages 159--170, Tuebingen, Apr. 15--17 2009. Springer.

Digital Library

[18]

S. Silva and L. Vanneschi. Operator equalisation, bloat and overfitting: a study on human oral bioavailability prediction. In G. Raidl, et al., editors, GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1115--1122, Montreal, 8--12 July 2009. ACM.

Digital Library

[19]

S. Silva and L. Vanneschi. Bloat free genetic programming: Application to human oral bioavailability prediction. International Journal of Data Mining and Bioinformatics, to appear.

Digital Library

[20]

S. Silva, M. Vasconcelos, and J. Melo. Bloat free genetic programming versus classification trees for identification of burned areas in satellite imagery. In C. Di Chio, et al., editors, Applications of Evolutionary Computation: EvoApplications 2010: Evolutionary Computation in Image Analysis and Signal Processing (EvoIASP), volume 6024 of LNCS, Istanbul, 7--9 Apr. 2010. Springer.

Digital Library

[21]

W. A. Tackett. Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA, 1994.

Digital Library

[22]

L. Vanneschi and S. Silva. Using operator equalisation for prediction of drug toxicity with genetic programming. In L. S. Lopes, et al., editors, Progress in Artificial Intelligence, 14th Portuguese Conference on Artificial Intelligence, EPIA 2009, volume 5816 of LNAI, pages 65--76, Aveiro, Portugal, Oct. 12--15 2009. Springer.

Digital Library

Cited By

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
Juárez-Smith PTrujillo LGarcía-Valdez MFernández de Vega FChávez F(2019)Pool-Based Genetic Programming Using Evospace, Local Search and Bloat ControlMathematical and Computational Applications10.3390/mca2403007824:3(78)Online publication date: 29-Aug-2019
https://doi.org/10.3390/mca24030078
Juárez-Smith PTrujillo LGarcía-Valdez MFernández de Vega FChávez F(2019)Local search in speciation-based bloat control for genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-019-09351-720:3(351-384)Online publication date: 23-Mar-2019
https://doi.org/10.1007/s10710-019-09351-7
Show More Cited By

Reassembling operator equalisation: a secret revealed
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 ...
Operator equalisation, bloat and overfitting: a study on human oral bioavailability prediction
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Operator equalisation was recently proposed as a new bloat control technique for genetic programming. By controlling the distribution of program lengths inside the population, it can bias the search towards smaller or larger programs. In this paper we ...
Operator equalisation and bloat free GP
EuroGP'08: Proceedings of the 11th European conference on Genetic programming

Research has shown that beyond a certain minimum program length the distributions of program functionality and fitness converge to a limit. Before that limit, however, there may be program-length classes with a higher or lower average fitness than that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
100
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Juárez-Smith PTrujillo LGarcía-Valdez MFernández de Vega FChávez F(2019)Pool-Based Genetic Programming Using Evospace, Local Search and Bloat ControlMathematical and Computational Applications10.3390/mca2403007824:3(78)Online publication date: 29-Aug-2019
https://doi.org/10.3390/mca24030078
Juárez-Smith PTrujillo LGarcía-Valdez MFernández de Vega FChávez F(2019)Local search in speciation-based bloat control for genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-019-09351-720:3(351-384)Online publication date: 23-Mar-2019
https://doi.org/10.1007/s10710-019-09351-7
Trujillo LZ-Flores EJuárez-Smith PLegrand PSilva SCastelli MVanneschi LSchütze OMuñoz L(2018)Local Search is Underused in Genetic ProgrammingGenetic Programming Theory and Practice XIV10.1007/978-3-319-97088-2_8(119-137)Online publication date: 25-Oct-2018
https://doi.org/10.1007/978-3-319-97088-2_8
Juárez-Smith PTrujillo LNeumann FSutton A(2016)Integrating Local Search within neat-GPProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931659(993-996)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2931659
Trujillo LMuñoz LGalván-López ESilva S(2016)neat Genetic ProgrammingInformation Sciences: an International Journal10.1016/j.ins.2015.11.010333:C(21-43)Online publication date: 10-Mar-2016
https://dl.acm.org/doi/10.1016/j.ins.2015.11.010
Silva SMuñoz LTrujillo LIngalalli VCastelli MVanneschi L(2016)Multiclass Classification Through Multidimensional ClusteringGenetic Programming Theory and Practice XIII10.1007/978-3-319-34223-8_13(219-239)Online publication date: 22-Dec-2016
https://doi.org/10.1007/978-3-319-34223-8_13
Gardner MGagné CParizeau M(2015)Controlling code growth by dynamically shaping the genotype size distributionGenetic Programming and Evolvable Machines10.1007/s10710-015-9242-816:4(455-498)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s10710-015-9242-8
Trujillo LMuñoz LNaredo EMartínez Y(2014)NEAT, There's No BloatRevised Selected Papers of the 17th European Conference on Genetic Programming - Volume 859910.1007/978-3-662-44303-3_15(174-185)Online publication date: 23-Apr-2014
https://dl.acm.org/doi/10.1007/978-3-662-44303-3_15
Krawiec KPawlak T(2013)Locally geometric semantic crossoverGenetic Programming and Evolvable Machines10.1007/s10710-012-9172-714:1(31-63)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1007/s10710-012-9172-7
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.

Media

Figures

Other

Tables

View Table of Contents