Article

Crossover in Grammatical Evolution: The Search Continues

Authors:

Michael O'Neill,

Maarten Keijzer,

Mike CattolicoAuthors Info & Claims

EuroGP '01: Proceedings of the 4th European Conference on Genetic Programming

Pages 337 - 347

Published: 18 April 2001 Publication History

Abstract

Grammatical Evolution is an evolutionary automatic programming algorithm that can produce code in any language, requiring as inputs a BNF grammar definition describing the output language, and the fitness function. The utility of crossover in GP systems has been hotly debated for some time, and this debate has also arisen with respect to Grammatical Evolution. This paper serves to continue an analysis of the crossover operator in Grammatical Evolution by looking at the result of turning off crossover, and by exchanging randomly generated blocks in a headless chicken-like crossover. Results show that crossover in Grammatical Evolution is essential on the problem domains examined. The mechanism of one-point crossover in Grammatical Evolution is discussed, resulting in the discovery of some interesting properties that could yield an insight into the operator's success.

References

[1]

Angeline, P.J. 1997. Subtree Crossover: Building block engine or macromutation? In Proceedings of GP'97 , pages 9-17.

[2]

Collins, R. 1992. Studies in Artificial Life. PhD thesis. University of California, Los Angeles.

[3]

Francone F. D., Banzhaf W., Conrads M, Nordin P. 1999. Homologous Crossover in Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 99 , pages 1021-1038.

[4]

Goldberg, David E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley.

[5]

Keijzer M., Ryan C., O'Neill M., Cattolico M., Babovic V. 2001. Ripple Crossover in Genetic Programming. In Proceedings of EuroGP 2001 .

[6]

Koza, J. 1992. Genetic Programming . MIT Press.

[7]

Langdon W.B. 1999. Size Fair and Homologous Tree Genetic Programming Crossovers. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 99 , pages 1092-1097.

[8]

Langdon W.B., Soule T., Poli R., and Foster J.A. 1999. The Evolution of Size and Shape. In Advances in Genetic Programming Volume 3 , MIT Press 1999, pp. 162-190.

[9]

O'Neill M. and Ryan C. 2001. Grammatical Evolution. IEEE Trans. Evolutionary Computation , 2001.

[10]

Justinian P. Rosca and Dana H. Ballard. 1999. Rooted-Tree Schemata in Genetic Programming, in Advances in Genetic Programming 3 , Chapter 11, pp. 243-271, 1999, MIT Press.

[11]

O'Neill M. and Ryan C. 2000. Crossover in Grammatical Evolution: A Smooth Operator? Lecture Notes in Computer Science 1802, Proceedings of the European Conference on Genetic Programming , pages 149-162. Springer-Verlag.

[12]

O'Neill M. and Ryan C. 1999. Genetic Code Degeneracy: Implications for Grammatical Evolution and Beyond. In Proceedings of the Fifth European Conference on Artificial Life .

[13]

O'Neill M. and Ryan C. 1999. Under the Hood of Grammatical Evolution. In Proceedings of the Genetic & Evolutionary Computation Conference 1999 .

[14]

O'Neill M. and Ryan C. 1999. Evolving Multi-line Compilable C Programs. Lecture Notes in Computer Science 1598, Proceedings of the Second European Workshop on Genetic Programming , pages 83-92. Springer-Verlag.

[15]

Poli Riccardo, Langdon W.B. 1998. On the Search Properties of Different Crossover Operators in Genetic Programming. In Proceedings of the Third annual Genetic Programming conference 1998 , pages 293-301.

[16]

Ryan C. and O'Neill M. 1998. Grammatical Evolution: A Steady State Approach. In Late Breaking Papers, Genetic Programming 1998 , pages 180-185.

[17]

Ryan C., Collins J.J., and O'Neill M. 1998. Grammatical Evolution: Evolving Programs for an Arbitrary Language. Lecture Notes in Computer Science 1391, Proceedings of the First European Workshop on Genetic Programming , pages 83- 95. Springer-Verlag.

Cited By

Thorhauer ARothlauf FAlba E(2013)Structural difficulty in grammatical evolution versus genetic programmingProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463491(997-1004)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463491
Alexander BGratton M(2009)Constructing an optimisation phase using grammatical evolutionProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689760(1209-1216)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689760

Crossover in Grammatical Evolution: The Search Continues
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Crossover in Grammatical Evolution

We present an investigation into crossover in Grammatical Evolution that begins by examining a biologically-inspired homologous crossover operator that is compared to standard one and two-point operators. Results demonstrate that this homologous ...
A feature-guided grammatical system
Grammatical evolution
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

Grammatical Evolution is an automatic programming system that is a form of Genetic Programming that uses grammars to evolve structures. These structures can be in any form that can be specified using a grammar, including computer languages, graphs and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EuroGP '01: Proceedings of the 4th European Conference on Genetic Programming

April 2001

379 pages

ISBN:3540418997

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 18 April 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thorhauer ARothlauf FAlba E(2013)Structural difficulty in grammatical evolution versus genetic programmingProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463491(997-1004)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463491
Alexander BGratton M(2009)Constructing an optimisation phase using grammatical evolutionProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689760(1209-1216)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689760

View Options

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

Media

Figures

Other

Tables

View Table of Contents