Grammatical Bias for Evolutionary Learning

Created by W.Langdon from gp-bibliography.bib Revision:1.4472

  author =       "Peter Alexander Whigham",
  title =        "Grammatical Bias for Evolutionary Learning",
  school =       "School of Computer Science, University College,
                 University of New South Wales, Australian Defence Force
  year =         "1996",
  address =      "Canberra, Australia",
  month =        "14 " # oct,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  URL =          "",
  size =         "172 pages",
  abstract =     "A framework for declarative bias, based on the genetic
                 programming paradigm (GP), is presented. The system,
                 CFG-GP, encapsulates background knowledge, inductive
                 bias and program structure. A context-free grammar is
                 used to create a population of programs, represented by
                 their corresponding derivation trees. These computer
                 programs evolve using the principle of Darwinian
                 selection. The grammar biases the form of language that
                 is expressible and the inductive hypotheses that are
                 generated. Using a formal grammar to define the space
                 of legal statements allows a declarative language bias
                 to be stated. The defined language may express
                 knowledge in the form of program structure and
                 incorporate explicit beliefs about the structure of
                 possible solutions. Additionally, the form of the
                 initial population of programs may be explicitly biased
                 using a merit selection operation. This
                 probabilistically biases particular statements
                 generated from the grammar.

                 The program induction system, CFG-GP, represents search
                 bias with three operators, namely selective crossover,
                 selective mutation and directed mutation. Each of these
                 operators allows a bias to be explicitly defined in
                 terms of how programs are modified and how the search
                 for a solution proceeds. Hence, both a search and
                 language bias are declaratively represented in an
                 evolutionary framework.

                 The use of a grammar to define language bias explicitly
                 separates this bias from the learning system. Hence,
                 the opportunity exists for the learning system to
                 modify this bias as an additional strategy for
                 learning. A general technique is described to modify
                 the initial grammar while the evolution for a solution
                 proceeds. Feedback between the evolving grammar and the
                 population of programs is shown to improve the
                 convergence of the learning system. The generalising
                 properties of the learnt grammar are demonstrated by
                 incrementally adapting a grammar for a class of

                 A theoretical framework, based on the schema theorem
                 for Genetic Algorithms (GA), is presented for CFG-GP.
                 The formal structure of a grammar allows a clear and
                 concise definition of a building block for a general
                 program. The result is shown to be a generalisation of
                 both fixed-length (GA) and variable-length (GP)
                 representations within the one framework.",

Genetic Programming entries for Peter Alexander Whigham