The Boolean parity functions have been over used as benchmark problems in GP. Investigations are usually empirical and often contain little analysis. The benchmarks are considered difficult, with the standard function set only the smaller versions of the problem can be solved by random search [Langdon and Poli1998a]. Perhaps their difficulty arises because the standard representation does not allow the ready discovery and use of building blocks? A number of techniques (ADF [Koza1994], ARL [Rosca1997], GLiB [Angeline1993]) have been suggested that aim to ease the discovery and use of building blocks. We assume some such approach has been successful at evolving functional building blocks and analyse the fitness space given a function set which comprises only this building block.
In Section 2 we describe the Boolean functions and give an expression for the number of them which can be constructed with one binary function. The form of the solutions and the building block used are given in Section 3 and in Section 4 we analyse the problem and derive a limit for the density of solutions. This is followed, in Section 5, by a discussion of the significance of this result and by our conclusions (Section 6).