research-article

A probabilistic functional crossover operator for genetic programming

Author:

Josh C. BongardAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 925 - 932

https://doi.org/10.1145/1830483.1830649

Published: 07 July 2010 Publication History

Abstract

The original mechanism by which evolutionary algorithms were to solve problems was to allow for the gradual discovery of sub-solutions to sub-problems, and the automated combination of these sub-solutions into larger solutions. This latter property is particularly challenging when recombination is performed on genomes encoded as trees, as crossover events tend to greatly alter the original genomes and therefore greatly reduce the chance of the crossover event being beneficial. A number of crossover operators designed for tree-based genetic encodings have been proposed, but most consider crossing genetic components based on their structural similarity. In this work we introduce a tree-based crossover operator that probabilistically crosses branches based on the behavioral similarity between the branches. It is shown that this method outperforms genetic programming without crossover, random crossover, and a deterministic form of the crossover operator in the symbolic regression domain.

References

[1]

L. Beadle and C. Johnson. Semantically driven crossover in genetic programming. In J. Wang, editor, Proceedings of the IEEE World Congress on Computational Intelligence, pages 111--116. IEEE Press, 2008.

[2]

J. Bongard and H. Lipson. Automated reverse engineering of nonlinear dynamical systems. Proceedings of the National Academy of Science, 104(24):9943--9948, 2007.

[3]

J. C. Bongard. A functional crossover operator for genetic programming. In R. Riolo, U.-M. O'Reilly, and T. McConaghy, editors, Genetic Programming Theory and Practice VII, pages 195--210. Springer, 2010.

[4]

P. D'haeseleer. Context preserving crossover in genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 256--261. IEEE Press, 1994.

[5]

R. Fisher and J. Bennett. The genetical theory of natural selection: a complete variorum edition. Oxford University Press, USA, 1999.

[6]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.

Digital Library

[7]

N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):159--195, 2001.

Digital Library

[8]

J. H. Holland. Adaptation in Natural and Artificial Systems. Michigan Press, Ann Arbor, MI, 1975.

Digital Library

[9]

T. Jones. Crossover, macromutation, and population-based search. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 73--80. Morgan Kaufmann, 1995.

Digital Library

[10]

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

Digital Library

[11]

W. Langdon, T. Soule, R. Poli, and J. Foster. The Evolution of Size and Shape. Advances in Genetic Programming, page 163, 1999.

Digital Library

[12]

W. B. Langdon. Size fair and homologous tree genetic programming crossovers. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, pages 1092--1097. Morgan Kaufmann, 1999.

[13]

M. A. Lones and A. M. Tyrrell. Enzyme genetic programming. In Proceedings of the Congress on Evolutionary Computation, pages 1183--1190. IEEE Press, 2001.

[14]

P. Nordin, W. Banzhaf, and F. D. Francone. Efficient evolution of machine code for CISC architectures using instruction blocks and homologous crossover. In L. Spector, W. B. Langdon, U.-M. O'Reilly, and P. J. Angeline, editors, Advances in Genetic Programming 3, pages 275--299. MIT Press, 1999.

Digital Library

[15]

R. Poli. Exact schema theory for genetic programming and variable-length genetic algorithms with one-point crossover. Genetic Programming and Evolvable Machines, 2(2):123--163, 2001.

Digital Library

[16]

R. Poli and W. Langdon. Schema theory for genetic programming with one-point crossover and point mutation. Evolutionary Computation, 6(3):231--252, 1998.

Digital Library

[17]

I. Rechenberg. Evolutionsstrategie: Optimierung technischer System nach Prinzipien der biologischen Evolution. Fromann-Holzboog, Stuttgart, DE, 1994.

[18]

G. Wagner and L. Altenberg. Perspective: Complex adaptations and the evolution of evolvability. Evolution, 50(3):967--976, 1996.

Cited By

