Price's Theorem and the MAX Problem

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

  author =       "W. B. Langdon and R. Poli",
  title =        "Price's Theorem and the MAX Problem",
  institution =  "University of Birmingham, School of Computer Science",
  number =       "CSRP-97-4",
  month =        jan,
  year =         "1997",
  file =         "/1997/",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "",
  abstract =     "We present a detailed analysis of the evolution of GP
                 populations using the problem of finding a program
                 which returns the maximum possible value for a given
                 terminal and function set and a depth limit on the
                 program tree (known as the MAX problem). We confirm the
                 basic message of \cite{Gathercole:1996:aicrtd} that
                 crossover together with program size restrictions can
                 be responsible for premature convergence to a
                 sub-optimal solution. We show that this can happen even
                 when the population retains a high level of variety and
                 show that in many cases evolution from the sub-optimal
                 solution to the solution is possible if sufficient time
                 is allowed. In both cases theoretical models are
                 presented and compared with actual runs. Experimental
                 evidence is presented that Price's Covariance and
                 Selection Theorem can be applied to GP populations and
                 the practical effect of program size restrictions are
                 noted. Finally we show that covariance between gene
                 frequency and fitness in the first few generations can
                 be used to predict the course of GP runs.",

Genetic Programming entries for William B Langdon Riccardo Poli