research-article

Managing Repetition in Grammar-Based Genetic Programming

Authors:

Miguel Nicolau,

Michael FentonAuthors Info & Claims

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Pages 765 - 772

https://doi.org/10.1145/2908812.2908904

Published: 20 July 2016 Publication History

Abstract

Grammar-based Genetic Programming systems are capable of generating identical phenotypic solutions, either by creating repeated genotypic representations, or from distinct genotypes, through their many-to-one mapping process. Furthermore, their initialisation process can generate a high number of duplicate individuals, while traditional variation and replacement operators can permit multiple individuals to percolate through generations unchanged. This can lead to a high number of phenotypically identical individuals within a population. This study investigates the frequency and effect of such duplicate individuals on a suite of benchmark problems. Both Grammatical Evolution and the CFG-GP systems are examined. Experimental evidence suggests that these useless evaluations can be instead be used either to speed-up the evolutionary process, or to delay convergence.

References

[1]

J. Balicki. Tabu programming for multiobjective optimization problems. IJCSNS International Journal of Computer Science and Network Security, 7(10):44--51, October 2007.

[2]

W. Banzhaf. Genotype-phenotype-mapping and neutral variation -- A case study in genetic programming. In Y. Davidor, H.-P. Schwefel, and R. Manner, editors, Parallel Problem Solving from Nature - PPSN III, volume 866 of LNCS, pages 322--332. Springer-Verlag, 1994.

Digital Library

[3]

C. D. Chio, S. Cagnoni, C. Cotta, M. Ebner, A. Ekart, A. I. Esparcia-Alcázar, C.-K. Goh, J. J. Merelo, F. Neri, M. Preuss, J. Togelius, and G. N. Yannakakis, editors. Applications of Evolutionary Computation, EvoApplications 2010: EvoCOMPLEX, EvoGAMES, EvoIASP, EvoINTELLIGENCE, EvoNUM, and EvoSTOC, volume 6024 of LNCS. EvoStar, Springer, 2010.

Digital Library

[4]

M. Fenton, C. McNally, J. Byrne, E. Hemberg, J. McDermott, and M. O'Neill. Automatic innovative truss design using grammatical evolution. Automation in Construction, 39:59--69, 2014.

[5]

F. Glover. Future paths for integer programming and links to artificial intelligence. Computers & operations research, 13(5):533--549, 1986.

Digital Library

[6]

F. Glover, J. P. Kelly, and M. Laguna. Genetic algorithms and tabu search: Hybrids for optimization. Computers & Operations Research, 22(1):111--134, 1995.

Digital Library

[7]

B. W. Goldman and W. F. Punch. Reducing wasted evaluations in cartesian genetic programming. In K. Krawiec, A. Moraglio, T. Hu, S. E.-U. A., and B. Hu, editors, Genetic Programming, 16th European Conference, EuroGP 2013, volume 7831 of LNCS, pages 61--72. Springer, 2013.

Digital Library

[8]

R. Harper. GE, explosive grammars and the lasting legacy of bad initialisation. In IEEE Congress on Evolutionary Computation, CEC 2010, pages 2602--2609, 2010.

[9]

E. Hemberg, L. Ho, M. O'Neill, and H. Claussen. A symbolic regression approach to manage femtocell coverage using grammatical genetic programming. In N. K. et al., editor, Genetic and Evolutionary Computation - GECCO 2011, pages 639--646. ACM, 2011.

Digital Library

[10]

M. Keijzer. Improving symbolic regression with interval arithmetic and linear scaling. In C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, and E. Costa, editors, Genetic Programming, 6th European Conference, EuroGP 2003, volume 2610 of LNCS, pages 70--82. Springer, 2003.

Digital Library

[11]

M. Keijzer. Alternatives in subtree caching for genetic programming. In M. Keijzer, A. Tettamanzi, P. Collet, J. van Hemert, and M. Tomassini, editors, Genetic Programming, 8th European Conference, EuroGP 2005, volume 3447 of LNCS, pages 328--337. Springer, 2005.

[12]

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

Digital Library

[13]

W. B. Langdon, B. Y. H. Lam, J. Petke, and M. Harman. Improving cuda dna analysis software with genetic programming. In S. Silva, editor, Genetic and Evolutionary Computation - GECCO 2015, pages 1063--1070. ACM, 2015.

Digital Library

[14]

J. F. Miller and P. Thomson. Restricted evaluation genetic algorithms with tabu search for optimising boolean functions as multi-level and-exor networks. In T. C. Fogarty, editor, Evolutionary Computing, AISB Workshop, Brighton, UK, April 1--2, 1996, Selected Papers, volume 1141 of LNCS, pages 85--101. Springer, 1996.

Digital Library

[15]

E. Murphy, E. Hemberg, M. Nicolau, M. O'Neill, and A. Brabazon. Grammar bias and initialisation in grammar based genetic programming. In A. Moraglio, S. Silva, K. Krawiec, P. Machado, and C. Cotta, editors, Genetic Programming, 15th European Conference, EuroGP 2012, volume 7244 of LNCS, pages 85--96. Springer, 2012.

Digital Library

[16]

M. Nicolau. Automatic grammar complexity reduction in grammatical evolution. In R. P. et al., editor, Genetic and Evolutionary Computation - GECCO 2004, 2004.

[17]

