Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: Proceedings of the First European Workshop on Genetic Programming, April 1998
• 2: Raymond Burke , Steven Gustafson , Graham Kendall, A Survey And Analysis Of Diversity Measures In Genetic Programming, Proceedings of the Genetic and Evolutionary Computation Conference, p.716-723, July 09-13, 2002
• 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.
• 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.
• 5: Janikow, Cezary Z. A Methodology for Processing Problem Constraints in Genetic Programming. Computers and Mathematics with Applications, 32(8):97--113, 1996.
• 6: Janikow, Cezary Z. and DeWeese, Scott. Processing Constraints in GP with CGP2.1. In Proceedings of the GP 1998 International Conference, 173--180.
• 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.
• 8: Janikow, Cezary Z. CGP. http://www.cs.umsl.edu/~janikow/CGP.
• 9: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 10: Ibrahim Kuscu, Evolving a Generalized Behaviour: Artificial Ant Problem Revisited, Proceedings of the 7th International Conference on Evolutionary Programming VII, p.799-808, March 25-27, 1998
• 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.
• 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.
• 13: Montana, David J. Strongly Typed Genetic Programming. Evolutionary Computation, 3(2):199--230, 1995.
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Design, Experimentation

Keywords:
evolutionary computation, genetic programming, heuristics