next up previous
Next: About this document ...

Code Growth in GP and other Stochastic Search Techniques
W. B. Langdon SEN 4
CENTRUM VOOR WISKUNDE EN INFORMATICA, KRUISLAAN 413, NL-1098 SJ AMSTERDAM,



Introduction

Background - Genetic Programming

Background - Program Growth in GP

Sextic Polynomial, Best of Initial Population

Ramped-half-and-half (2:6) Length 11, Depth 4, Fitness 0.043511, Hits 6, constant value, First run

Sextic Polynomial, First Solution

Length 173, Depth 21, Fitness 0.00432659, Hits 50, generation 37

Sextic Polynomial, Best of Pop, End of run

Length 383, Depth 24, Fitness 0.0029695, Hits 50

Program Growth in GP

What is known about space of all programs

Number of programs v. size, Sextic Polynomial
\psfig{figure=polyspace.size.eps}

Distribution of Binary Trees by size and height
\psfig{height=0.8\textheight,figure=shape.eps}

Distribution of Binary Trees by size and height
\psfig{height=0.8\textheight,figure=ntreeshape.eps}

What is wrongly assumed about space of all programs

New measurements and conjectures about programs spaces

Proportion of Ant programs with each score

\psfig{width=\textwidth,figure=montecarlo.eps}

Error Distribution Sextic Polynomial Problem

\psfig{width=\textwidth,figure=montepoly.fit.eps}

Distribution of 3 bit Boolean Functions

\psfig{width=\textwidth,figure=uniform.freq.eps}

Distribution of 3 bit Boolean Functions with XOR

\psfig{width=\textwidth,figure=uni.xor.freq.eps}

Hits on 6 Inputs All-1s Problem

\psfig{width=\textwidth,figure=ones6.eps}

Even-6 parity program space

\psfig{width=\textwidth,figure=even6.eps}

Hits on 6 Inputs All-1s, XOR included

\psfig{width=\textwidth,figure=ones6.xor.eps}

Even-6 parity program space, including XOR

\psfig{width=\textwidth,figure=even6.xor.eps}

Implications

Two Mechanisms for Bloat

1.
Longer programs are more resilient to change. They are more likely to produce children as fit as they are.

2.
Small changes to existing code is less likely to disrupt it. However there is no counterbalancing size effect on adding code. So fit children either result from small removals of code and small additions or small removals and large additions. Together this means fit children are on average bigger than their parents.

Random Walk, Maximising Entropy Model of Bloat

One general cause, although counter examples can be constructed

1.
Practical search techniques start with short candidate solutions

2.
they search the neighbourhood of good solutions

3.
It is easy to make improvements initially

4.
As the best-so-far improves, further improvements become harder

5.
I.e. they get stuck and may execute a random walk amongst solutions as good as those they have found so far.

6.
There are many more (exponentially more) long programs of this fitness than short ones.

7.
Thus a random walk is over time far more likely to increase program size than decrease it.

Bloat is inherent in variable length search not just GP.

Predications

Evolution of shape

Evolution of Shape: 6 Problems
\psfig{height=0.8\textheight,figure=shape_6plots.eps}

Conclusions

Bloat, Fair v. Standard Crossover
\psfig{height=0.8\textheight,figure=polyp50xo.length.eps}

Evolution of shape, Fair v. Standard Crossover
\psfig{height=0.8\textheight,figure=polyp50xo.depth.eps}



 
next up previous
Next: About this document ...
Bill Langdon
1999-03-03