Evolving Program defined by a Formal Grammar

摘要

Many problems of symbolic induction may be defined as the search for a structure or sentence whose possible representations are constrained in some way. The use of a formal grammar to define legal sentences (programs) of a language has been studied and formalised for many years. This paper describes the use of a formal grammar to generate and maintain the structure of sentences for a context-free language, based on the Genetic Programming paradigm. A population of initially random programs are transformed to new senstences using a crossover and mutation operator, where seletion of individuals is based on a proportional fitness measure. The use of a grammar to represent the search space also allows explicit language and search bias to be defined.