Zhou LFeng LTan KZhong JZhu ZLiu KChen C(2021)Toward Adaptive Knowledge Transfer in Multifactorial Evolutionary ComputationIEEE Transactions on Cybernetics10.1109/TCYB.2020.297410051:5(2563-2576)Online publication date: May-2021
https://doi.org/10.1109/TCYB.2020.2974100
Yoon JDeBiase M(2018)Real-Time Analysis of Big Network Packet Streams by Learning the Likelihood of Trusted SequencesBig Data – BigData 201810.1007/978-3-319-94301-5_4(43-56)Online publication date: 21-Jun-2018
https://doi.org/10.1007/978-3-319-94301-5_4
Tam KFeizollah AAnuar NSalleh RCavallaro L(2017)The Evolution of Android Malware and Android Analysis TechniquesACM Computing Surveys10.1145/301742749:4(1-41)Online publication date: 13-Jan-2017
https://dl.acm.org/doi/10.1145/3017427
Show More Cited By

Index Terms

A probabilistic functional crossover operator for genetic programming
1. Computing methodologies
  1. Artificial intelligence
    1. Philosophical/theoretical foundations of artificial intelligence

Recommendations

Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we ...
General schema theory for genetic programming with subtree-swapping crossover: Part II

This paper is the second part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover (Part I (Poli and McPhee, 2003)). Like other recent GP schema theory results, the theory gives an ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 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: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
155
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou LFeng LTan KZhong JZhu ZLiu KChen C(2021)Toward Adaptive Knowledge Transfer in Multifactorial Evolutionary ComputationIEEE Transactions on Cybernetics10.1109/TCYB.2020.297410051:5(2563-2576)Online publication date: May-2021
https://doi.org/10.1109/TCYB.2020.2974100
Yoon JDeBiase M(2018)Real-Time Analysis of Big Network Packet Streams by Learning the Likelihood of Trusted SequencesBig Data – BigData 201810.1007/978-3-319-94301-5_4(43-56)Online publication date: 21-Jun-2018
https://doi.org/10.1007/978-3-319-94301-5_4
Tam KFeizollah AAnuar NSalleh RCavallaro L(2017)The Evolution of Android Malware and Android Analysis TechniquesACM Computing Surveys10.1145/301742749:4(1-41)Online publication date: 13-Jan-2017
https://dl.acm.org/doi/10.1145/3017427
Pavai GGeetha T(2016)A Survey on Crossover OperatorsACM Computing Surveys10.1145/300996649:4(1-43)Online publication date: 20-Dec-2016
https://dl.acm.org/doi/10.1145/3009966
Majmudar CMorshed B(2016)Autonomous OA Removal in Real-Time from Single Channel EEG Data on a Wearable Device Using a Hybrid Algebraic-Wavelet AlgorithmACM Transactions on Embedded Computing Systems10.1145/298362916:1(1-16)Online publication date: 13-Oct-2016
https://dl.acm.org/doi/10.1145/2983629
Sauer CLoeb H(2016)A Lightweight Framework for the Dynamic Creation and Configuration of Virtual Platforms in SystemCACM Transactions on Embedded Computing Systems10.1145/298362616:1(1-16)Online publication date: 13-Oct-2016
https://dl.acm.org/doi/10.1145/2983626
Sotiriou-Xanthopoulos EXydis SSiozios KEconomakos GSoudris D(2016)A Framework for Interconnection-Aware Domain-Specific Many-Accelerator SynthesisACM Transactions on Embedded Computing Systems10.1145/298362416:1(1-26)Online publication date: 13-Oct-2016
https://dl.acm.org/doi/10.1145/2983624
Meyer RWagner JFarkas BHorsinka SSiegl PBuchty RBerekovic M(2016)A Scriptable Standard-Compliant Reporting and Logging Framework for SystemCACM Transactions on Embedded Computing Systems10.1145/298362316:1(1-28)Online publication date: 13-Oct-2016
https://dl.acm.org/doi/10.1145/2983623
Wehner PRettkowski JKalb TGÖhringer D(2016)Simulating Reconfigurable Multiprocessor Systems-on-Chip with MPSoCSimACM Transactions on Embedded Computing Systems10.1145/297295216:1(1-24)Online publication date: 23-Oct-2016
https://dl.acm.org/doi/10.1145/2972952
Kuan YChang YChen THuang PLam K(2016)Space-Efficient Index Scheme for PCM-Based Multiversion Databases in Cyber-Physical SystemsACM Transactions on Embedded Computing Systems10.1145/295006016:1(1-26)Online publication date: 13-Oct-2016
https://dl.acm.org/doi/10.1145/2950060
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.

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