

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

neutral degrees. The acceptance of a transition is determined by the difference between the distance to the input distribution before and after this transition. The distance we use to compare two distributions is the root mean square :

$$d i s t(D,D_{0})={\sqrt{\sum_{i=0}^{N}(D[i]-D_{0}[i])^{2}}}$$

Simulated annealing appeared to be a fast and efficient method for this particular task. Improvements made by simulated annealing are shown in figure 3. Easiest neutral distributions to obtain seemed to be smooth ones like gaussian distributions (which are the most encountered when dealing with real or artificial neutral problems). On the other hand, sharp distributions (like the middle-right one of figure 3) are really hard to approach. In addition, independently of the shape, distributions with higher average neutral degree are harder to approximate.

## 2.3 Space And Time Complexity

To create a landscape with a search space of size 2 N , we use an array of size 2 N containing fitness values and a list of forbidden values for each solution. Thus we need a memory space of size O(2N × N). Consequently the space complexity is : O(2N × N)
In order to know what are the possible neutral degrees of an unaffected solution s, we must consider every interesting value for s
(the fitnesses of all neighbour solutions and a random value), and for each of these values, we must find out all possible neutral degrees. This can be done in a time O(N
2). We evaluate the possible neutral degrees once for each solution. Time allowed for simulated annealing is proportional to the time elapsed during construction.

Thus, the time complexity of the algorithm is O(2N N
2).

Consequently we can only construct ND-Landscapes with a small N (≤ 16) but we will see in section 4 how to create Additive Extended ND-Landscapes with far greater search spaces.

## 2.4 Sizes Of The Generated Neutral Networks

Figure 4 shows the diversity of sizes of neutral networks for 4 distributions. For every distribution we created 50 different NDLandscapes. Graphics on the left show the input and the mean resulting distribution. Graphics on the right show all of the networks of these landscapes sorted by decreasing size with a logarithmic scale. We clearly see that the neutral degree distribution is a really determining parameter for the structure of the generated landscape.

## 3. Tuning Deceptiveness Of Nd-Landscapes

Once we have generated a landscape with a specific neutral degree distribution, we can change the fitness value of all neutral networks without changing the neutral degree distribution (as long as we do not give the same fitness to two adjacent networks). Hence, for a given neutral distribution, we can tune the difficulty of a NDLandscape. For instance if each NN have a random fitness value from [0, 1] then the landscape is very hard to optimize. Here, we will use the well known *Trap* Functions [20] to affect fitnesses to NN in order to obtain a ND-Landscape with tunable deceptiveness.

The trap functions are defined from the distance to one particular solution. They admit two optima, a global one and a local one.

They are parametrized by two values b and r. The first one, b allows to set the width of the attractive basin for each optima, and r sets theirs relative importance. The function fT : {0, 1}
N → IR is so