CONCLUSIONS

Average growth in program depth when using standard subtree crossover with standard random initial trees is near linear. The rate is about 1 level per generation but varies between problems. When combined with the known distribution of number of programs, this yields a prediction of sub-quadratic, rising to quadratic, growth in program size. There is considerable variation between runs but on the average we observe sub-quadratic growth in size. Which in a continuous domain problem, rises apparently towards a quadratic power law limit.

Discrete	$\mbox{mean length}$	$\mbox{O}(\mbox{generations}^{2.0})$
Continuous	$\lim_{g \rightarrow \infty} \mbox{mean length}$	$\mbox{O}(\mbox{generations}^{2.0})$

However in large discrete programs we observe a new type of genetic programming (GP) specific convergence: the whole population has the same fitness, even though its variety is 100%. This reduces the selection pressure on the population which, we suggest, is the reason why the growth remains sub-quadratic.

Most GP systems store each program separately and memory usage grows linearly with program size. I.e.  O(generations^1.2-2). Run time is typically dominated by program execution time, which is proportional to its length [Langdon1998b, D.8], therefore run time O(generations^2.2-3).

In other systems the whole population is stored in a directed acyclic graph (DAG) [Handley1994]. New links are created at a constant rate. However memory usage may be less than O(generations), since every generation programs are deleted. In the absence of side effects and with a fixed fitness function it may be possible to avoid re-evaluating unchanged code by caching intermediate values. I.e. only code from the crossover point to the root would be execute. Then run time should be proportional to the average height of trees. So run time $\mbox{O}(\mbox{generations}^{2})$.

Note we refer to standard sub-tree crossover, other genetic operators and/or representations have different bloat characteristics. For example [Nordin and Banzhaf1995] suggests program size increases exponentially with generations in his linear machine code representation and crossover operator. While new mutation [Langdon1998a] and crossover operators [Langdon2000] can reduce bloat in trees.

GP populations using standard sub-tree crossover (and no parsimony techniques) quickly reach bounds on size or depth commonly used. When this will happen can be readily estimated. We suggest such bounds may have unanticipated (but problem dependent) benefits.

To allow big programs (1,000,000 nodes) to evolve we were restricted to simple problems which and can be solved by small trees. However our results do raise the question of how effective subtree crossover will be on complex discrete problems whose solutions are big programs. It may also be the case that subtree crossover will cease to be effective (i.e. explorative, disruptive) if the program is structured as big trees. GP may need to limit tree size (perhaps by evolving programs compose of many smaller trees) and/or alternative genetic operators may be required.