M. Nicolau, A. Agapitos, M. O'Neill, and A. Brabazon. Guidelines for defining benchmark problems in genetic programming. In IEEE Congress on Evolutionary Computation, CEC 2015, Sendai, Japan, May 25--28, 2015, Proceedings, 2015.

[18]

M. Nicolau, M. O'Neill, and A. Brabazon. Termination in grammatical evolution: Grammar design, wrapping, and tails. In IEEE Congress on Evolutionary Computation, CEC 2012, Brisbane, Australia, June 10--15, 2012, Proceedings, pages 1--8. IEEE Press, 2012.

[19]

M. O'Neill and C. Ryan. Grammatical Evolution - Evolutionary Automatic Programming in an Arbitrary Language, volume 4 of Genetic Programming. Kluwer Academic, 2003.

Digital Library

[20]

R. Poli, W. B. Langdon, N. F. McPhee, and J. R. Koza. A field guide to genetic programming. 2008.

Digital Library

[21]

C. Ryan and A. Azad. Sensible initialisation in grammatical evolution. In E. C.-P. et al., editor, Genetic and Evolutionary Computation - GECCO 2003. AAAI, 2003.

[22]

C. Ryan, M. Keijzer, and M. Nicolau. On the avoidance of fruitless wraps in grammatical evolution. In E. C.-P. et al., editor, Genetic and Evolutionary Computation - GECCO 2003, volume 2724 of LNCS, pages 1752--1763. Springer, 2003.

Digital Library

[23]

C.-K. Ting, C.-F. Ko, and C.-H. Huang. Selecting survivors in genetic algorithm using tabu search strategies. Memetic Computing, 1:191--203, September 2009.

[24]

E. J. Vladislavleva, G. F. Smits, and D. den Hertog. Order of nonlinearity as a complexity measure for models generated by symbolic regression via pareto genetic programming. IEEE Transactions on Evolutionary Computation, 13(2):333--349, 2009.

Digital Library

[25]

P. A. Whigham. Grammatically-based genetic programming. In Proceedings of the workshop on genetic programming: from theory to real-world applications, volume 16, pages 33--41, 1995.

[26]

D. R. White, J. McDermott, M. Castelli, L. Manzoni, B. W. Goldman, G. Kronberger, W. Jaskowski, U.-M. O'Reilly, and S. Luke. Better gp benchmarks: community survey results and proposals. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 14(1):3--29, 2013.

Digital Library

[27]

P. Wong. Scheme: Caching subtrees in genetic programming. In IEEE Congress on Evolutionary Computation, CEC 2008, Hong-Kong, June 1--6, 2008, Proceedings, pages 2678--2685, 2008.

Cited By

Ramos Criado PBarrios Rolanía DManrique DSerrano E(2020)Grammatically uniform population initialization for grammar-guided genetic programmingSoft Computing10.1007/s00500-020-05061-wOnline publication date: 12-Jun-2020
https://doi.org/10.1007/s00500-020-05061-w
Hemberg EKelly JO'Reilly UAuger AStützle T(2019)On domain knowledge and novelty to improve program synthesis performance with grammatical evolutionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321865(1039-1046)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321865
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
Show More Cited By

Index Terms

Managing Repetition in Grammar-Based Genetic Programming
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic programming
2. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

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 ...
Segment-based genetic programming
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

Genetic Programming (GP) is one of the successful evolutionary computation techniques applied to solve classification problems, by searching for the best classification model applying the fitness evaluation. The fitness evaluation process greatly ...
Fitness landscapes and problem hardness in genetic programming
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

The performance of searching agents, or metaheuristics, like evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algorithms (simulated annealing, tabu search, etc.) depend on some properties of the search space ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

July 2016

1196 pages

ISBN:9781450342063

DOI:10.1145/2908812

Editor:
Tobias Friedrich
Hasso Plattner Institute
,
General Chair:
Frank Neumann
University of Adelaide
,
Program Chair:
Andrew M. Sutton
Hasso Plattner Institute

Copyright © 2016 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: 20 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Science Foundation Ireland

Conference

GECCO '16

Sponsor:

SIGEVO

GECCO '16: Genetic and Evolutionary Computation Conference

July 20 - 24, 2016

Colorado, Denver, USA

Acceptance Rates

GECCO '16 Paper Acceptance Rate 137 of 381 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
103
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ramos Criado PBarrios Rolanía DManrique DSerrano E(2020)Grammatically uniform population initialization for grammar-guided genetic programmingSoft Computing10.1007/s00500-020-05061-wOnline publication date: 12-Jun-2020
https://doi.org/10.1007/s00500-020-05061-w
Hemberg EKelly JO'Reilly UAuger AStützle T(2019)On domain knowledge and novelty to improve program synthesis performance with grammatical evolutionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321865(1039-1046)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321865
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
Cody-Kenny BFenton MRonayne AConsidine EMcGuire TO'Neill MBosman P(2017)A search for improved performance in regular expressionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071196(1280-1287)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071196
Fenton MMcDermott JFagan DForstenlechner SHemberg EO'Neill M(2017)PonyGE2Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3082469(1194-1201)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3082469
Nicolau M(2017)Understanding grammatical evolutionGenetic Programming and Evolvable Machines10.1007/s10710-017-9309-918:4(467-507)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10710-017-9309-9

View Options

Get Access

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