2.1 NK Landscapes

Specifying an NK landscape requires the following parameters:

N - the total number of bits (genes).

K - the amount of epistasis. Each bit depends on K other bits to determine that its fitness contribution. We will call the K + 1 bits involved in each contribution a subfunction.

b_i - N (possibly random) bit masks (i = 1, 2, 3…, N). Each bit mask is of length N, and contains K + 1 ones. The 1 s in a bit mask indicate the bits in an individual that are used to determine the value of the ith subfunction.

Given these parameters, one can construct a random NK landscapes as follows:

A. Construct an N by 2^K + 1 table, X.

B. Fill X with random numbers, typically from a standard uniform distribution.

Given the table X, and the bit masks, one determines the fitness of an individual as follows:

C. For each bit mask b_i, select out the substring of the individual that correspond with the K + 1 one-valued bits in that bit mask.

D. Decode these bits into their decimal integer equivalent j.

E. Add the entry X(i, j) to the overall fitness function value for this individual.

Note that the fitness values are typically normalized by dividing by N.

A typical set of bit masks for this type of problem consists of all N bit masks that have K + 1 consecutive ones. In this case the string is treated as a circle, so that the consecutive 1 bits wrap around. This set of bit masks outlines a function where any given bit depends on the K preceding bits to determine its contribution to fitness. However, bit masks are sometimes used such that b_i has the ith bit set to one, but the remaining K one-valued bits are selected at random. Some other possibilities are discussed in [2].

2.2 NKP Landscapes

Altenberg [1, 2], and later Heckendorn and Whitley [4], allude to a set of landscapes that we will call the NKP landscapes. If one uses an analogy to the NK landscapes, specifying an NKP landscape requires the same parameters as the NK landscapes, with one addition:

P - the number of subfunctions (each assumed to be of epistasis K, for this discussion) that contribute to the overall fitness function. This discussion also assumes that the P subfunctions are simply summed to determine overall fitness. Each subfunction is associated with a bit mask (also called a partition) b_i. Note that, for coverage of the space of all K epistatic functions

$0\le P\le \left(\begin{array}{c}\hfill N\hfill \\ \hfill \left(K+1\right)\hfill \end{array}\right).$

Moreover, this means that one must specify P bit masks, rather than only N. This means that table X must be extended to be P by 2^K + 1. Otherwise, the construction and decoding procedure is the same as that for NK landscapes.

3.1 Juxtapositional Complexity Considerations

A previous paper [10] defined a yardstick for juxtapositional complexity, called misleadingness. Specifically, it defined the probability of n^thorder misleadingness, to be the probability that, when one considers all building blocks of n bits or less, the compliment of the optimum appears as fit or more fit than the optimum itself. Although misleadingness is a less strict phenomenon than deception [3], it is related, and it yields a calculable measure of juxtapostional complexity in the randomly generated landscapes we consider here.

3.2 Observations

Examinations of NKP landscapes [10] (of which NK landscapes are a subset, with P = N), revealed the following with regard to peak distribution characteristics:

• The parameter P has little effect on the most critical of these characteristics.

• However, P acts as a “gain factor” on the landscape’s expected range of fitness values.

• Moreover, P seems more responsible than K for the so-called complexity catastrophe in these landscapes.

A more general observation is that K is an overly sensitive control on peak distribution complexity. That is, for values of K much larger than 3, landscapes become intractable. It is worth considering that since this analysis was based on exhaustive searches, landscapes with N > 20 were not considered, and it is possible that the critical value of K is related to N, perhaps in a logarithmic fashion

With regard to juxtapositional characteristics, the following is observed:

• The expected juxtapositional complexity (that is, the complexity of the building block structure) of landscapes generated by the NKP procedure is limited.

• P seems to have little effect on changing the juxtapositional characteristics of landscapes generated by the NKP procedure.

Finally, [10] suggests that it may be possible to directly manipulate Walsh coefficient statistics, and thus develop random landscapes with more desirable and controllable juxtapositional characteristics. Previous work [10] did not speculate about the effects of such manipulation on peak distribution characteristics. The following section introduces the general notion of Walsh-based landscapes, in a form analogous to NKP landscapes, and later sections introduce a particular form of generator based on this idea.

