Article

Exploiting disruption aversion to control code bloat

Authors:

Robert B. Heckendorn,

Terry SouleAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1605 - 1612

https://doi.org/10.1145/1068009.1068281

Published: 25 June 2005 Publication History

Abstract

The authors employ multiple crossovers as a novel natural extension to crossovers as a mixing operator. They use this as a framework to explore the ideas of code growth. Empirical support is given for popular theories for mechanisms of code growth. Three specific algorithms for multiple crossovers are compared with classic methods for performance in terms of fitness and genome size. The details of the performance of these algorithms is examined in detail for both practical value and theoretical implications. The authors conclude that multiple crossovers is a practical scheme for containing code growth without a significant loss of fitness.

References

[1]

T. Blickle and L. Thiele. Genetic programming and redundancy. In J. Hopf, editor, Genetic Algorithms within the Framework of Evolutionary Computation, pages 33 --38. Saarbrucken, Germany: Max-Planck-Institut fur Informatik, 1994.

[2]

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

Digital Library

[3]

W. B. Langdon. Fitness causes bloat: Simulated annealing, hill climbing and populations. Technical Report CSRP-97-22, The University of Birmingham, Birmingham, UK, 1997.

[4]

W. B. Langdon and R. Poli. Foundations of Genetic Programming. Springer-Verlag, Berlin, Germany, 1998.

Digital Library

[5]

W. B. Langdon, T. Soule, R. Poli, and J. A. Foster. The evolution of size and shape. In L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. J. Angeline, editors, Advances in Genetic Programming III, pages 163--190. Cambridge, MA: The MIT Press, 1999.

Digital Library

[6]

S. Luke. Code growth is not caused by introns. In Late Breaking Papers, Proceedings of the Genetic and Evolutionary Computation Conference 2000, pages 228--235, 2000.

[7]

N. F. McPhee and J. D. Miller. Accurate replication in genetic programming. In L. J. Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 303--309. San Francisco, CA: Morgan Kaufmann, 1995.

Digital Library

[8]

P. Nordin. Evolutionary Program Induction of Binary Machine Code and its Application. Muenster: Krehl Verlag, 1997.

[9]

P. Nordin and W. Banzhaf. Complexity compression and evolution. In L. J. Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 310--317. San Francisco, CA: Morgan Kaufmann, 1995.

Digital Library

[10]

P. Nordin, W. Banzhaf, and F. D. Francone. Introns in nature and in simulated structure evolution. In D. Lundh, B. Olsson, and A. Narayanan, editors, Proceedings Bio-Computing and Emergent Computation, pages 22--35. Springer, 1997.

Digital Library

[11]

P. Nordin, F. Francone, and W. Banzhaf. Explicitly defined introns and destructive crossover in genetic programming. In P. Angeline and J. Kenneth E. Kinnear, editors, Advances in Genetic Programming II, pages 111 -- 134. Cambridge, MA: The MIT Press, 1996.

Digital Library

[12]

T. Soule. Code Growth in Genetic Programming. PhD thesis, University of Idaho, University of Idaho, 1998.

Digital Library

[13]

T. Soule. Exons and code growth in genetic programming. In J. A. Foster, E. Lutton, J. F. Miller, C. Ryan, and A. Tettamanzi, editors, Genetic Programming, 5th European Conference, EuroGP 2002, pages 142--151, 2002.

Digital Library

[14]

T. Soule. Operator choice and the evolution of robust solutions. In R. Riolo and B. Worzel, editors, Genetic Programming Theory and Practice, pages 257--270, 2003.

[15]

T. Soule and J. A. Foster. Removal bias: a new cause of code growth in tree based evolutionary programming. In ICEC 98: IEEE International Conference on Evolutionary Computation 1998, pages 781--786. IEEE Press, 1998.

[16]

T. Soule, J. A. Foster, and J. Dickinson. Code growth in genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. R. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 215--223. Cambridge, MA: MIT Press, 1996.

Digital Library

[17]

T. Soule and R. Heckendorn. An analysis of the causes of code growth in genetic programmin. Genetic Programming and Evolvable Machines, 3:283--309, 2002.

