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

ORDERTREE: a new test problem for genetic programming

Published: 08 July 2006 Publication History

Abstract

In this paper, we describe a new test problem for genetic programming (GP), ORDERTREE. We argue that it is a natural analogue of ONEMAX, a popular GA test problem, and that it also avoids some of the known weaknesses of other benchmark problems for Genetic Programming. Through experiments, we show that the difficulty of the problem can be tuned not only by increasing the size of the problem, but also by increasing the non-linearity in the fitness structure.

References

[1]
Banzhaf, W.el al. Genetic Programming: An Introduction, Morgan Kaufmann, CA, 1998.
[2]
Burke E., Gustafson S., and Kendall G., A Puzzle to Challenge Genetic Programming, in Proceedings of the 5th European Conference in Genetic Programming, LNCS 2278, Spinger-Verlag, Berlin, 2002, 238--247.
[3]
Cramer, N. L. A Representation for the Adaptive Generation of Sequential Programs, Proceedings of an International Conference on GA and the Applications, 183--187, 1985.
[4]
Daida J.M. et al. What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines,2001, 165--191.
[5]
Daida J. M et al. What Makes a Problem GP-Hard? Validating a Hypothesis of Structure Causes, Proceedings of Genetic Algorithms and Evolutionary Computation Conference (GECCO2003), LNCS 2724, Springer-Verlag 2003,1665--1677.
[6]
Deb K. and Goldberg D. E. Analyzing Deception in Trap Functions, Foundations of Genetic Algorithms 2, Morgan Kaufmann, CA, 1993, 93--108.
[7]
Dejong, K. A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Doctoral Dissertation, University of Michigan, Ann Arbor. Michigan, 1975.
[8]
Gathercole C. and Ross P. An Adverse Interaction between Crossover and Restricted Tree Depth in Genetic Programming, in Proceedings of the First Annual Conference on GP, MIT Press, CA, 1996, 28--31.
[9]
Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, MA, 1989.
[10]
Goldberg, D. E. The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publisher, 2002.
[11]
Goldberg D. E. and O'Reilly U. M. Where Does the Good Stuff Go and Why?, In Proceedings of The First European Conference on Genetic Programming (EuroGP), Springer-Verlag, 1998.
[12]
Gustafson S. et al. Problem Difficulty and Code Growth in Genetic Programming, Genetic Programming and Evolvable Machines, 5, 2004, 271--290.
[13]
Koza J. R. Genetic Programming: On the Programming of Computers by Natural Selection, MIT Press, MA, 1992.
[14]
Koza J. R. Genetic Programming II: Automatic Discovery of Reusabe Programs, MIT Press, MA, 1994.
[15]
Langdon W. B. and Poli R. Foundations of Genetic Programming, Springer-Verlag, Berlin, 2002.
[16]
Mitchell M., Holland J. H., and Forrest S. When Will a Genetic Algorithm Outperform Hill Climbing?, In Advances in Neural Information Processing Systems 6, Morgan Kaufmann, CA, 1994.
[17]
Nguyen X. H. et al. Solving the Symbolic Regression Problem with Tree Adjunct Grammar Guided Genetic Programming: The Comparative Result, In Proceedings of Congress on Evolutionary Computation (CEC 2002), IEEE Press, 2002, 1326--1331.
[18]
O'Reilly U. M. and Goldberg D. E. How Fitness Structure Affects Subsolution Acquisition in Genetic Programming, in Proceedings of the Third Annual Conference on Genetic Programming, Morgan Kaufmann, 1998, 269--277.
[19]
Punch W. F., Zongker D., and Goodman E. D. The Royal Tree Problem, a Benchmark for Single and Multi-population Genetic Programming, in Advances in Genetic Programming 2, MIT Press, MA, 1996, 299--316.
[20]
Reeves C. R. and Rowe J. E. Genetic Algorithms: Principles and Perspectives, Kluwer Academic Publisher, 2003.
[21]
Sastry K., O'Reilly U. M., and Goldberg D. E. Population Sizing for Genetic Programming based on Decision Making, in Genetic Programming Theory and Practice II, Springer-Verlag, 2004, 49--65.
[22]
Schaffer J. D. and Eshelman L. J. On crossover as an evolutionary viable strategy. In Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, 1991, 61--68.
[23]
Schmidhuber, J. Evolutionary Principles in Self-Referential Learning, Diploma Thesis, Technische Universitat, Muchen, 1987.
[24]
Watson, R. A. Hornby G. S, and Pollack J. B. Modeling Building Blocks Dependency, in Parallel Problem-Solving from Nature 5, Springer-Verlag, Berlin, 97--106.

Cited By

View all
  • (2016)Modelling Evolvability in Genetic ProgrammingGenetic Programming10.1007/978-3-319-30668-1_14(215-229)Online publication date: 24-Mar-2016
  • (2015)Impact of Crossover Bias in Genetic ProgrammingProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754778(1079-1086)Online publication date: 11-Jul-2015
  • (2013)Better GP benchmarksGenetic Programming and Evolvable Machines10.1007/s10710-012-9177-214:1(3-29)Online publication date: 1-Mar-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation
July 2006
2004 pages
ISBN:1595931864
DOI:10.1145/1143997
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: 08 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. benchmark problems
  2. genetic programming
  3. problem difficulty

Qualifiers

  • Article

Conference

GECCO06
Sponsor:
GECCO06: Genetic and Evolutionary Computation Conference
July 8 - 12, 2006
Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2016)Modelling Evolvability in Genetic ProgrammingGenetic Programming10.1007/978-3-319-30668-1_14(215-229)Online publication date: 24-Mar-2016
  • (2015)Impact of Crossover Bias in Genetic ProgrammingProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754778(1079-1086)Online publication date: 11-Jul-2015
  • (2013)Better GP benchmarksGenetic Programming and Evolvable Machines10.1007/s10710-012-9177-214:1(3-29)Online publication date: 1-Mar-2013
  • (2011)On Synergistic Interactions Between Evolution, Development and Layered LearningIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.215075215:3(287-312)Online publication date: 1-Jun-2011

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