research-article

On the Bias of Syntactic Geometric Recombination in Genetic Programming and Grammatical Evolution

Authors:

Franz RothlaufAuthors Info & Claims

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

Pages 1103 - 1110

https://doi.org/10.1145/2739480.2754726

Published: 11 July 2015 Publication History

Abstract

For fixed-length binary representations as used in genetic algorithms, standard recombination operators (e.g.,~one-point crossover) are unbiased. Thus, the application of recombination only reshuffles the alleles and does not change the statistical properties in the population. Using a geometric view on recombination operators, most search operators for fixed-length strings are geometric, which means that the distances between offspring and their parents are less than, or equal to, the distance between their parents. In genetic programming (GP) and grammatical evolution (GE), the situation is different since the recombination operators are applied to variable-length structures. Thus, most recombination operators for GE and GP are not geometric.

This paper focuses on the bias of recombination in GE and GP and studies whether the application of recombination alone produces specific types of solutions with a higher probability. We consider two different types of recombination operators: standard recombination and syntactic geometric recombination. In our experiments, we performed random walks through the binary tree search space and found that syntactic geometric recombination operators are biased and strongly reduce population diversity. In a performance comparison, we found that syntactic geometric recombination leads to large fitness improvements in the first generations, but that fitness converges after several generations and no further search is possible.

References

[1]

J. D. Caruana, Rich and Schaffer. Representation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms. In Proceedings of the Fifth International Workshop on Machine Learning, 1988.

[2]

T. Castle and C. G. Johnson. Positional effect of crossover and mutation in grammatical evolution. In Genetic Programming, volume 6021 LNCS, pages 26--37. Springer, 2010.

Digital Library

[3]

J. M. Daida. Limits to expression in genetic programming: Lattice-aggregate modeling. In Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002, volume 1, pages 273--278. IEEE Press, 2002.

[4]

J. M. Daida and A. M. Hilss. Identifying Structural Mechanisms in Standard Genetic Programming. In Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 LNCS, pages 1639--1651. Springer, 2003.

Digital Library

[5]

J. M. Daida, H. Li, R. Tang, and A. M. Hilss. What Makes a Problem GP-Hard? Validating a Hypothesis of Structural Causes. In Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 LNCS, pages 1665--1677. Springer, 2003.

Digital Library

[6]

D. Goldberg, B. Korb, and K. Deb. Messy Genetic Algorithms: Motivation, Analysis, and First Results. Complex Systems, 3:493--530, 1989.

[7]

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

Digital Library

[8]

K. Krawiec and T. Pawlak. Locally geometric semantic crossover: A study on the roles of semantics and homology in recombination operators. Genetic Programming and Evolvable Machines, 14(1):31--63, 2013.

Digital Library

[9]

N. F. McPhee, B. Ohs, and T. Hutchison. Semantic Building Blocks in Genetic Programming. In Proceedings of the 11th European Conference on Genetic Programming, volume 4971 LNCS, pages 134--145, Naples, Italy, 2008. Springer.

Digital Library

[10]

A. Moraglio. Towards a geometric unification of evolutionary algorithms. Phd, University of Essex, 2007.

[11]

A. Moraglio, K. Krawiec, and C. G. Johnson. Geometric Semantic Genetic Programming. In Parallel Problem Solving from Nature - PPSN XII, volume 7491 LNCS, pages 21--31. Springer, 2012.

Digital Library

[12]

A. Moraglio and R. Poli. Geometric landscape of homologous crossover for syntactic trees. In Congress on Evolutionary Computation, pages 427--434. IEEE, 2005.

[13]

R. Moraglio, Alberto and Poli. Topological Interpretation of Crossover. In Genetic and Evolutionary Computation -- GECCO 2004, volume 3102 LNCS, pages 1259--1271. Springer, 2004.

[14]

M. O'Neill and C. Ryan. Grammatical Evolution. IEEE Transactions on Evolutionary Computation, 5(4):349--358, 2001.

Digital Library

[15]

M. O'Neill, C. Ryan, M. Keijzer, and M. Cattolico. Crossover in Grammatical Evolution. Genetic Programming and Evolvable Machines, 4:67--93, 2003.

Digital Library

[16]

M. Pawlik and N. Augsten. RTED: a robust algorithm for the tree edit distance. Proceedings of the VLDB Endowment, pages 334--345, 2011.

Digital Library

[17]

F. Rothlauf. Representations for genetic and evolutionary algorithms. Springer, 2006.

