Towards scalable genetic programming

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

  author =       "Steffen Moffatt Christensen",
  title =        "Towards scalable genetic programming",
  year =         "2007",
  school =       "Carleton University",
  address =      "Ottawa, Canada",
  month =        "14 " # nov,
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  URL =          "",
  isbn13 =       "978-0-494-23290-3",
  order_no =     "AAINR23290",
  size =         "282 pages",
  abstract =     "Genetic programming (GP) is a technique for
                 automatically solving optimisation problems where
                 candidate solutions are expressible as trees with no
                 human intervention. We propose an extension of GP,
                 termed scalable genetic programming, which solves
                 problems parametrised by a scalable difficulty
                 parameter. We first define a taxonomy of evolutionary
                 computation (EC) systems that identifies variability
                 dimensions and levels for EC systems. We define an
                 algorithm, the scientist algorithm, which uses genetic
                 programming as a subroutine to reliably make progress
                 on scalable problems. The scientist algorithm uses a
                 toolkit of provided routines to progress, by carrying
                 out experiments to determine the value of different
                 methods. We define several of the tools for this
                 toolkit. We define and implement an algorithm for
                 systematically considering all small trees for a
                 problem. We then use these small trees in an iterative
                 algorithm to define subroutines that improve
                 performance on a problem under study. Using this
                 algorithm, we beat the best known performance on the
                 artificial ant on the Santa Fe trail problem by a
                 factor of 7.

                 As science depends on accurate hypothesis testing to
                 make progress, we perform a comparison and evaluation
                 of statistical techniques used to evaluate evolutionary
                 computation systems. Finding many of these wanting,
                 with the exception of computational effort, we
                 introduce two additional techniques, effective mean
                 best fitness and the y-test. We also perform an
                 extensive analysis of the computational effort, and
                 identify some statistical cautions around the use of
                 this key statistic. We provide an algorithm that
                 carefully uses computational effort to determine the
                 best values of population size and generation number
                 for an EC treatment.

                 Finally, we identify several components that are of use
                 with the scientist algorithm. We treat the use of
                 multiobjective algorithms in GP, principal components
                 analysis, and their combination. We demonstrate this by
                 providing and testing an algorithm that makes evolved
                 trees parsimonious. We introduce the notion of
                 incremental evolution, and use it to make useful
                 subroutines automatically from successful solutions to
                 easy problems. We then use this to demonstrate scalable
                 genetic programming on an integer sorting problem.",
  notes =        "
                 Tuesday, Jan. 30, 2007 Also known as


                 supervisor Franz Oppacher",

Genetic Programming entries for Steffen Christensen