Article

A less destructive, context-aware crossover operator for GP

Authors:

Hammad Majeed,

Conor RyanAuthors Info & Claims

EuroGP'06: Proceedings of the 9th European conference on Genetic Programming

Pages 36 - 48

https://doi.org/10.1007/11729976_4

Published: 10 April 2006 Publication History

Publisher Site

Abstract

Standard GP crossover is widely accepted as being a largely destructive operator, creating many poor offspring in the search for better ones. One of the major reasons for its destructiveness is its disrespect for the context of swapped subtrees in their respective parent trees when creating offspring. At times, this hampers GP's performance considerably, and results in populations with low average fitness values.

Many attempts have been made to make it a more constructive crossover, mostly by preserving the context of the selected subtree in the offspring. Although successful at preserving context, none of these methods provide the opportunity to discover new and better contexts for exchanged subtrees.

We introduce a context-aware crossover operator which operates by identifying all possible contexts for a subtree, and evaluating each of them. The context that produces the highest fitness is used to create a child which is then passed into the next generation.

We have tested its performance on many benchmark problems. It has shown better results than the standard GP crossover operator, using either the same number or fewer individual evaluations. Furthermore, the average fitness of populations using this scheme improves considerably, and programs produced in this way are much smaller than those produced using standard crossover.

References

[1]

Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Francone. Genetic Programming-An Introduction; On the Automatic Evolution of Computer Programs and its Applications. Morgan Kaufmann, dpunkt.verlag, January 1998.

Digital Library

Google Scholar

[2]

Patrik D'haeseleer. Context preserving crossover in genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 256-261, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.

Crossref

Google Scholar

[3]

S. Hengproprohm and P. Chongstitvatana. Selective crossover in genetic programming. In ISCIT International Symposium on Communications and Information Technologies, ChiangMai Orchid, ChiangMai Thailand, 14-16 November 2001.

Google Scholar

[4]

Takuya Ito, Hitoshi Iba, and Satoshi Sato. Non-destructive depth-dependent crossover for genetic programming. In Wolfgang Banzhaf, Riccardo Poli, Marc Schoenauer, and Terence C. Fogarty, editors, Proceedings of the First European Workshop on Genetic Programming, volume 1391 of LNCS, pages 71-82, Paris, 14-15 April 1998. Springer-Verlag.

Digital Library

Google Scholar

[5]

John R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994.

Digital Library

Google Scholar

[6]

Hammad Majeed. A new approach to evaluate GP schema in context. In Franz Rothlauf, Misty Blowers, Jürgen Branke, Stefano Cagnoni, Ivan I. Garibay, Ozlem Garibay, Jörn Grahl, Gregory Hornby, Edwin D. de Jong, Tim Kovacs, Sanjeev Kumar, Claudio F. Lima, Xavier Llorà, Fernando Lobo, Laurence D. Merkle, Julian Miller, Jason H. Moore, Michael O'Neill, Martin Pelikan, Terry P. Riopka, Marylyn D. Ritchie, Kumara Sastry, Stephen L. Smith, Hal Stringer, Keiki Takadama, Marc Toussaint, Stephen C. Upton, and Alden H. Wright, editors, Genetic and Evolutionary Computation Conference (GECCO2005) workshop program, pages 378-381, Washington, D.C., USA, 25-29 June 2005. ACM Press.

Digital Library

Google Scholar

[7]

David J. Montana. Strongly typed genetic programming. BBN Technical Report #7866, Bolt Beranek and Newman, Inc., 10 Moulton Street, Cambridge, MA 02138, USA, 7 May 1993.

Google Scholar

[8]

Riccardo Poli and William B. Langdon. On the search properties of different crossover operators in genetic programming. In John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 293-301, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.

Google Scholar

[9]

Walter Alden Tackett. Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA, 1994.

Google Scholar

[10]

K. P. Vekaria. Selective Crossover as an Adaptive Strategy for Genetic Algorithms. PhD thesis, University of London, Department of Selective Recombination (Dominance Crossover) Computer Science, University College London, UK, 1999.

Google Scholar

[11]

Chi Chung Yuen. Selective crossover using gene dominance as an adaptive strategy for genetic programming. Msc intelligent systems, University College, London, UK, September 2004.

Google Scholar

Cited By

View all