Digital Library

[18]

F. Rothlauf. Design of Modern Heuristics. Natural Computing Series. Springer, Berlin, Heidelberg, 2011.

Digital Library

[19]

F. Rothlauf and D. E. Goldberg. Redundant Representations in Evolutionary Computation. Evolutionary Computation, 11:381--415, 2003.

Digital Library

[20]

F. Rothlauf and M. Oetzel. On the Locality of Grammatical Evolution. In Proceedings of the 9th European Conference on Genetic Programming, volume 3905 LNCS, pages 320--330, Budapest, Hungary, 2006. Springer.

Digital Library

[21]

A. Thorhauer and F. Rothlauf. Structural difficulty in grammatical evolution versus genetic programming. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference, pages 997--1004. ACM, 2013.

Digital Library

[22]

N. Uy, M. O'Neill, N. Hoai, B. Mckay, and E. Galván-López. Semantic Similarity Based Crossover in GP: The Case for Real-Valued Function Regression. In Artifical Evolution, volume 5975 LNCS, pages 170--181. Springer, 2010.

Digital Library

[23]

N. Q. Uy, N. X. Hoai, M. O. Neill, and B. Mckay. The Role of Syntactic and Semantic Locality of Crossover in Genetic Programming. In Parallel Problem Solving from Nature PPSN XI, volume 6239 LNCS, pages 533--542. Springer, 2010.

Digital Library

[24]

N. Q. Uy, N. X. Hoai, M. O'Neill, R. McKay, and D. N. Phong. On the roles of semantic locality of crossover in genetic programming. Information Sciences, 235:195--213, June 2013.

Digital Library

[25]

P. A. Whigham. Grammatically-based Genetic Programming. In Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 33--41. Morgan Kaufmann, 1995.

[26]

P. A. Whigham. Search Bias, Language Bias, and Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference, pages 230--237, 1996.

Digital Library

Cited By

Schweim D(2021)On the Influence of Grammars on Crossover in Grammatical EvolutionGenetic Programming10.1007/978-3-030-72812-0_8(114-129)Online publication date: 25-Mar-2021
https://doi.org/10.1007/978-3-030-72812-0_8
García MMoraglio A(2019)A Unifying View on Recombination Spaces and Abstract Convex Evolutionary SearchTheory and Applications of Models of Computation10.1007/978-3-030-16711-0_12(179-195)Online publication date: 28-Mar-2019
https://doi.org/10.1007/978-3-030-16711-0_12
Schweim DRothlauf FTakadama K(2018)An analysis of the bias of variation operators of estimation of distribution programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205582(1191-1198)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205582

Index Terms

On the Bias of Syntactic Geometric Recombination in Genetic Programming and Grammatical Evolution
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

Structural and nodal mutation in grammatical evolution
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

This study focuses on mutation in Grammatical Evolution and divides mutation events into those that are structural in nature and those that are nodal. A structural event being one that alters the length of the phenotype. A nodal event simply alters the ...
Positional effect of crossover and mutation in grammatical evolution
EuroGP'10: Proceedings of the 13th European conference on Genetic Programming

An often-mentioned issue with Grammatical Evolution is that a small change in the genotype, through mutation or crossover, may completely change the meaning of all of the following genes. This paper analyses the crossover and mutation operations in GE, ...
Diverse partner selection with brood recombination in genetic programming
Graphical abstract

Display Omitted
Highlights
- Optimal parent selection during crossover in genetic programming.
- Exploitation ...
Abstract
The ultimate goal of learning algorithms is to find the best solution from a search space without testing each and every solution available in the search space. During the evolution process new solutions (children) are produced from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 2015 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 the author(s) 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: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

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%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
93
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schweim D(2021)On the Influence of Grammars on Crossover in Grammatical EvolutionGenetic Programming10.1007/978-3-030-72812-0_8(114-129)Online publication date: 25-Mar-2021
https://doi.org/10.1007/978-3-030-72812-0_8
García MMoraglio A(2019)A Unifying View on Recombination Spaces and Abstract Convex Evolutionary SearchTheory and Applications of Models of Computation10.1007/978-3-030-16711-0_12(179-195)Online publication date: 28-Mar-2019
https://doi.org/10.1007/978-3-030-16711-0_12
Schweim DRothlauf FTakadama K(2018)An analysis of the bias of variation operators of estimation of distribution programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205582(1191-1198)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205582

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