Article

CGP visits the Santa Fe trail: effects of heuristics on GP

Authors:

Cezary Z. Janikow,

Christopher J. MannAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1697 - 1704

https://doi.org/10.1145/1068009.1068293

Published: 25 June 2005 Publication History

Get Access

Abstract

GP uses trees to represent chromosomes. The user defines the representation space by defining the set of functions and terminals to label the nodes in the trees, and GP searches the space. Previous research and experimentation show that the choice of the function/terminal set, choice of the initial population, and some other explicit and implicit "design" factors have great influence on both the quality and the speed of the evolution. Such heuristics are valuable simply because they improve GP's performance, or because they enforce some desired properties on the solutions. In this paper, we evaluate the effect of heuristics on GP solving the Santa Fe trail. We concentrate on improving the solution quality, but we also look at efficiency. Various heuristics are tried and mixed by hand, while evaluated with the help of the CGP system. Results show that some heuristics result in very substantial performance improvements, that complex heuristics are usually not decomposable, and that the heuristics generalize to apply to other similar problems, but the applicability reduces with the complexity of the heuristics and the dissimilarity of the new problem to the old one. We also compare such user-mixed heuristics with those generated by the ACGP system which automatically extracts heuristics improving GP performance.

References

[1]

Banzhaf, Wolfgang, Nordin, Peter, Keller, Robert E., and Francone, Frank D. Genetic Programming. Morgan Kaufmann 1998.

Digital Library

Google Scholar

[2]

Burke, Edmund, Gustafson, Steven, and Kendall, Graham. A survey and analysis of diversity measures in genetic programming. In Langdon, W., Cantu-Paz, E. Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Honavar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M., Schultz, A., Miller, J., Burke, E. and Jonoska, N., editors. GECCO2002: Proceedings of the Genetic and Evolutionary Computation Conference, 716--723, New York. Morgan Kaufmann.

Digital Library

Google Scholar

[3]

Daida, Jason, Hills, Adam, Ward, David, and Long, Stephen. Visualizing tree structures in genetic programming. In Cantu-Paz, E., Foster, J., Deb, K., Davis, D., Roy, R., O'Reilly, U., Beyer, H., Standish, R., Kendall, G., Wilson, S., Harman, M., Wegener, J., Dasgupta, D., Potter, M., Schultz, A., Dowsland, K., Jonoska, N., and Miller, J., editors, Genetic and Evolutionary Computation - GECCO-2003, volume 2724 of LNCS, 1652--1664, Chicago. Springer Verlag.

Digital Library

Google Scholar

[4]

Hall, John M. and Soule, Terence. Does Genetic Programming Inherently Adopt Structured Design Techniques? In O'Reilly, Una-May, Yu, Tina, and Riolo, Rick L., editors. Genetic Programming Theory and Practice (II). Springer, New York, NY, 2005, 159--174.

Google Scholar

[5]

Janikow, Cezary Z. A Methodology for Processing Problem Constraints in Genetic Programming. Computers and Mathematics with Applications, 32(8):97--113, 1996.

Google Scholar

[6]

Janikow, Cezary Z. and DeWeese, Scott. Processing Constraints in GP with CGP2.1. In Proceedings of the GP 1998 International Conference, 173--180.

Google Scholar

[7]

Janikow, Cezary Z. ACGP: Adaptable Constrained Genetic Programming. In O'Reilly, Una-May, Yu, Tina, and Riolo, Rick L., editors. Genetic Programming Theory and Practice (II). Springer, New York, NY, 2005, 191--206.

Google Scholar

[8]

Janikow, Cezary Z. CGP. http://www.cs.umsl.edu/~janikow/CGP.

Google Scholar

[9]

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

Digital Library

Google Scholar

[10]

Kuscu, Ibrahim. Evolving a Generalized Behavior: Artificial Ant Problem Revisited. In Porto, V.W., Saravanan, N., Waagen, D., and Eiben, A.E., editors, Evolutionary Programming VII 1998, pages 799--808, San Diego, California, Mar. 1998.

Digital Library

Google Scholar

[11]

