research-article

An Efficient Structural Diversity Technique for Genetic Programming

Authors:

Armand R. Burks,

William F. PunchAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 991 - 998

https://doi.org/10.1145/2739480.2754649

Published: 11 July 2015 Publication History

Get Access

Abstract

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 can do so at the cost of efficiency, requiring more fitness evaluations to find high quality solutions. We introduce a simple and efficient genetic diversity technique that is capable of avoiding premature convergence while maintaining a high level of search quality in tree-based genetic programming. Our method finds solutions to a set of benchmark problems in significantly fewer fitness evaluations than the algorithms that we compared against.

References

[1]

E. Burke, S. Gustafson, and G. Kendall. Diversity in genetic programming: An analysis of measures and correlation with fitness. Evolutionary Computation, IEEE Transactions on, 8(1):47--62, 2004.

Digital Library

Google Scholar

[2]

E. de Jong, R. Watson, and J. Pollack. Reducing bloat and promoting diversity using multi-objective methods. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2001, pages 11--18. Morgan Kaufmann, 2001.

Google Scholar

[3]

C. Gathercole and P. Ross. An adverse interaction between crossover and restricted tree depth in genetic programming. In Proceedings of the 1st Annual Conference on Genetic Programming, pages 291--296, Cambridge, MA, USA, 1996. MIT Press.

Digital Library

Google Scholar

[4]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989.

Digital Library

Google Scholar

[5]

G. S. Hornby. Alps: The age-layered population structure for reducing the problem of premature convergence. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO '06, pages 815--822, New York, NY, USA, 2006. ACM.

Digital Library

Google Scholar

[6]

J. Hu, E. Goodman, K. Seo, Z. Fan, and R. Rosenberg. The hierarchical fair competition (hfc) framework for sustainable evolutionary algorithms. Evol. Comput., 13(2):241--277, June 2005.

Digital Library

Google Scholar

[7]

J. Hu, K. Seo, S. Li, Z. Fan, R. C. Rosenberg, and E. D. Goodman. Structure fitness sharing (sfs) for evolutionary design by genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 780--787. Morgan Kaufmann Publishers, 2002.

Digital Library

Google Scholar

[8]

M. Hutter and S. Legg. Fitness uniform optimization. Evolutionary Computation, IEEE Transactions on, 10(5):568--589, 2006.

Digital Library

Google Scholar

[9]

D. Jackson. Mutation as a diversity enhancing mechanism in genetic programming. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO '11, pages 1371--1378, New York, NY, USA, 2011. ACM.

Digital Library

Google Scholar

[10]

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

Digital Library

Google Scholar

[11]

J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evol. Comput., 19(2):189--223, June 2011.

Digital Library

Google Scholar

[12]

N. F. McPhee and N. J. Hopper. Analysis of genetic diversity through population history. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1112--1120. Morgan Kaufmann, 1999.

Digital Library

Google Scholar

[13]

R. Poli and W. Langdon. On the search properties of different crossover operators in genetic programming. In Genetic Programming, pages 293--301. Morgan Kaufmann, 1998.

Google Scholar

[14]

M. Schmidt and H. Lipson. Age-fitness pareto optimization. Genetic Programming Theory and Practice VIII, 8:129--146, 2011.

Crossref

Google Scholar

Cited By

View all

Burlacu BYang KAffenzeller M(2023)Population diversity and inheritance in genetic programming for symbolic regressionNatural Computing10.1007/s11047-022-09934-x23:3(531-566)Online publication date: 17-Jan-2023
https://doi.org/10.1007/s11047-022-09934-x
Salama SKaihara TFujii NKokuryo D(2022)Multi-Objective Approach with a Distance Metric in Genetic Programming for Job Shop SchedulingInternational Journal of Automation Technology10.20965/ijat.2022.p029616:3(296-308)Online publication date: 5-May-2022
https://doi.org/10.20965/ijat.2022.p0296
Sijben EAlderliesten TBosman PWagner M(2022)Multi-modal multi-objective model-based genetic programming to find multiple diverse high-quality modelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528850(440-448)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528850
Show More Cited By

Index Terms

An Efficient Structural Diversity Technique for Genetic Programming
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Reducing Antagonism between Behavioral Diversity and Fitness in Semantic Genetic Programming
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Maintaining population diversity has long been considered fundamental to the effectiveness of evolutionary algorithms. Recently, with the advent of novelty search, there has been an increasing interest in sustaining behavioral diversity by using both ...
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 ...
Research on Diversity Measure of Niche Genetic Algorithm
WGEC '08: Proceedings of the 2008 Second International Conference on Genetic and Evolutionary Computing

Niche genetic algorithm (NGA) is superior to genetic algorithm (GA) in multiple hump function optimization. NGA could search all global optimums of multiple hump function in a running. It is a class of parallel evolutionary method which suppresses ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
258
Total Downloads

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

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Burlacu BYang KAffenzeller M(2023)Population diversity and inheritance in genetic programming for symbolic regressionNatural Computing10.1007/s11047-022-09934-x23:3(531-566)Online publication date: 17-Jan-2023
https://doi.org/10.1007/s11047-022-09934-x
Salama SKaihara TFujii NKokuryo D(2022)Multi-Objective Approach with a Distance Metric in Genetic Programming for Job Shop SchedulingInternational Journal of Automation Technology10.20965/ijat.2022.p029616:3(296-308)Online publication date: 5-May-2022
https://doi.org/10.20965/ijat.2022.p0296
Sijben EAlderliesten TBosman PWagner M(2022)Multi-modal multi-objective model-based genetic programming to find multiple diverse high-quality modelsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528850(440-448)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528850
Nieto-Fuentes RSegura C(2022)GP-DMD: a genetic programming variant with dynamic management of diversityGenetic Programming and Evolvable Machines10.1007/s10710-021-09426-423:2(279-304)Online publication date: 21-Jan-2022
https://doi.org/10.1007/s10710-021-09426-4
Batot ESahraoui H(2022)Promoting social diversity for the automated learning of complex MDE artifactsSoftware and Systems Modeling10.1007/s10270-021-00969-921:3(1159-1178)Online publication date: 19-Jan-2022
https://doi.org/10.1007/s10270-021-00969-9
Zhang HZhang HZhou A(2020)A Multi-metric Selection Strategy for Evolutionary Symbolic Regression2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC42975.2020.9283385(585-591)Online publication date: 11-Oct-2020
https://doi.org/10.1109/SMC42975.2020.9283385
Oliveira LMartins JMiranda LPappa GTakadama K(2018)Analysing symbolic regression benchmarks under a meta-learning approachProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208293(1342-1349)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208293
Harris SMichalak ESchoonover KGausmann AReinbolt HHerman JTauritz DRawlings CPope ATakadama K(2018)Evolution of network enumeration strategies in emulated computer networksProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208270(1640-1647)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208270
Burlacu BAffenzeller MTakadama K(2018)Schema-based diversification in genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205594(1111-1118)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205594
Burks APunch WTakadama K(2018)Genetic programming for tuberculosis screening from raw X-ray imagesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205461(1214-1221)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205461
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

Index Terms

Recommendations

Reducing Antagonism between Behavioral Diversity and Fitness in Semantic Genetic Programming

An analysis of the genetic marker diversity algorithm for genetic programming

Research on Diversity Measure of Niche Genetic Algorithm