Evolving problem heuristics with on-line ACGP

ABSTRACT

Genetic Programming 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. The sufficiency principle requires that the set be sufficient to label the desired solution trees, often forcing the user to enlarge the set, thus also enlarging the search space. Structure-preserving crossover, STGP, CGP, and CFG-based GP give the user the power to reduce the space by specifying rules for valid tree construction: types, syntax, and heuristics. However, in general the user may not be aware of the best representation space, including heuristics, to solve a particular problem. Recently, the ACGP methodology for extracting problem-specific heuristics, and thus for learning model of the problem domain, was introduced with preliminary off-line results. This paper overviews ACGP, pointing out its strength and limitations in the off-line mode. It then introduces a new on-line model, for learning while solving a problem, illustrated with experiments involving the multiplexer and the Santa Fe trail.

REFERENCES

• 1: Banzhaf, Wolfgang, Nordin, Peter, Keller, Robert E., and Francone, Frank D. Genetic Programming. Morgan Kaufmann 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. 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.
• 7: Janikow, Cezary Z. Adapting Representation in Genetic Programming. In K. Deb et al. editors. Proceedings of Genetic and Evolutionary Computation Conference: GECCO 2004, 507--518.
• 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: 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.
• 11: 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.
• 12: Montana, David J. Strongly Typed Genetic Programming. Evolutionary Computation, 3(2):199--230, 1995.
• 13: Pelikan, Martin and Goldberg, David. Boa: The Bayesian Optimization Algorithm. In Banzhaf, Wolfgang, Daida, Jason, Eiben, Agoston E., Garzon, Max H., Honavar, Vasant, Jakiela, Mark, and Smith, Robert E., editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 1, pages 525--532, Orlando, Florida, USA, 13--17 July 1999. Morgan Kaufmann.
• 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:
genetic programming, heuristics, machine learning