Why Ants are Previous: The Artificial Ant

Size of Program and Solution Space

The number of different programs of a specific length is given by the size of the terminal set and the numbers of different functions in the function set of each arity (branching factor). To create a tree of a specific length a corresponding number of functions of each branching factor and number of leafs must be used. Where there are more than one branching factor available in the function set, there may be multiple combinations of function arity which give rise to a tree of the required size. In general there are multiple ways of arranging the branches and leafs. Each way gives rise to a distinct tree shape. Finally, where there are more than one terminal or more than one function of a given arity, there are multiple programs of the same shape. The number of different programs in the ant problem is plotted against their lengths in Figure 1 (and is tabulated in the ``Total'' row at the bottom of Table 2). As expected the number of programs grows approximately exponentially with the length of the programs. (The program used to calculate the number of programs is available via anonymous ftp from ftp.cs.bham.ac.uk in pub/authors/W.B.Langdon/gp-code/ntrees.cc).

For the shorter programs it is feasible to explore the program space exhaustively. Table 2 summarises the programs space up to programs of length 14. Table 2 shows the program space is highly asymmetric with almost all programs having very low scores and the proportion with higher scores falling rapidly (but not monotonically) to a low point near 72. Above 72 it rises slightly. The modal score is zero, the median is one and the mean rises with length from 1 to 2.7 while the standard deviation remains near 4 (cf. Figure 7). There is some dependence upon program length and, as expected, programs must be above a minimum size to reach modest scores. However above the minimum size the number of programs with a given score rises rapidly, being a roughly constant proportion of the total number of programs. There are an unexpectedly high number of solutions (albeit a tiny fraction of the total) and their number similarly grows with program size.

For longer programs exhaustive search is not feasible and instead we sampled the program space randomly in a series of Monte Carlo trials for a number of program sizes. For each such size between 10,000,000 random programs where generated and tested. The random programs where chosen uniformly from the set of possible programs of the specific length using the bijective random tree creation algorithm described in [Alonso and Schott1995, Chapter 4,].

Where there are multiple different combinations of function arity which give rise to trees of the required size, one was chosen at random in proportion to the number of trees it contains. Each tree was converted to a program by labelling each of its nodes with a function or terminal of the correct arity chosen uniformly at random from those that match in the function or terminal set. In this way we ensure every program of the specified length has the same chance of being chosen.

 
Figure 1:   Number of programs of a specific length (note log log scale)

Number of Trees and Distribution of Fitness

 
Figure 2:   Proportion of programs of a given length by their fitness. Values for lengths 15 and above are based on Monte Carlo sampling.

 
Figure 3:   Proportion of programs of a given length which are solutions. Error bars indicate standard error on Monte Carlo estimates.

Figure 2 shows that the proportion of programs with a given score is approximately constant for a wide range of program lengths. Since the total number of programs rises rapidly, this means the number of programs with a given score also rises rapidly with length. This confirms assumptions in [Langdon and Poli1997a].

With any Monte Carlo technique there will be some stochastic error in the estimates. In the case of rare events (such as finding a solution to the ant problem) this could be large. The stochastic error was kept reasonable by using a large number of trials so a modest number of solutions were found at each length (between 9 and 101 and on average 39).

An estimate of the stochastic error is plotted in Figure 3 using error bars.

Why Ants are Previous: The Artificial Ant