A new approach to evaluate GP schema in context

ABSTRACT

Evaluating GP schema in context is considered to be a complex, and, at times impossible, task. The tightly linked nodes of a GP tree is the main reason behind its complexity.This paper presents a new approach to evaluate GP schema in context. It is simple in its implementation with a potential to address well-known GP problems, such as identification of significant schema, dead code (introns) and module acquisition to name a few.It is based on the principle that the contribution of a schema can be evaluated by neutralizing the effect of the schema in the tree containing it (container-tree) and then checking its effect on the container-tree's fitness. Its usefulness is empirically demonstrated along with its limitation.

REFERENCES

• 1: Peter J. Angeline, Genetic programming and emergent intelligence, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 2: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 3: Una-May O'Reilly and Franz Oppacher. The troubling aspects of a building block hypothesis for genetic programming. In L. Darrell Whitley and Michael D. Vose, editors, Foundations of Genetic Algorithms 3, pages 73--88, Estes Park, Colorado, USA, 31 July--2 August 1994 1995. Morgan Kaufmann.
• 4: Riccardo Poli and W. B. Langdon. A new schema theory for genetic programming with one-point crossover and point mutation. Technical Report CSRP-97-3, School of Computer Science, The University of Birmingham, B15 2TT, UK, January 1997. Presented at GP-97.
• 5: Riccardo Poli and William B. Langdon. Schema theory for genetic programming with one-point crossover and point mutation. Evolutionary Computation, 6(3):231--252, 1998.
• 6: Justinian P. Rosca. Analysis of complexity drift in genetic programming. In John R. Koza, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max Garzon, Hitoshi Iba, and Rick L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 286--294, Stanford University, CA, USA, 13--16 July 1997. Morgan Kaufmann.
• 7: Justinian P. Rosca , Dana H. Ballard, Discovery of subroutines in genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.0 General

General Terms:
Algorithms, Theory

Keywords:
module acquisition, schema theory, tree semantics