skip to main content
10.1145/1276958.1277297acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

An analysis of constructive crossover and selection pressure in genetic programming

Published: 07 July 2007 Publication History

Abstract

A common problem in genetic programming search algorithms is destructive crossover in which the offspring of good parents generally has worse performance than the parents. Designing constructive crossover operators and integrating some local search techniques into the breeding process have been suggested as solutions. This paper reports on experiments demonstrating that premature convergence may happen more often when using these techniques in combination with standard parent selection. It shows that modifying the selection pressure in the parent selection process is necessary to obtain a significant performance improvement.

References

[1]
T. Blickle and L. Thiele. A mathematical analysis of tournament selection. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 9--16. Morgan Kaufmann, 1995.
[2]
C. B. D.J. Newman, S. Hettich and C. Merz. UCI repository of machine learning databases, 1998.
[3]
A. E. Eiben and C. A. Schippers. On evolutionary exploration and exploitation. Fundamenta Informaticae, 35(1-4):35--50, 1998.
[4]
S. M. Gustafson. An Analysis of Diversity in Genetic Programming. PhD thesis, University of Nottingham, 2004.
[5]
K. Harries and P. Smith. Exploring alternative operators and search strategies in genetic programming. In J. R. Koza, et al, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 147--155, Stanford University, CA, USA, 1997. Morgan Kaufmann.
[6]
J. R. Koza. Genetic Programming - On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, 1992.
[7]
J. R. Koza. A response to the ML-95 paper entitled "Hill climbing beats genetic search on a boolean circuit synthesis of Koza's". Distributed 11 July 1995 at the 1995 International Machine Learning Conference in Tahoe City, California, USA, 11 July 1995.
[8]
K. J. Lang. Hill climbing beats genetic search on a boolean circuit synthesis of Koza's. In Proceedings of the Twelfth International Conference on Machine Learning, 1995. Morgan Kaufmann.
[9]
S. W. Mahfoud. Crowding and preselection revisited. In R. Männer and B. Manderick, editors, Parallel problem solving from nature 2, pages 27--36, Amsterdam, 1992. North-Holland.
[10]
H. Majeed and C. Ryan. A less destructive, context-aware crossover operator for GP. In P. Collet and et al, editors, Proceedings of EuroGP 2006, volume 3905 of LNCS, pages 36--48. Springer-Verlag, 2006.
[11]
P. Nordin and W. Banzhaf. Complexity compression and evolution. In L. Eshelman, editor, Genetic Algorithms: Proceedings of the Sixth International Conference, pages 310--317, Pittsburgh, PA, USA, 15-19 1995. Morgan Kaufmann.
[12]
P. Nordin, F. Francone, and W. Banzhaf. Explicitly defined introns and destructive crossover in genetic programming. In J. P. Rosca, editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 6--22, 1995.
[13]
S. J. Russell and P. Norvig. Artificial Intelligence - A modern approach. Pearson Education, New Jersey, US, 2nd edition, 2003.
[14]
W. A. Tackett. Recombination, selection, and the genetic construction of computer programs. PhD thesis, University of Southern California, Los Angeles, CA, USA, 1994.
[15]
M. D. Terrio and M. I. Heywood. On naive crossover biases with reproduction for simple solutions to classification problems. In K. Deb, et al, editors, GECCO-2004, Part II, volume 3103 of LNCS, pages 678--689, Seattle, WA, USA, 2004. Springer-Verlag.

Cited By

View all
  • (2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
  • (2020)Fuzzy Control of Exploration and Exploitation Trade-Off with On-Line Convergence Rate Estimation in Evolutionary AlgorithmsArtificial Intelligence and Soft Computing10.1007/978-3-030-61401-0_42(454-463)Online publication date: 7-Oct-2020
  • (2018)Depth-control strategies for crossover in tree-based genetic programmingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-011-0700-915:9(1865-1878)Online publication date: 29-Dec-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation
July 2007
2313 pages
ISBN:9781595936974
DOI:10.1145/1276958
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. crossover
  2. genetic programming
  3. selection pressure
  4. stochastic elements

Qualifiers

  • Article

Conference

GECCO07
Sponsor:

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
  • (2020)Fuzzy Control of Exploration and Exploitation Trade-Off with On-Line Convergence Rate Estimation in Evolutionary AlgorithmsArtificial Intelligence and Soft Computing10.1007/978-3-030-61401-0_42(454-463)Online publication date: 7-Oct-2020
  • (2018)Depth-control strategies for crossover in tree-based genetic programmingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-011-0700-915:9(1865-1878)Online publication date: 29-Dec-2018
  • (2013)Parent Selection Pressure Auto-Tuning for Tournament Selection in Genetic ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.218265217:1(1-19)Online publication date: 1-Feb-2013
  • (2011)Genetic programming with a norm-referenced fitness functionProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001755(1323-1330)Online publication date: 12-Jul-2011
  • (2009)Approximating geometric crossover in semantic spaceProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570036(987-994)Online publication date: 8-Jul-2009
  • (2009)Balancing Parent and Offspring Selection in Genetic ProgrammingProceedings of the 22nd Australasian Joint Conference on Advances in Artificial Intelligence10.1007/978-3-642-10439-8_46(454-464)Online publication date: 17-Nov-2009
  • (2009)Evolutionary AlgorithmsAutomating the Design of Data Mining Algorithms10.1007/978-3-642-02541-9_3(47-84)Online publication date: 28-Oct-2009
  • (2008)An analysis of the distribution of swapped subtree sizes in tree-based genetic programming2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence)10.1109/CEC.2008.4631181(2859-2866)Online publication date: Jun-2008
  • (2008)A survey and taxonomy of performance improvement of canonical genetic programmingKnowledge and Information Systems10.1007/s10115-008-0184-921:1(1-39)Online publication date: 12-Dec-2008
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media