DISTRIBUTION OF FITNESSES

Provided programs are bigger than some problem and fitness level dependent threshold, the distribution of their fitness values in the GP search space does not change with length []. Figure 1 shows an example distribution of fitness against size. Note as size increases the lines tend to lie parallel to the y-axis, indicating little dependence upon size. Thus the number of programs with a given fitness is distributed like the total number of programs. The number of programs rises approximately exponentially with program length. Also most programs have a maximum depth near   $2\protect\sqrt{\pi \mbox{(internal nodes)}}$(ignoring terms O(N^1/4) [Flajolet and Oldyzko1982]. See dashed parabola line on Figure 2.

Figure: 2 Distribution of binary trees by size and maximum depth. Solid line and error bars indicate the mean and standard deviation of the depth for trees of a give size. The dashed line is the large tree limit for the mean, i.e.  $2\protect\sqrt{\pi \mbox{(internal nodes)}}$. The full tree and minimal tree limits are shown with dotted lines, as are the most likely shape (peak) and the 5% and 95% limits (which enclose 90% of all programs of a given size).