Our investigations of the artificial ant following the Santa Fe trail [Langdon and Poli1998] suggests that, provided programs are big enough, the distribution of program fitnesses is roughly independent of their size. That is if we pick a program of a certain length at random its as likely to perform as well as another program of a different length also chosen at random (provided both exceed some threshold size). If this is generally true then as the size of the search space grows approximately exponentially as we allow longer programs then so to does the number of programs with a certain level of performance. Therefore while a search space with no size or depth limits will be infinite it will contain an infinite number of solutions!
We test this result from the Ant problem on a range of other problems. In Section 2 we describe the Boolean problems. Section 3 describes how we measure the performance spaces of these problems and gives our results. The ramped-half-and-half method [Koza1992, page 93,] is commonly used to generate the initial population in genetic programming (GP). Half the random programs generated by it are full. Therefore we also explicitly consider the subspace of full trees. This is followed by a discussion of these results and their implications (Section 4) and our conclusions (Section 5). Finally in Appendix A we consider using the Boolean functions to experimentally test the No Free Lunch theorems and give reasons to reject this idea.