@TechReport{langdon:1996:eGPpRN,
author = "W. B. Langdon",
title = "Evolution of Genetic Programming Populations",
institution = "University College London",
year = "1995",
type = "Research Note",
number = "RN/96/125",
address = "Gower Street, London WC1E 6BT, UK",
month = sep,
keywords = "Genetic Programming, Genetic Algorithms, population
variety, diversity, genetic programming, Price's
theorem, Fisher's theorem, evolution, automatic code
generation",
url = "ftp://ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/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 runs. 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 crossover. Section 6 discusses the
importance of these results to GP in general.",
notes = "Abridgement of Chapter 7 of langdon:thesis",
size = "48 pages",
}