A Schema Theorem for context-free grammars

Abstract

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.