If we compare Figures 4, 5, 8, 9, 10 and 11 with a similar plot for the artificial ant problem on the Santa Fe trail [Langdon and Poli1998, Figure 2,] we see in all cases a certain minimum size is required before any solutions with a certain functionality exist, and that this threshold increases with the difficulty of the functionality. Once this threshold size is exceeded the proportion of programs grows rapidly to a stable value which appears to be more-or-less independent of program size. Conversely the proportion of the search space which implements easy functionality starts high and then falls with increasing program length, again converging to a stable value which is more-or-less independent of further increases in program length. We have demonstrated this property on the 256 3-input Boolean functions, 4 6-input Boolean functions as well as the ant problem. We expect this property to hold in many cases, however demonstrating it on 261 problems is not sufficient to prove it holds in general. But it does add experimental weight to some of our claims about the nature of program fitness landscapes and their influence on the bloating phenomena [Langdon and Poli1997].
On average half the random trees sampled using the ramped-half-and-half method [Koza1992, page 93,] are full. Therefore, particularly if the depth parameter is increased beyond the usual 6 (equivalent to maximum size of 63), the chances of finding at random both the even-3 and the odd-3 parity functions are considerably higher using it than using uniform search. In contrast ramped-half-and-half is less likely to find solutions to the Santa Fe ant trail problem than uniform search (see [Langdon and Poli1998, Table 3,]). This suggests that the best method to use to create the initial random population is problem dependent.
In [Koza1992, Chapter 9,] GP performance is shown not to be the same as random search. Indeed in the case of all but a few of the simplest problems which both GP and random search easily solve, GP performance is shown to be superior to random search. [Koza1992, Chapter 9,] treats in detail all the 256 Boolean functions with 3 bit inputs. (See also [Lang1995] and [Koza1995]). When [Koza1992, page 211,] compares the performance of GP with random search on these problems it explicitly assumes that programs of one length (41) are typical of the whole search space. In Section 3.1 we have verified this assumption. It should be noted that the subspaces consisting of short trees or full trees are not typical of the whole space. In particular full trees are much more likely to implement one of the parity functions than asymmetric trees which form most of the search space.