The Boolean functions have often been used as benchmark problems.
The program trees we will consider are composed of n terminals (D0, D1, ... D) which are the Boolean inputs to the program and the Boolean logic functions AND, OR, NAND and NOR [Koza1992]. These are sufficient to construct any Boolean function but we shall also investigate including the exclusive-or function (XOR). Note [Koza1992] required all the functions to have the same arity, this is not required in our approach. The fitness of each tree is given by evaluating it as a logical expression for each of the possible combinations of D inputs. Its fitness is the number of fitness cases when its output agrees with that of the target Boolean function.
There are different trees of length l [Koza1992, page 213,] [Alonso and Schott1995]. |F| is four (or five if XOR is included). (Note this formula is simple as each function (internal node) has two arguments). The number of programs rises rapidly (approximately exponentially) with increasing program length l (see Figures 1 and 2). Of course if no bounds are placed on the size or depth of programs then the number of them is unbounded, i.e. the search space is infinite.
Figure 1: Size of 3-Input Boolean Function Search Spaces (note log log scale)
Figure 2: Size of 6-Input Boolean Function Search Spaces (note log log scale)