Genetic Interface Programming

Evolution of Trees

Evolution of tree size and depth CUDA gzip matches kernel using BNF grammar based STGP. 
Grammar parse trees displayed as circular lattices.
1MB 101 frames
Evolution of tree size and depth CUDA gzip matches kernel using BNF grammar based STGP Cf. TR-10-02 Figures 15-19. Notice the population tends to lie near the random trees "peak" and that programs without children (blue) tend to be smaller than those with descendents. (red). 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 circular grid [Daida] with all <start> nodes placed at the origin (cf.  gp2lattice.awk.) 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 very 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.

Evolution of tree size and depth CUDA gzip matches kernel using BNF grammar based STGP. 
Grammar parse trees displayed as circular lattices.
1MB 101 frames run8.3
As above, on unsuccessful run.

Contact

CREST
Department of Computer Science,

9 Feb 2010 (Last update 14 Jan 2017)