Sub-Symbolic Representation and Search Operators for Genetic Programming

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

  author =       "Jonathan Page",
  title =        "Sub-Symbolic Representation and Search Operators for
                 Genetic Programming",
  school =       "School of Computer Science, The University of
  year =         "1999",
  address =      "B29 15TT, UK",
  month =        dec,
  email =        ",",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  size =         "226 pages",
  abstract =     "Genetic Programming (GP) is one of the more recent
                 additions to a diverse body of biologically-inspired
                 search techniques known as evolutionary algorithms
                 (EAs). GP differs from most other EAs in that candidate
                 solutions are executable programs of arbitrary size
                 which are evaluated according to how well they perform
                 on a specified task. Whilst GP has been successfully
                 applied to a number of problem domains, there remain
                 many tasks on which performance is notably poor.

                 This thesis argues that poor performance is, in many
                 cases, due to the nature of the search that GP's
                 operators perform. GP's primary operator, crossover,
                 has been shown to perform a predominantly local search
                 of the program space, and this can make global optima
                 difficult to locate if the fitness landscape is
                 characterised by long stretches of very weak or neutral
                 fitness gradients.

                 Recently, a GP search operator that performs global
                 search has been proposed. This operator is known as GP
                 uniform crossover, and in this thesis we test it
                 extensively on a number of benchmark problems. We also
                 propose a novel sub-symbolic representation for
                 function which can be used in conjunction with GP
                 uniform crossover, and which accords GP the additional
                 ability to perform a very local, directed search of the
                 program space.

                 The experiments reported in this thesis raise a number
                 of issues that are discussed in detail. The
                 sub-symbolic representation, as used here, constrains
                 the size of the function set and in many cases this is
                 significantly larger than those used in most GP
                 implementations. Despite of this, we report enhanced
                 performance on a number of problems and this leads us
                 to question the received wisdom which states that the
                 recommends a minimalist approach to function set
                 design. The use of different operators and
                 representations transforms the search space and
                 highlights a number of properties of GP program spaces
                 that have so far been overlooked. We discuss these and,
                 in the light of our findings, reevaluate some of the
                 hypotheses that have been put forward concerning the
                 program spaces of some well-known functions. The search
                 operators used here also constrain the complexity of
                 the programs that may be evolved. We examine the
                 advantages of this, particularly with respect to
                 controlling program size and resultant run-time, and
                 the disadvantages.

                 The issues arising from these studies are diverse and
                 many have received little attention in the literature.
                 We believe that the findings reported here pose
                 numerous questions, and we suggest several directions
                 for future research.",

Genetic Programming entries for Jonathan Page