

![0_image_1.png](0_image_1.png)

- *Deceptive problems* (**F DC** ≥ 0.15), in which fitness increases with distance to optimum.
- *Hard problems* (−0.15 **< F DC <** 0.15) in which there is no correlation between fitness and distance.

- *Easy problems* (F DC ≤ −0.15) in which fitness increases as the global optimum approaches.

Hard problems are in fact hard to predict, since in this case, the FDC brings little information. The threshold interval [−0.15, 0.15]
has been empirically determined by Jones. When FDC does not give a clear indication i.e., in the interval [−0.15, 0.15], examining the scatterplot of fitness versus distance can be useful. The FDC has been criticized on the grounds that counterexamples can be constructed for which the measure gives wrong results [22, 23, 24].

Figure 6 shows the average and standard deviation of FDC over ND-Landscapes for each set of parameters, neutral distribution and deceptiveness. The absolute value of FDC decreases as we generate ND-Landscapes with more and more neutrality. When adding neutrality, the landscapes are increasingly flatter and thus less easy or deceptive. So neutrality smoothes correlation. Adding neutrality to a deceptive landscape makes it easier and adding neutrality to a easy landscape makes it harder.

## 3.2 Genetic Algorithm Performances On Ndlandscapes

In this section, difficulty is measured by genetic algorithm performances which is the success rate over 10 independent runs. In order to minimize the influence of the random creation of NDLandscapes, we consider 30 different landscapes for each distribution D and each trap function. For the GA, one-bit mutation and one-point crossover are used with rates of respectively 0.8 and 0.2. The evolution, without elitism and with 3-tournament selection of a population of 50 individuals took place during 50 generations. Figure 8 shows average and standard deviation of GA performances over the 30 ND-landscapes. Until the average neutral

![0_image_0.png](0_image_0.png) 

degree 5, the landscapes are fully deceptive (a) or fully easy (b).

Between neutral degree 5 and 7, the deceptiveness and the easiness decrease. After neutral degree 7, the two trap functions have nearly a same good success rate (0.7). Whereas the FDC coefficient gave no information about performances, examining the scatter plot fitness/distance allowed to predict these good performances (figure 7 (c)). When neutrality increases on deceptive trap, performances increase whereas on easy trap they decrease. These results confirm conclusions found in section 3.1 from FDC measures.

## 4. Additive Extended Nd-Landscapes

Exhaustive fitness allocation allows only to generate landscapes with small search space (in our experiments 2 16 solutions). Hence we must find a way to construct similar problems on a larger scale.

We propose here to concatenate several small ND-Landscapes to create an additive ND-Landscape. Even though we are not able to create an additive ND-Landscape directly from a neutral degree distribution we can chose the mean, the standard deviation and less precisely the shape of his neutral degree distribution. Moreover, this method allows us to know exactly the neutral degree distribution of the resulting landscape. Let be P1 = (E1, V1, f1) and P2 = (E2, V2, f2) two fitness landscapes. We define the extended landscape P = P1 ⊕ P2 = (**E, V, f**) such as :
- E = E1 × E2

* $\forall(x_{1},y_{1})\in E_{1}^{2},\forall(x_{2},y_{2})\in E_{2}^{2},$ $(x_{1},x_{2})\in V(y_{1},y_{2})\iff(x_{1}\in V_{1}(y_{1})$ _and_ $x_{2}=y_{2})$ _or_ $(x_{1}=y_{1}$ _and_ $x_{2}\in V_{2}(y_{2}))$
- f(x1, x2) = f1(x1) + f2(x2)
The size of the larger ND-landscape will be the product of the sizes of the small ones. The neutral degree distribution of the resulting landscape is the *convolution product* of the two components distributions. The convolution product of two distributions D1 and D2 is the distribution D (see figure 9) such as

$\forall n\in\mathbb{N},D(n)=\sum_{i=0}^{n}(D_{1}(i)\times D_{2}(n-i))$  the full rank $n$ is a $n$-dimensional
We have the following properties :