Langon, William. Quadratic bloat in genetic programming. In Whitley, D., Goldberg, D., Cantu-Paz, E., Spector, L., Parmee, I., and Beyer, H-G., editors, Proceedings of the Genetic and Evolutionary Conference GECCO 2000, 451--458, Las Vegas. Morgan Kaufmann.

Google Scholar

[12]

McPhee, Nicholas F. and Hopper, Nicholas J. Analysis of genetic diversity through population history. In Banzhaf, W., Daida, J., Eiben, A. Garzon, M. Honavar, V., Jakiela, M. and Smith, R., editors Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, pages 1112--1120, Orlando, Florida, USA. Morgan Kaufmann.

Google Scholar

[13]

Montana, David J. Strongly Typed Genetic Programming. Evolutionary Computation, 3(2):199--230, 1995.

Digital Library

Google Scholar

[14]

Whigham, P. A. Grammatically-based Genetic Programming. In Rosca, Justinian P., editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 33--41, Tahoe City, California, 9 July 1995.

Google Scholar

Cited By

View all

Chivilikhin DUlyantsev VShalyto A(2013)Solving Five Instances of the Artificial Ant Problem with Ant Colony OptimizationIFAC Proceedings Volumes10.3182/20130619-3-RU-3018.0043646:9(1043-1048)Online publication date: 2013
https://doi.org/10.3182/20130619-3-RU-3018.00436
Janikow CAleshunas JHauschild MLanzi P(2011)Second order heuristics in ACGPProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002066(671-678)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002066
Ricalde EVázquez KBosman PYu TEkárt A(2007)A GP neutral function for the artificial ANT problemProceedings of the 9th annual conference companion on Genetic and evolutionary computation10.1145/1274000.1274026(2565-2571)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1274000.1274026
Show More Cited By

Index Terms

CGP visits the Santa Fe trail: effects of heuristics on GP
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
  2. Machine learning
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A genetic programming approach for solving the linear ordering problem
HAIS'12: Proceedings of the 7th international conference on Hybrid Artificial Intelligent Systems - Volume Part II

The linear ordering problem (LOP) consists in rearranging the rows and columns of a given square matrix such that the sum of the super-diagonal entries is as large as possible. The LOP has a significant number of important practical applications. In ...
Automated design of relocation rules for minimising energy consumption in the container relocation problem
Abstract
The container relocation problem (CRP) is a combinatorial optimisation problem in which the sequence of container relocations must be determined to retrieve all containers from the yard while optimising a given objective. Prior to now, the ...
Highlights
- Considering energy optimisation in container relocation problems.
- Automated design of relocation rules for energy optimisation.
- Automated design of rules for optimising energy and number of relocations.
- Genetic programming ...
Automatic Discovery of Optimisation Search Heuristics for Two Dimensional Strip Packing Using Genetic Programming
Simulated Evolution and Learning
Abstract
This paper presents a genetic programming based hyper-heuristic (GPHH) for automatic discovery of optimisation heuristics for the two dimensional strip packing problem (2D-SPP). The novelty of this method is to integrate both the construction and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
204
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

Chivilikhin DUlyantsev VShalyto A(2013)Solving Five Instances of the Artificial Ant Problem with Ant Colony OptimizationIFAC Proceedings Volumes10.3182/20130619-3-RU-3018.0043646:9(1043-1048)Online publication date: 2013
https://doi.org/10.3182/20130619-3-RU-3018.00436
Janikow CAleshunas JHauschild MLanzi P(2011)Second order heuristics in ACGPProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002066(671-678)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002066
Ricalde EVázquez KBosman PYu TEkárt A(2007)A GP neutral function for the artificial ANT problemProceedings of the 9th annual conference companion on Genetic and evolutionary computation10.1145/1274000.1274026(2565-2571)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1274000.1274026
Janikow CRothlauf F(2005)Adaptable representation in GPProceedings of the 7th annual workshop on Genetic and evolutionary computation10.1145/1102256.1102329(327-331)Online publication date: 25-Jun-2005
https://dl.acm.org/doi/10.1145/1102256.1102329

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A genetic programming approach for solving the linear ordering problem

Automated design of relocation rules for minimising energy consumption in the container relocation problem

Automatic Discovery of Optimisation Search Heuristics for Two Dimensional Strip Packing Using Genetic Programming