8.1 Peak Distribution Characteristics

In order to evaluate the properties of NKPSR landscapes, a number of landscapes were created for each of a set of combinations of parameter values. For landscapes of size N = 12,14,16,18 and 20, 10 landscapes were created for each of the valid combinations of the following parameters:

K = {2, 4, 6, 8, }

P = {4, 8, 16, 32, 64}

R = (-0.81, -0.2, 0.0, 0.2, 0.81}

S = {0.01, 0.1, 1.0}

Each landscape was exhaustively probed in order to discover the location and value of all the optima (both local and global), and the following values were then calculated for each landscape:

• Maximum, minimum, mean and standard deviation of fitness,

• Mean and standard deviation of optima fitness,

• Number of optima, mean and standard deviation of distance of optima from the global optimum,

• Correlation between relative fitness of local optima and distance from the global optimum.

The results were subjected to a one-way analysis of variance (ANOVA) for the factors N, K, P, R and S, and to tests for linearity. The results are summarized in Table 2. Where the ANOVA tests indicate statistical significance at the 1% level, the ε² value (a measure of the proportion of the variance in the measured value that can be attributed to the factor) is given where the factor accounts for more than 1% of the observed variance. Particularly meaningful values are shown in bold, and a hyphen indicates that the ε² value is less than 5% although the ANOVA results show that the factor is significant. In all cases, NSS indicates no statistical significance. Where a factor appears to be a major determinant in the value of the variable, and tests suggest a significant linearity between the values of the factor and the observations, the correlation co-efficient is shown in braces.

The analysis shows that the factor R is not statistically significant for the distance related measures, and never accounts for more than 2% of the observed variance in the fitness related measures, and so this column is omitted for clarity.

From these results we can observe that as with the NKP landscapes, the dominant factors affecting these coarse peak distribution statistics are N, K and P.

Previously reported analysis on NKP landscapes [10] showed that the major effect of P was as a kind of “gain control”, altering the spread of fitness values present in the landscape but not affecting the location of peaks. This is a secondary effect arising from the fact that if partitions overlap it is not possible to simultaneously optimise them all, and as the number of partitions increases so do the number of partitions with sub optimal values in optima. This effect can be seen again in these results, and there is an additional affect that P now accounts for over 10% in the observed variance in the number of peaks, the number reducing as P is increased.

Unlike the NKP landscapes, the value of K now has a significant effect on the range of fitness values present, with both the range of fitness value, and the mean fitness of local optima increasing with K. This can be explained by the fact that as K increases, so the number of low order Walsh coefficients within each partition increases, with a corresponding increase in the variance of the normal distribution from which the high order coefficient is drawn.

As K increases, the mean distance of local optima from the global optimum, the mean and standard deviation of their fitnesses (relative to that of the global optimum), and the positive correlation between fitness and distance from the global optimum all increase, reflecting the pattern observed by Kauffman of a “massif central” present at low K but disappearing as the K increases.

The significant (i.e. ε² > 1%) effects of S as it increases from 0.01 to 1.0, (i.e the high order co-efficients become less important) are:

• the mean distance of local optima from the global decreases

• the correlation between their fitness and that distance becomes more negative

• the standard deviations of both fitness and distances increases.

The first two observations can be understood when it is considered that the scale factor S stochastically affects whether the high order co-efficient outweighs the effect of the low order values in determining the location of the global optimum: S approaches 1.0 there is less chance of creating a misleading landscape.

The effects of S on the peak distribution characteristics are more clear when a single set of values are considered for N,K and P, for example the correlation values for N = P = 16, K = 2 with R = − 0.81 are − 0.2278 for S = 0.01 and − 0.5520 for S = 1.0.

However when N,K,P and S are fixed, the effects of changing R are not statistically significant, suggesting that these peak distribution characteristics are perhaps too coarse to detect the effects of a single deceptive global optimum

In conclusion it would appear that in terms of the peak distribution metrics, the characteristics of the NKPRS landscapes are broadly similar to those of the NKP landscapes, and are largely determined by K, with secondary effects due to S as noted. These metrics are based on measuring distance in Hamming space, which more closely reflects search conducted by “bit-flipping” hill climbers and mutational operators.

