research-article

Mutation as a diversity enhancing mechanism in genetic programming

Author:

David JacksonAuthors Info & Claims

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

Pages 1371 - 1378

https://doi.org/10.1145/2001576.2001761

Published: 12 July 2011 Publication History

Abstract

In various evolutionary computing algorithms, mutation operators are employed as a means of preserving diversity of populations. In genetic programming (GP), by contrast, mutation tends to be viewed as offering little benefit, to the extent that it is often not implemented in GP systems. We investigate the role of mutation in GP, and attempt to answer questions regarding its effectiveness as a means for enhancing diversity, and the consequent effects of any such diversity promotion on the solution finding performance of the algorithm. We find that mutation can be beneficial for GP, but subject to the proviso that it be tailored to enhance particular forms of diversity.

References

[1]

Beadle, L. and Johnson, C.G. Semantic Analysis of Program Initialisation in Genetic Programming. In Genetic Programming and Evolvable Machines, vol. 10, no. 3, 2009, 307--337.

Digital Library

[2]

Beadle, L. and Johnson, C.G. Semantically Driven Crossover in Genetic Programming. In IEEE World Congress on Computational Intelligence, IEEE Press, 2008, 111--116.

[3]

Burke, E., Gustafson, S., Kendall, G. and Krasnogor, N. Advanced Population Diversity Measures in Genetic Programming. In Proc. 7th Int. Conf. Parallel Problem Solving from Nature (PPSN), Lecture Notes in Computer Science, vol. 2439, Guervos, J.J.M et al (eds), Springer-Verlag, Berlin Heidelberg, 2002, 341--350.

Digital Library

[4]

Burke, E., Gustafson, S., and Kendall, G. Diversity in Genetic Programming: An Analysis of Measures and Correlation with Fitness. In IEEE Transactions on Evolutionary Computation, vol. 8, no. 1, Feb. 2004, 47--62.

Digital Library

[5]

de Jong, E.D., Watson, R.A. and Pollack, J.B. Reducing Bloat and Promoting Diversity using Multi-Objective Methods. In Proc. Genetic Evolutionary Computation Conf. Spector, L. et al (eds), San Francisco, CA, USA, 2001, 11--18.

[6]

Fogel, L.J. Intelligence through Simulated Evolution: Forty Years of Evolutionary Programming. Wiley, New York, 1992.

Digital Library

[7]

Jackson, D. Promoting Phenotypic Diversity in Genetic Programming. In: Proc. 11th International Conference Parallel Problem Solving from Nature (PPSN XI), Krakow, Poland, Lecture Notes in Computer Science vol. 6239, Schaefer, R. et al (eds), Springer-Verlag, Berlin, Heidelberg, 2010, 472--481.

Digital Library

[8]

Jackson, D. Phenotypic Diversity in Initial Genetic Programming Populations. In Proc. EuroGP 2010, Lecture Notes in Computer Science vol. 6021, Esparcia-Alcazar, A.I. et al (eds), Springer-Verlag, Berlin, Heidelberg, 2010, 98--109

Digital Library

[9]

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

Digital Library

[10]

Luke, S. And Spector, L. A Revised Comparison of Crossover and Mutation in Genetic Programming. In Proc. 3rd Annual Conf. Genetic Programming, Koza, J.R. et al (eds), Morgan Kaufmann, 1998, 208--213.

[11]

Miller, J.F. and Thomson, P. Cartesian Genetic Programming. In Proceedings of the 3rd European Conference on Genetic Programming, Lecture Notes in Computer Science vol. 1802, Springer-Verlag, Berlin Heidelberg, 2000, 121--132.

Digital Library

[12]

Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 1998.

Digital Library

[13]

O'Reilly, U.-M. and Oppacher, F. Program Search with a Hierarchical Variable Length Representation: Genetic Programming, Simulated Annealing and Hill Climbing. In Proc. Parallel Problem Solving from Nature (PPSN) III, Lecture Notes in Computer Science vol. 866, Y. Davidor et al (eds), Springer-Verlag, Berlin Heidelberg, 1994, 39--46.

Digital Library

[14]

Rosca, J.P. Genetic Programming Exploratory Power and the Discovery of Functions. In Proc. 4th Conf. Evolutionary Programming, McDonnell, J.R. et al (eds), San Diego, CA, USA, 1995),719--736.

[15]

Rosca, J.P. Entropy-Driven Adaptive Representation. In Proc. Workshop on Genetic Programming: From Theory to Real-World Applications, Rosca, J.P. (ed), Tahoe City, CA, USA, 1995, 23--32.

[16]

White, D.R. and Poulding, S. A Rigorous Evaluation of Crossover and Mutation in Genetic Programming. In Proc. EuroGP 2009, Lecture Notes in Computer Science, vol. 5481, Vanneschi, L. et al (eds), Springer-Verlag, Berlin Heidelberg, 2009, 220--231.

Digital Library

Cited By

Merelo CMerelo JGarcía-Valdez M(2022)A Brave New Algorithm to Maintain the Exploration/Exploitation BalanceNew Perspectives on Hybrid Intelligent System Design based on Fuzzy Logic, Neural Networks and Metaheuristics10.1007/978-3-031-08266-5_20(305-316)Online publication date: 1-Oct-2022
https://doi.org/10.1007/978-3-031-08266-5_20
Burks APunch W(2017)An analysis of the genetic marker diversity algorithm for genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-016-9281-918:2(213-245)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10710-016-9281-9
Burks APunch WEsparcia-Alcázar A(2015)An Efficient Structural Diversity Technique for Genetic ProgrammingProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754649(991-998)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754649
Show More Cited By

Index Terms

Mutation as a diversity enhancing mechanism in genetic programming
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Logical and relational learning
        Inductive logic learning

Recommendations

An Efficient Structural Diversity Technique for Genetic Programming
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Genetic diversity plays an important role in avoiding premature convergence, which is a phenomenon that stifles the search effectiveness of evolutionary algorithms. However, approaches that avoid premature convergence by maintaining genetic diversity ...
An analysis of the genetic marker diversity algorithm for genetic programming

Many diversity techniques have been developed for addressing premature convergence, which is a serious problem that stifles the search effectiveness of evolutionary algorithms. However, approaches that aim to avoid premature convergence can often take ...
The roles of diversity preservation and mutation in preventing population collapse in multiobjective genetic programming
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

It has been observed previously that genetic programming populations can collapse to all single node trees when a parsimony measure (tree node count) is used in a multiobjective setting. We have investigated the circumstances under which this can occur ...

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

4
Total Citations
View Citations
163
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

Merelo CMerelo JGarcía-Valdez M(2022)A Brave New Algorithm to Maintain the Exploration/Exploitation BalanceNew Perspectives on Hybrid Intelligent System Design based on Fuzzy Logic, Neural Networks and Metaheuristics10.1007/978-3-031-08266-5_20(305-316)Online publication date: 1-Oct-2022
https://doi.org/10.1007/978-3-031-08266-5_20
Burks APunch W(2017)An analysis of the genetic marker diversity algorithm for genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-016-9281-918:2(213-245)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10710-016-9281-9
Burks APunch WEsparcia-Alcázar A(2015)An Efficient Structural Diversity Technique for Genetic ProgrammingProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754649(991-998)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754649
Amir Haeri MEbadzadeh MFolino G(2013)Statistical Genetic Programming: The Role of DiversitySoft Computing in Industrial Applications10.1007/978-3-319-00930-8_4(37-48)Online publication date: 21-Nov-2013
https://doi.org/10.1007/978-3-319-00930-8_4

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