Golafshani E(2015)Introduction of Biogeography-Based Programming as a new algorithm for solving problemsApplied Mathematics and Computation10.1016/j.amc.2015.08.026270:C(1-12)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.08.026
Uy NHoai NO'Neill MMckay RPhong D(2013)On the roles of semantic locality of crossover in genetic programmingInformation Sciences: an International Journal10.1016/j.ins.2013.02.008235(195-213)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.ins.2013.02.008
Pennachin CLooks Mde Vasconcelos JPelikan MBranke J(2010)Robust symbolic regression with affine arithmeticProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830648(917-924)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830648
Show More Cited By

Recommendations

Towards a Less Destructive Crossover Operator Using Immunity Theory
ICCS '07: Proceedings of the 7th international conference on Computational Science, Part IV: ICCS 2007

When searching for good scheme, a good solution can be destroyed by an inappropriate choice of crossover points. Furthermore, because of the randomicity of crossover, mutation and selection, a better solution can hardly reach in last stage in EA, and ...
A parameter-less genetic algorithm with customized crossover and mutation operators
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Genetic algorithm is one of the well-known population based meta-heuristics. The reasonable performance of the algorithm on a wide variety of problems as well as its simplicity made this algorithm a first choice in lots of cases. However, the algorithm ...
Using context-aware crossover to improve the performance of GP
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

This paper describes the use of a recently introduced crossover operator for GP, context-aware crossover. Given a randomly selected subtree from one parent, context-aware crossover will always find the best location to place the subtree in the other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EuroGP'06: Proceedings of the 9th European conference on Genetic Programming

April 2006

360 pages

ISBN:3540331433

Editors:
Pierre Collet
Université Louis Pasteur, LSIIT, FDBT, Pôle API, Illkirch, France
,
Marco Tomassini
Institut des Systèmes d'Information (ISI), Université de Lausanne, Hautes Etudes Commerciales (HEC), Illkirch
,
Marc Ebner
Lehrstuhl für Informatik II, Universität Würzburg, Am Hubland, Würzburg, Germany
,
Steven Gustafson
GE Global Research, Niskayuna, NY, Germany
,
Anikó Ekárt
Aston University, Birmingham, UK

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 April 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
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

View all

Golafshani E(2015)Introduction of Biogeography-Based Programming as a new algorithm for solving problemsApplied Mathematics and Computation10.1016/j.amc.2015.08.026270:C(1-12)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.08.026
Uy NHoai NO'Neill MMckay RPhong D(2013)On the roles of semantic locality of crossover in genetic programmingInformation Sciences: an International Journal10.1016/j.ins.2013.02.008235(195-213)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1016/j.ins.2013.02.008
Pennachin CLooks Mde Vasconcelos JPelikan MBranke J(2010)Robust symbolic regression with affine arithmeticProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830648(917-924)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830648
Uy NHoai NO'Neill MMcKay BPelikan MBranke J(2010)Semantics based crossover for boolean problemsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830642(869-876)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830642
Uy NO'Neill MHoai NMckay BGalván-López E(2009)Semantic similarity based crossover in GPProceedings of the 9th international conference on Artificial evolution10.5555/1883723.1883745(170-181)Online publication date: 26-Oct-2009
https://dl.acm.org/doi/10.5555/1883723.1883745
Tchougang ABlansché ABaumes LLachiche NCollet P(2008)Testing the CAX on a Real-World Problem and Other BenchmarksProceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 519910.5555/2951659.2951722(599-609)Online publication date: 13-Sep-2008
https://dl.acm.org/doi/10.5555/2951659.2951722
Krawiec KPolewski PRyan C(2008)Potential fitness for genetic programmingProceedings of the 10th annual conference companion on Genetic and evolutionary computation10.1145/1388969.1389043(2175-2180)Online publication date: 12-Jul-2008
https://dl.acm.org/doi/10.1145/1388969.1389043
Xie HZhang MAndreae PLipson H(2007)An analysis of constructive crossover and selection pressure in genetic programmingProceedings of the 9th annual conference on Genetic and evolutionary computation10.1145/1276958.1277297(1739-1748)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1276958.1277297
Majeed HRyan CLipson H(2007)On the constructiveness of context-aware crossoverProceedings of the 9th annual conference on Genetic and evolutionary computation10.1145/1276958.1277286(1659-1666)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1276958.1277286
Majeed HRyan CLipson H(2007)Context-aware mutationProceedings of the 9th annual conference on Genetic and evolutionary computation10.1145/1276958.1277285(1651-1658)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1276958.1277285
Show More Cited By

Abstract

References

Cited By

Recommendations

Towards a Less Destructive Crossover Operator Using Immunity Theory

A parameter-less genetic algorithm with customized crossover and mutation operators

Using context-aware crossover to improve the performance of GP

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations