A Schema Theorem for context-free grammars
Peter A. Whigham · 2002
The basic Schema Theorem for genetic algorithms is modified for a grammatically-based learning system. A context-free grammar is used to define a language in which each sentence is mapped to a fitness value. The derivation trees associated with these sentences are used to define the structure of schemata. The effect of crossover and mutation on schemata is described. A schema theorem is developed which describes how sentences of a language are propagated during evolution. 1. Introduction The Schema Theorem for genetic algorithms (GA) [3] defines how useful structures in a population of strings are propagated during the evolution of a solution. It gives a lower bound on the propagation of schemata from one generation to the next. A GA uses a fitness function to evaluate the population, and the genetic operations of crossover and mutation to search for new strings. The fixed-length nature of GA's has been extended with genetic programming (GP) [4], which uses a tree-based representati...