Digital Library

[18]

T. Soule, R. Heckendorn, and J. Shen. Solution stability in evolutonary computation. In I. Cicekli, N. K. Cicekli, and E. Gelenbe, editors, Proceedings of the 17th International Symposium on Computer and Information Systems, pages 237--241, 2002.

[19]

M. J. Streeter. The root causes of code growth in genetic programming. In C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, and E. Costa, editors, Genetic Programming, 6th European Conference, EuroGP 2003, pages 443--454, 2002.

Digital Library

Cited By

Silva SDignum SVanneschi L(2012)Operator equalisation for bloat free genetic programming and a survey of bloat control methodsGenetic Programming and Evolvable Machines10.1007/s10710-011-9150-513:2(197-238)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9150-5
Costa EPozo AVergilio S(2010)A Genetic Programming Approach for Software Reliability ModelingIEEE Transactions on Reliability10.1109/TR.2010.204075959:1(222-230)Online publication date: Mar-2010
https://doi.org/10.1109/TR.2010.2040759
Jackson D(2010)The identification and exploitation of dormancy in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-009-9086-111:1(89-121)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1007/s10710-009-9086-1
Show More Cited By

Recommendations

Semantics Based Substituting Technique for Reducing Code Bloat in Genetic Programming
SoICT '18: Proceedings of the 9th International Symposium on Information and Communication Technology

Genetic Programming (GP) is a technique that allows computer programs encoded as a set of tree structures to be evolved using an evolutionary algorithm. In GP, code bloat is a common phenomenon characterized by the size of individuals gradually ...
An Analysis of the Causes of Code Growth in Genetic Programming

This research examines the cause of code growth (bloat) in genetic programming (GP). Currently there are three hypothesized causes of code growth in GP: protection, drift, and removal bias. We show that single node mutations increase code growth in ...
A statistical learning theory approach of bloat
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Code bloat, the excessive increase of code size, is an important issue in Genetic Programming (GP). This paper proposes a theoretical analysis of code bloat in the framework of symbolic regression in GP, from the viewpoint of Statistical Learning Theory,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

Copyright © 2005 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: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
193
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Silva SDignum SVanneschi L(2012)Operator equalisation for bloat free genetic programming and a survey of bloat control methodsGenetic Programming and Evolvable Machines10.1007/s10710-011-9150-513:2(197-238)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9150-5
Costa EPozo AVergilio S(2010)A Genetic Programming Approach for Software Reliability ModelingIEEE Transactions on Reliability10.1109/TR.2010.204075959:1(222-230)Online publication date: Mar-2010
https://doi.org/10.1109/TR.2010.2040759
Jackson D(2010)The identification and exploitation of dormancy in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-009-9086-111:1(89-121)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1007/s10710-009-9086-1
Badran KRockett P(2010)The influence of mutation on population dynamics in multiobjective genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-009-9084-311:1(5-33)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1007/s10710-009-9084-3
Silva SCosta E(2009)Dynamic limits for bloat control in genetic programming and a review of past and current bloat theoriesGenetic Programming and Evolvable Machines10.1007/s10710-008-9075-910:2(141-179)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1007/s10710-008-9075-9
Kouchakpour PZaknich ABräunl T(2008)A survey and taxonomy of performance improvement of canonical genetic programmingKnowledge and Information Systems10.1007/s10115-008-0184-921:1(1-39)Online publication date: 12-Dec-2008
https://doi.org/10.1007/s10115-008-0184-9
Collet P(2007)Genetic ProgrammingHandbook of Research on Nature-Inspired Computing for Economics and Management10.4018/978-1-59140-984-7.ch005(59-73)Online publication date: 2007
https://doi.org/10.4018/978-1-59140-984-7.ch005
Costa EPozo A(2006)A (\mu + \lambda) - GP Algorithm and its use for Regression ProblemsProceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence10.1109/ICTAI.2006.6(10-17)Online publication date: 13-Nov-2006
https://dl.acm.org/doi/10.1109/ICTAI.2006.6

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