Scaling of Program Tree Fitness Spaces

We investigate the distribution of fitness of programs concentrating upon those represented as parse trees, particularly how such distributions scale with respect to changes in size of the programs. By using a combination of enumeration and Monte Carlo sampling on a large number of problems from three very different areas we are lead to suggest, in general, once some minimum size threshold has been exceeded, the distribution of performance is approximately independent of program length. We proof this for linear programs and for simple side effect free parse trees. We give the density of solutions to the parity problems in program trees composed of XOR building blocks. We have so far only conducted limited experiments with programs including side effects and iteration. These suggest a similar result may also hold for this wider class of programs