- 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 Academy",
- year = "1996",
- address = "Canberra, Australia",
- month = "14 " # oct,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://divcom.otago.ac.nz/sirc/Peterw/Publications/thesis.zip",
-
URL = "https://dl.acm.org/citation.cfm?id=923829",
-
URL = "https://search.proquest.com/docview/304319299",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/whigham_1996_phd.pdf",
- 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 problems.
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.",
