Genetic Interface Programming
Evolution of Trees
Evolution of tree size and depth
CUDA gzip matches kernel
using BNF grammar based STGP
TR-10-02 Figures 15-19.
Notice the population tends to lie near the random trees
and that programs without children (blue)
tend to be smaller than those with descendents.
Noise added to spread points.
Error bars show mean and one standard deviation.
The purple lines indicate the size and shape of binary trees.
90% of all binary trees lie between the 5% and 95% lines
[Foundations of GP].
Lower trace shows the distribution of binary tree sizes as histograms.
(Bin size ten. See right hand vertical scale.)
White is the whole population (total 1000).
Blue is the histogram for that
part of population whose
genes are not inherited by the next generation
(typically 500 programs).
The right hand plot shows the whole population of grammar trees as a
with all <start> nodes placed at the origin
The colour indicates the number of members of the population
which have the same tree branches
lying exactly on top of each other.
The circular lattice includes all of the grammar nodes not just
the binary choice nodes.
The circular lattice point makes it obvious that GP trees evolve to
asymmetric shapes and although there is some convergence
(the plot stress the root node)
the population never fixes on a particular shape
even when more than half the population have the same fitness
(generation 57 onwards).
Initial population (Generation 0) is created by ramped half-and-half
but quickly evolves to humped distribution with long tails.
As above, on unsuccessful run.
Department of Computer Science,
9 Feb 2010
(Last update 14 Jan 2017)