- 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 generation",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.ecj.price.125.pdf",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/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 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 = "Abridgment of Chapter 7 of \cite{langdon:thesis}",
- size = "48 pages, double spaced",
