Section 4 shows the program space of the parity functions when given the appropriate functional building block. For all but the simpliest problems at all program lengths the fitness space is dominated by a central spike indicating almost all programs score exactly half marks. However a small fraction of programs do solve the parity problems. We have derived a simple analytical expression for the case of large programs which shows, the proportion of solutions falls exponentially with increasing number of inputs. However for modest, but realistic, numbers of inputs the proportion is not so small as to be infeasible to find using modern computers.
To derive a fitness landscape, we would also need to consider how genetic or other operators move between points in the search space, as well as the fitness of those points. However this is unneccessary in this case because either we have found a solution or the point in the search space scores half marks. That is the program space contains no gradient information. Search techniques, such as GP, which rely on gradient information will be unable to out-perform random search on such a landscape. Indeed we might anticipate population based search without mutation performing worse than random search as genetic drift in a small population means the population may loose one or more primitives. If this happended then it becomes impossible to construct a solution.
This suggests techniques which seak to solve the parity problems by evolving the appropriate building blocks are unlikely to find minimal solutions directly. Such evolutionary technqiues will probably have found programs with fitness well above half marks [Langdon and Poli1998a] and so will reject almost any solution only composed of the discovered building blocks since most of these will score less than the partial solutions it has already discovered. (It is possible impure solutions to the problem may be found which subsequent evolution, perhaps under the influence of parsimony or beauty pressures, may convert into a solution comprised only of building blocks).
When considering the Boolean problems it is common to require the inputs to be unstructured (a notable example gainfully employing typed inputs is [Janikow1996], while Yu structures her inputs as a list [Yu and Clark1998]). Our analysis shows it may not be enough to find functional building blocks without considering how they will act on the inputs.
If we compare Figure 1, with a similar plots for the artificial ant problem on the Santa Fe trail [Langdon and Poli1998b, Figure 2,] and plots for Boolean problems with other function sets [Langdon and Poli1998a] we see the proportion of programs which solve a particular problem or reach a given level of performance on the problem converges to a stable value which appears to be more-or-less independent of program size (provided we ignore lengths which syntactically cannot be solutions). We have demonstrated this property on the 256 3-input Boolean functions, 6 6-input Boolean functions as well as the ant problem. We expect this property to hold in many cases, however demonstrating it on 263 problems is not sufficient to prove it holds in general. However in Section 4 we proved it will hold in general for the special cases of the parity and always-on problems when given appropraite building blocks. These add weight to some of our claims about the nature of program fitness landscapes and their influence on the bloating phenomena [Langdon and Poli1997].
Random search using the ramped-half-and-half method of creating random trees [Koza1992, page 93,] is poor at finding solutions to these parity and always-on problems because it creates trees of many sizes. Most of these do not obey the restriction l=2n+4i-1 and so will score exactly half marks on these problems.