Evolution of Genetic Programming Populations

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

  author =       "W. B. Langdon",
  title =        "Evolution of Genetic Programming Populations",
  institution =  "University College London",
  year =         "1996",
  type =         "Research Note",
  number =       "RN/96/125",
  address =      "Gower Street, London WC1E 6BT, UK",
  month =        sep,
  keywords =     "genetic algorithms, genetic programming, population
                 variety, diversity, genetic programming, Price's
                 theorem, Fisher's theorem, evolution, automatic code
  URL =          "http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.ecj.price.125.pdf",
  URL =          "http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.ecj.price.125.ps.gz",
  abstract =     "We investigate in detail what happens as genetic
                 programming (GP) populations evolve. Since we shall use
                 the populations which showed GP can evolve stack data
                 structures as examples, we start in Section 1 by
                 briefly describing the stack experiment
                 \cite{Langdon:1995:GPdata}. In Section 2 we show
                 Price's Covariance and Selection Theorem can be applied
                 to Genetic Algorithms (GAs) and GP to predict changes
                 in gene frequencies. We follow the proof of the theorem
                 with experimental justification using the GP runs from
                 the stack problem. Section 3 briefly describes Fisher's
                 Fundamental Theorem of Natural Selection and shows in
                 its normal interpretation it does not apply to
                 practical GAs.

                 An analysis of the stack populations, in Section 4,
                 explains that the difficulty of the stack problem is
                 due to the presence of ``deceptive'' high scoring
                 partial solutions in the population. These cause a
                 negative correlation between necessary primitives and
                 fitness. As Price's Theorem predicts, the frequency of
                 necessary primitives falls, eventually leading to their
                 extinction and so to the impossibility of finding
                 solutions like those that are evolved in successful

                 Section 4 investigates the evolution of variety in GP
                 populations. Detailed measurements of the evolution of
                 variety in stack populations reveal loss of diversity
                 causing crossover to produce offspring which are copies
                 of their parents. Section 5 concludes with measurements
                 that show in the stack population crossover readily
                 produces improvements in performance initially but
                 later no improvements at all are made by

                 Section 6 discusses the importance of these results to
                 GP in general.

  notes =        "Abridgment of Chapter 7 of \cite{langdon:thesis}",
  size =         "48 pages, double spaced",

Genetic Programming entries for William B Langdon