8.2 Juxtapositional Characteristics

To evaluate the effects of the various parameters of NKPSR landscapes on juxtapositional complexity, 40 landscapes were generated for a number of combinations of these parameters, and the results were used to calculate the probability of misleadingness, as discussed in Section 5. Typical results of this exploration are shown in Figure 2 through Figure 5.

Note that, as one would expect, the complexity of the landscape increases with negative R. P also has a noticeable effect. Complexity also increases with decreasing S, as one would expect.

8.3 GA Performance

The previous sections show that over the space of possible landscapes of a given size N, one would expect K and S to have the most effect of peak distribution, while K, S, and R should have effects on juxtapositional complexity. Whether these effects result in actual complexity for the GA remains to be established. To examine this issue, we applied a relatively simple GA to a selection of problems constructed with this generator.

The GA used a population of 100 binary individuals, with uniform crossover, applied with probability one, point mutation applied with probability 0.05, and tournament selection. This GA was in no way optimised for these problems, since we simply wished to illustrate variations in GA performance over the space of landscapes generated. For each set of generator settings, the GA was run 100 times: 10 random restarts on 10 separate landscapes.

In each landscape, we exhaustively located the optimum, and ran the GA until it either found this point, or completed 300 generations. We recorded the number of GA runs that located the optimum, and the number of generations to find the optimum in those cases.

Figure 6 shows the results of the GA for N = 15, K = 2, and P = 15. Note that this yields 3-bit interactions, and the number of partitions typical in NK landscapes. As expected, this figure shows increasing difficulty for the GA as S becomes smaller and R becomes more negative. However, note that for large values of S (where problems are relatively easy for the GA), distinctions in R become less important.

Similar results are seen by observing the number of generations needed to locate the optimum, for the runs where the optimum is found (see Figure 7).

However, it is interesting to note that the pattern shifts for higher levels of epistasis. Consider the results for K = 4 and P = 15, shown in Figure 8 and Figure 9. Note that in Figure 8 the S axis is shown in reverse order (relative to previous plots) for clarity. As one would expect, these problems, which have higher order Walsh coefficients, become more difficult for the GA to solve. However, at this level of epistasis, it seems that the effect of S (scale) is reversed. High S yields problems that are more difficult for the GA, in terms of actually finding the optimum. This runs counter to the intuition of our previous analysis. However, note that Figure 9 generally shows the familiar pattern predicted by our analysis. Apparently, the effects of Walsh coefficient scale change, in some way that is unexplained by our current analysis. For such landscapes, the optimum becomes more difficult for the GA to discover with higher S. The effects of R are less clear, although the seem to follow the pattern predicted by analysis for intermediate values of R, shown in Figure 8. However, when the optimum is found by the GA, the number of generations increases with lower S, as our analysis would suggest.

It is also interesting to examine patterns of performance with respect to S and R for low values of P. These problems are generally easy for the GA. For instance, consider results for K = 4 and P = 5 shown in Figure 10 and Figure 11. There is still some pattern of declining difficulty with increasing S and more negative R, particularly in the generations-to-optimum results, shown in Figure 11.

It is also useful to observe landscape behaviour for levels of P greater than N. Figure 12 and Figure 13 show results for K = 2 and P = 20. In this case, the pattern of increasing difficulty with decreasing S is shown in both success in finding the optimum, and the number of generations required. A general pattern of increasing numbers of generations to find the optimum with more negative R is generally observed as well (Figure 13). However, the effects of R on success of the GA in finding the optima (Figure 12) are less clear, and seem to sometimes reflect the opposite of the expected, giving decreasing difficulty with lower and more negative R, particularly for the intermediate values of S.

Finally, we consider results for K = 4 and P = 20, shown in Figure 14 and Figure 15. As in previous plots with K = 4, note that Figure 14, has the S axis reversed, since the effects of S on the GAs ability to find the optimum are generally the opposite of our intuition. Moreover, in this case (and in other higher K and P scenarios), the effects of R seem reversed, as well. However, in the generations-to-optima results (Figure 15), the results stay relatively consistent with our analytical intuitions, as they have in our other experiments.