Dip. Leonardo Vanneschi
email: vanneschi@disco.unimib.it

Yuri Pirola
email: yuri.pirola@gmail.com

Philippe Collard
email: philippe.collard@unice.fr

Marco Tomassini
email: marco.tomassini@unil.ch

S Ébastien Verel

Giancarlo Mauri
email: mauri@disco.unimib.it

A Quantitative Study of Neutrality in GP Boolean Landscapes

Keywords: I.2 [ARTIFICIAL INTELLIGENCE]: Automatic Programming; D.2.8 [Software Engineering] Metrics -complexity measures, performance measures Genetic Programming, Neutrality, Fitness Landscapes, Even Parity

Neutrality of some boolean parity fitness landscapes is investigated in this paper. Compared with some well known contributions on the same issue, we define some new measures that help characterizing neutral landscapes, we use a new sampling methodology, which captures some features that are disregarded by uniform random sampling, and we introduce new genetic operators to define the neighborhood of tree structures. We compare the fitness landscape induced by two different sets of functional operators ({nand} and {xor ; not}). The different characteristics of the neutral networks seem to justify the different difficulties of these landscapes for genetic programming.

INTRODUCTION

The role played by neutrality in determining the ability of evolutionary algorithms to find good quality solutions for a given problem has been a controversial issue in the last few years. A good introduction on the role of neutrality has been done by Reidys and Stadler in [START_REF] Reidys | Neutrality in fitness landscapes[END_REF]. In [START_REF] Toussaint | Neutrality: A necessity for self-adaptation[END_REF], Toussaint and Igel claim the necessity of a certain degree of neutrality in fitness landscapes for self-adaption. In [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF], Geard compared the neutrality of some binary landscapes claiming a relationship between neutrality and performance of genetic algorithms (GAs). In [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF], Collard et al. studied synthetic neutrality and its effects on the evolvability of GAs. The study of neutrality for genetic programming (GP) is mainly due to the work of Yu et al.: in [START_REF] Yu | Finding needles in haystacks is not hard with neutrality[END_REF], they showed that artificially introducing neutrality can help Cartesian GP to navigate some restricted fitness landscapes. These results have been recently criticized by Collins in [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF]. Some other contributions on the importance of artificially introducing neutrality into fitness landscapes can be found in [START_REF] Yu | Six degrees of separation" in boolean function networks with neutrality[END_REF][START_REF] Yu | Neutrality and the evolvability of boolean function landscape[END_REF][START_REF] Yu | The role of neutral and adaptive mutation in an evolutionary search on the onemax problem[END_REF]. In this paper, we take up a different point of view. First of all, we study even parity fitness landscapes for standard tree based GP [START_REF] Koza | Genetic Programming[END_REF] instead of Cartesian GP. Secondly, instead of artificially introducing neutrality into the landscapes, we study them without modifying them, trying to infer some conclusions on the impact of neutrality on GP performance. Third, we introduce some new neutrality measures, such as the average neutrality ratio, the average ∆-fitness of neutral networks and the ratio of some particular solutions contained into the neutral networks (see section 4 for the definitions of these measures). Fourth, we introduce some new genetic operators to define neighborhood between trees. Finally, instead of using a fixed set of functions to build solutions, we compare the landscapes induced by two different set of boolean operators ({nand} and {xor ; not}). Boolean spaces have already been studied, among others, in [START_REF] Collins | Counting solutions in reduced boolean parity[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF]. In those contributions, either landscapes of small size have been studied exhaustively (i.e. taking into account all the possible solutions) or larger fitness landscapes have been studied by means of uniform random samplings. The shape and features of the boolean parity fitness landscapes make them hard to study by means of uniform random samplings and thus more sophisticated sampling methodologies are needed. The first attempt to study them by means of some well known importance sampling techniques can be found in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. In this paper we define a new, and more elaborate, sampling methodology to study even parity fitness landscapes, but the techniques are general and can be used for any GP program space.

This paper is structured as follows: in section 2, we give some definitions that will be useful in the continuation of the paper. In section 3, we discuss some features of the even parity fitness landscapes. Section 4 contains an exhaustive investigation of a reduced size even parity landscape. Our new sampling technique is described in section 5. In section 6, we present some results on large even parity landscapes. Finally, in section 7, we offer our conclusions and ideas for future research.

PRELIMINARY DEFINITIONS

Using a landscape metaphor to develop insight about the workings of a complex system originates with [START_REF] Wright | The roles of mutation, inbreeding, crossbreeding and selection in evolution[END_REF]. A simple definition of fitness landscape in EAs is a plot where the points in the horizontal plane represent the different individual genotypes in a search space (ordered according to a particular neighborhood relationship) and the points in the vertical direction represent the fitness of each one of these individuals [START_REF] Langdon | Foundations of Genetic Programming[END_REF]. Generally, the neighborhood relationship is defined in terms of the genetic operators used to traverse the search space [START_REF] Vanneschi | Fitness distance correlation in structural mutation genetic programming[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF][START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. This can be done easily for unary genetic operators like mutation, but it is clearly more difficult if binary or multi-parent operators, like crossover, are considered. Many formal definitions of fitness landscape have been given so far (see for instance [START_REF] Stadler | Fitness landscapes[END_REF]). In this work, a fitness landscape is a triple L = (S, V, f) where S is the set of all possible solutions, V : S → 2 S is a neighborhood function specifying, for each s ∈ S, the set of its neighbors V(s), and f : S → IR is the fitness function. Given the set of variation operators, V can be defined as V(s) = {s ∈ S|s can be obtained from s by a single variation}. In some cases, as for the even parity problems, even though the size of the search space S is huge, f can only assume a limited set of values. Thus, a large number of solutions have the same fitness. In this case, we say that the landscape has a high degree of neutrality [START_REF] Reidys | Neutrality in fitness landscapes[END_REF]. Given a solution s, the subset of V(s) composed by neighbor solutions that are also neutral can be defined. Formally, the neutral neighborhood of s is the set

N (s) = {s ∈ V(s)|f (s ) = f (s)}.
The number of neutral neighbors of s is called the neutrality degree of s and the ratio between neutrality degree and cardinality of V(s) is the neutrality ratio of s. Given these definitions, we can imagine a fitness landscape as being composed by a set of (possibly large) plateaus. More formally, a neutral network [START_REF] Schuster | From sequences to shapes and back: a case study in RNA secondary structures[END_REF] can be defined as a graph connected component (S, EN ) where EN = {(s1, s2) ∈ S 2 |s2 ∈ N (s1)}. The set of all neutral networks in the fitness landscape will be denoted by NN from now on. Replacing each solution with its neutral network, we can define a fitness landscape by means of its neutrality graph GNN = (NN, ENN ), where ENN is a relation such that, given two neutral networks N1 and N2: (N1, N2) ∈ ENN ⇔ ∃s1 ∈ N1, s2 ∈ N2 : s2 ∈ V(s1)\N (s1). Finally, we define the fitness of a network (or network fitness) as the fitness value shared by all its individuals. A neutral net with fitness ϕ will be indicated as ϕ-network.

THE EVEN PARITY PROBLEM

The goal of the even-k parity problem [START_REF] Koza | Genetic Programming[END_REF] is to find a boolean function of k variables that returns True if an even number of inputs is True and False otherwise. Fitness is computed as 2 k minus the number of hits over the 2 k fitness cases represented by all the possible combinations of the k input values. Here, all the fitness values will be normalized dividing them by 2 k . Thus a perfect individual has fitness 0, while the worst individual has fitness 1. The set of all possible solutions is composed by all the well-formed trees that can be built using a function set F and a terminal symbols set T and having a depth smaller or equal than a given limit. The set T is composed by k variables (where k is the order of the problem). Two different function sets are studied in this work: {xor ; not} and {nand}. The first one is not a generator set (i.e. it is impossible to generate all the different boolean functions using only this set), but it easily enables to obtain a perfect solution for the even parity problem. The second one is a minimal generator set, but it is difficult (even though not impossible) to build an optimal solution using it (see [START_REF] Pirola | Studio della neutralità degli spazi di ricerca booleani in programmazione genetica[END_REF] for a more detailed discussion). We have chosen to use these function sets because they are small enough to limit the cardinality of the search space but also rich enough to represent some perfect solutions. Furthermore, these function sets induce two fitness landscapes with different difficulties for GP [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]: the landscape induced by {xor ; not} is easy to search, while the one induced by {nand} is generally hard. Thus, we can compare the two landscapes (indicated with L {xor ; not} (k,h) and L {nand} (k,h) from now on, where k is the problem order and h is the prefixed tree depth limit) to find some interpretations of their different difficulties.

To define a neighborhood structure based on variation operators, we have to choose a suitable set of these operators. Standard crossover or subtree mutation [START_REF] Koza | Genetic Programming[END_REF] generate neighborhoods which are too wide and complex to be studied. In this paper, we consider a simplified version of the inflate and deflate mutation operators first introduced in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF][START_REF] Vanneschi | Fitness distance correlation in structural mutation genetic programming[END_REF] (also called structural mutation operators in those works): (1) Strict deflate mutation, which transforms a subtree of depth 1 into a randomly selected leaf chosen among its children. (2) Strict inflate mutation, which transforms a leaf into a tree of depth 1, rooted in a random operator and whose children are a random list of variables containing also the original leaf. (3) Point terminal mutation, that replaces a leaf with another random terminal symbol. This set of genetic operators (that will be called Strict-Structural, or StSt, mutation operators from now on) is easy enough to study and provides enough exploration power to GP. For instance, StSt mutations present two important properties: (i) each mutation has an inverse and, (ii) for each pair of solutions, a sequence of mutations which transforms the first one into the second exists (see [START_REF] Pirola | Studio della neutralità degli spazi di ricerca booleani in programmazione genetica[END_REF] for the formal proof). Thus, the associated graph (S, V) of fitness landscape is undirected (given the (i) property) and connected (given the (ii) property) graph.

Some other interesting properties of the even parity fitness landscapes have been discussed, among others, in [START_REF] Langdon | Foundations of Genetic Programming[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF]. First of all, supposing that all fitness values have been normalized into the range [0, 1], if an expression does not contain at least an occurrence of each variable, then its fitness value is exactly equal to 0.5. For this reason, the wide majority of individuals in the even parity landscapes have fitness 0.5 [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. Secondly, an expression in the L {xor ; not} landscape can only have a fitness value equal to 0, 0.5 or 1. (see for instance [START_REF] Langdon | Foundations of Genetic Programming[END_REF][START_REF] Pirola | Studio della neutralità degli spazi di ricerca booleani in programmazione genetica[END_REF] for the formal proofs of these properties). The choice of the StSt mutation operators permits to define some other properties of the L {xor ; not} landscape: (a) there is only one neutral network at fitness 0.5 (we call it the central network), (b) all the other networks are composed by one single individual (we call them the peripheral networks) and (c) all the peripheral networks are connected with the central one by one mutation. The proofs of these properties are omitted for lack of space; they can be found in [START_REF] Pirola | Studio della neutralità degli spazi di ricerca booleani in programmazione genetica[END_REF].

EXHAUSTIVE ANALYSIS OF A "SMALL" EVEN-PARITY FITNESS LANDSCAPE

The first step of our study is to investigate a fitness landscape of small size, in order to be able to exhaustively generate all the possible individuals contained in it. We have built it by considering the even-2 parity problem and trees with a maximum depth equal to 3. The resulting

L {xor ; not} (2,3)
and

L {nand} (2,3)
landscapes both contain at least one perfect solution. In table 1 some characteristics of these fitness landscapes are reported. In agreement with the theoreti-Table 1: Some characteristics of the "small" fitness landscapes that we have exhaustively studied its size is proportional to the logarithm of the network size. The node colour indicates the fitness value of the network (from 1, black, to 0, white).

L {xor ; not} (2,3) L {nand} (2,

Experimental Results

The first parameter that we study is the average neutrality ratio, r. It is defined as the mean of the neutrality ratios (as defined in section 2) of all the individuals included into a network. High values r (near to 1) correspond to a large amount of neutral mutations. Figure 3 as in all the subsequent ones, a gray line is drawn, joining all the average points for each considered fitness value. This line should help readability. Furthermore, points at the same coordinates have been slightly displaced, so that they can be distinguished. In L {xor ; not} (2,3)

, the central network (fitness equal to 0.5) has high values of r, while for the other networks r = 0. Furthermore, the scatterplot is nearly symmetrical around fitness equal to 0.5. In L {nand} (2,3) r values are, on average, larger than 0.2 for some bad fitness values (fitness equal to 0.75) and smaller than 0.2 for good ones (fitness equal to 0 and 0.25): in general, in L {nand} (2,3) networks with bad fitness seem to be "more neutral" than networks with good fitness.

The second measure that we study is the average ∆-fitness of the neutral networks. This measure is the average fitness gain (positive or negative) achieved after a mutation of the individuals belonging to the network. Formally, let N be a neutral network, then its average ∆-fitness can be defined as:

∆ f (N ) := 1 |N | • X s∈N " P v∈V(s) (f (v) -f (s)) |V(s)| #
This measure is clearly related to the notions of evolvability [START_REF] Altenberg | The evolution of evolvability in genetic programming[END_REF] and innovation rate [START_REF] Huynen | Exploring phenotype space through neutral evolution[END_REF]. It also helps to statistically describe the graph (S, V). A negative value of ∆ f corresponds to a fitness improvement (because it reduces the error) while a positive one corresponds to a worsening (because it increases the error). As figure 4 shows, in L {nand} [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF] the possible values of ∆ f are included into a narrower range than in L {xor ; not} [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF] . We deduce that in L produce large fitness improvements (on average). Thus, to solve the problem, GP has to find individuals with many different fitness values. This is not the case for

L {xor ; not} (2,3)
, where a mutation of an individual contained into the central network can produce an individual with a fitness equal to 0 (global optimum). Furthermore, in L {nand} [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF] good fitness networks (fitness equal to 0.25 or 0.5) have positive values of ∆ f . In other words, in L {nand} (2,3) , it is unlikely that mutations of good individuals generate better offspring. Now, we present two measures that we have called Non Improvable (NI) Solutions ratio (rni) and Non Worsenable 1 (NW) Solutions ratio (rnw). The first one is defined as the number of non-improvable solutions, or non-strict local optima (i.e. individuals i which cannot generate offspring j by applying a StSt mutation such that the fitness of j is better than the fitness of i) that are contained into a network divided by the size of the network. The second one is the ratio of the individuals i which cannot generate offspring j (by applying a StSt mutation) such that the fitness of j is worse than the fitness of i. Figures 5 and6 present the scatterplots of rni and rnw for each fitness value, respectively.

NI solutions ratio is 1 in 0-networks (they are composed of optimal solutions, so they cannot further improve) and it is 0 in 1-networks. Analogously, NW solutions ratio is 1 in 1-networks and it is 0 in 0-networks. In L {nand} (2,3) , there are some good networks (low fitness) with high rni values. At fitness 0.25, all the networks have an high value of rni (larger than 0.6) and 5 of them (over a total of 9 networks) have a value of rni equal to 1 and thus they are plateaus of nonstrict local optima. We call these networks trap networks, since their individuals cannot generate better offspring and thus once GP has reached these networks, it cannot escape from them by means of a StSt mutation improving fitness. Trap networks do not exist in L {xor ; not} (2,3)

. 1 We are aware that the word "worsenable" does not exist in the English dictionary. Nevertheless we use it here as a contrary of "improvable", i.e. as something that cannot be worsened. all the points are disposed along the segment ((1, 0), (0, 1)). In L {nand} (2,3) , the scatterplots are approximately parallel to the Cartesian axis and networks located at good fitness values have a large number of NI solutions. Thus, it is unlikely to mutate their individuals generating better offspring. This is not the case for L {xor ; not} [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF] . This may help explain why the

L {nand} (2,3)
landscape is hard for GP, while L {xor ; not} (2,3) is easy. 2 The scatterplot at fitness values equal to 1 and 0 are not reported for lack of space. However, they are obviously identical to the case of L {xor ; not} [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF] reported in figure 8. .

SAMPLING METHODOLOGY

The even parity fitness landscape is a very hard one to sample. In fact, as the order k of the problem increases, the percentage of individuals with a fitness equal to 0.5 increases too. In [START_REF] Collins | Counting solutions in reduced boolean parity[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] some uniform random samplings for these spaces have been presented. In [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF] some well known importance sampling techniques such as Metropolis and Metropolis-Hastings have been used. Even though the resuls obtained were satisfactory for the purposes of those works, still the large majority of the individuals had fitness equal to 0.5 and too few ones with different fitness were considered. Thus, those samples did not capture some important characteristics of the fitness landscape, such as the number and size of the neutral networks at fitness values different from 0.5, the connectivity of optimal solutions to these networks, etc. In other words, those samplings did not offer a useful "view" of the fitness landscapes and did not allow us to completely understand the behavior of GP on them.

In this paper, we present a new methodology to generate samples containing trees of many (possibly all the) different fitness values and forming connected neutral networks, if possible. This technique is composed by three steps: we have called them modified Metropolis, vertical expansion and horizontal expansion. Modified Metropolis generates a sample S of individuals. The vertical expansion tries to enrich S by adding to it some non-neutral neighbors of its individuals. Finally, the horizontal expansion tries to enrich S by adding to it some neutral neighbors of its individuals.

Modified Metropolis Sampling

Our sampling methodology has been inspired by the Metropolis technique. According to that technique, a solution is generated at random at the beginning and considered as the current solution P . Successively, a loop is executed. At each iteration of that loop, a new solution T is generated at random and accepted (and thus inserted into the sample and considered as the new current solution P ) or rejected according to a certain probability distribution. In the Metropolis technique, the distribution for accepting or rejecting individuals is equal to αM (f (P ), f(T )) = min

" 1, f (P ) f (T ) "
, where f is the fitness function. In this way, the Metropolis technique favors fitter solutions but it does not penalize solutions at fitness 0.5. In our methodology, we define a probability distribution α that rewards solutions with a different fitness than the previously accepted one. In this way, we intend to reward solutions with a different fitness than 0.5. Let pm be the minimum probability of accepting a solution, then our definition of the α function is:

α(f (P ), f(T )) = (1-pm)•log 10 " 9 • |f (P ) -f (T )| max(f (P ), 1 -f (P )) + 1 « +pm (1)
In this way, if |f (P )f (T )| is equal to 0, the new solution T gets a small probability (equal to pm) of being accepted3 . On the other hand, the larger the value of |f (P )f (T )|, the higher the probability. In particular, if T has the most different possible fitness value from P , then |f (P )f (T )| =max(f (P ), 1f (P )). In that case, the logarithmic term becomes log10(9 + 1) = 1, and thus α(f (P ), f(T )) = 1.

We have chosen a logarithmic function because it increases very quickly for small differences and thus it also rewards solutions T with a slightly different fitness from P .

Vertical Expansion

The vertical expansion of our methodology takes as input the sample S generated by the modified Metropolis algorithm and enriches it by adding some new individuals. In synthesis, it works as follows: for each individual i ∈ S, L different neighbors of i are generated by means of L StSt mutations. Each one of these neighbors can be accepted or rejected according to the probability distribution expressed by equation [START_REF] Altenberg | The evolution of evolvability in genetic programming[END_REF]. All accepted neighbors are finally inserted in S which is returned as output of the vertical expansion phase. Since the value of pm is "small", there is a "small" probability of having neutral neighbors in S at the end of the vertical phase. The goal of the horizontal phase is basically to add some neutral neighbors to the individuals in S. The neighbors which have been generated by the vertical expansion phase will represent the "links" (or "bridges") between these neutral networks.

Horizontal Expansion

Let an incomplete neutral network be a sample IN of a neutral network N such that at least one neutral neighbor j of an individual i ∈ IN exists such that j / ∈ IN . The horizontal expansion phase of our sampling technique takes as arguments the sample S returned by the vertical expansion phase, the minimum admitted size of an incomplete neutral network Imax and the maximum size of the sample that has to be generated Smax. These last two measures are parameters of our sampling technique and have to be manually defined. The horizontal phase returns a new sample S, possibly enriched by some individuals that form some neutral networks. It can be defined by the pseudo-code in figure 9, where rnd(0,1) is a random number generated with uniform probability from the range (0, 1), iter is a variable containing the number of iterations that have been executed and β(f (i), f(j), iter) is defined as follows:

β(f (i), f(j), iter) = ( 1 i ff (i) = f (j), k -iter otherwise
where k is a constant that has to be chosen in such a way that probability β decreases "quickly enough" with iterations (in this work, k = 4). Horizontal expansion stops when the sample reaches the maximum size Smax or when an iteration does not add any new individual. This phase iter ← 1; while (at least one incomplete neutral network exists in S) and (|S| < Smax) do N ← set of incomplete networks in S of size less than Imax; expands the size of neutral networks contained in the sample, by adding some new neutral neighbors to them. This is very useful to study neutrality, but it has some bias: for instance, a large neutral network could be represented in our sample by many smaller ones. It is the case, for instance, of the central network for the L {xor ; not} landscape. However, in this particular case, this is not a problem, since we are aware about the unicity of the central network because of the theoretical results presented in section 3 (property (a)). Those theoretical results should contribute to understand the real shapes of the fitness landscapes under study.

forall N ∈ N do forall i ∈ N do forall j ∈ V(i) do if (rnd(0,1) < β(f (i), f(j),

ANALYSIS OF A "REALISTIC" FITNESS LANDSCAPE BY MEANS OF SAMPLING

The largest search spaces that we have been able to study using our computational resources 4 correspond to the even-4 parity problems using trees of a maximum depth equal to 8. We indicate with L {xor ; not} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] and L {nand} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] the landscapes using {xor ; not} and {nand} as function sets respectively. Both these spaces contain optimal solutions for the even-4 parity. Nevertheless, for L {nand} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] they are difficult to automatically generate (either by a Metropolis algorithm or by GP). Thus, in order to sample all the possible fitness values, one of them has been manually added to the S sample that has been given as input to the vertical expansion phase. For the same reason, we have manually added to S an individual with the worst possible fitness (fitness equal to 1). Table 2 summarizes the parameters used to generate the samples of the two landscapes. Figure 10 monitors the fitness distributions and shows that our samples have covered the whole range of possible fitness values for the two landscapes.

In figure 11, we present the average neutrality ratios (r). The ratios calculated over the sample of L {xor ; not} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] are not affected by the presence of multiple 0.5-networks (caused by the bias of our sampling methodology) instead of having only one central network: all the ratios of these networks are close to the "large" single one observed for the even-2 parity 4 A PC 2.6 GHz with Pentium T M IV Processor, with 512MB central memory and 30GB hard disk. (left part) and

L {xor ; not} (4,8)
(right part).

(figure 3). Furthermore, as for L {nand}

(figure 3), also in

L {nand} (4,8)
the networks with good fitness values have a lower r than ones with bad fitness values. The networks with good fitness in L {nand} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] seem to be "less neutral" than ones with bad fitness.

The scatterplot of the average ∆-fitness is shown in figure 12. In L {xor ; not} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] this scatterplot reflects the behaviour observed for the even-2 parity (figure 4 landscapes for the even-4 parity problem.

The scatterplot of NI and NW solutions (figures 13 and 14 respectively) present some differences with respect to the ones observed for the landscape studied exhaustively (figures 5 and 6), expecially for L {nand} [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF] . Nevertheless, as in networks with good fitness values have a large number of NI solutions and thus it is unlikely to escape from them mutating its individuals, which is not the case for L {xor ; not} (4,8)

.

CONCLUSIONS AND FUTURE WORK

Some new characteristics of fitness landscapes related to neutrality have been defined in this paper and studied for different versions of the boolean parity problem. In particular, we have defined: (1) the average neutrality ratio of a neutral network, which quantifies the amount of possible neutral mutations of its individuals; (2) the average ∆fitness of a neutral network, which quantifies the average fitness gain achieved by mutating its individuals; (3) the nonimprovable solutions ratio, which quantifies the amount of solutions that cannot generate better offspring in a neutral network; (4) the "non-worsenable" solutions ratio, which quantifies the amount of solutions that cannot generate worse offspring in a neutral network. Studying measure (1), we have observed that networks with bad fitness values seem to be "more neutral" than networks with good fitness values if {nand} is used as the set of operators, while this is not the case if {xor ; not} is used. Studying measures (2), ( 3) and (4), we have observed that it is unlikely to improve fitness mutating individuals of neutral networks with good fitness values if {nand} is used, which is not the case if we use {xor ; not}. These results may help explain why the even parity problem is easy for GP if we use {xor ; not} and hard if we use {nand}. These results hold both for a "small" fitness landscape that we have been able to study exhaustively and for a "large" fitness landscape that we have sampled using a new methodology defined in this paper. This fact may suggest the suitability of our sampling methodology for the boolean parity problems. Since our techniques are general and can be used for any GP program space, future work includes extending this kind of study to other problems and possibly defining new measures of problem hardness based on neutrality. Finally, studying neutrality induced by inflate and deflate mutations separately may provide some useful information about bloat.

  has a large number (1388) of neutral networks at fitness 0 and 1 composed by only one individual and one large (4164 individuals) central network at fitness 0.5. On the other hand, L {nand} (2,3) has smaller size and it has few networks, all of them medium-sized. Figures 1 and 2 report a graphical representation of the neutrality graphs of L {nand} (2,3) and L {xor ; not} (2,3) respectively. Each square represents a neutral network, and

Figure 1 :

 1 Figure 1: Graphical representation of the neutrality graph of L {nand} (2,3) .

Figure 2 :

 2 Figure 2: Graphical representation of the neutrality graph of L {xor ; not} (2,3)

.

Figure 3 :

 3 Figure 3: Scatterplot of the average neutrality ratio in L {nand} (2,3) (left part) and L {xor ; not} (2,3) (right part).

Figure 4 :

 4 Figure 4: Scatterplot of the average ∆-fitness in L {nand} (2,3) (left part) and L {xor ; not} (2,3) (right part).

Figure 5 :

 5 Figure 5: Scatterplot of NI solutions ratio in L {nand} (2,3) (left part) and L {xor ; not} (2,3) (right part).

Figure 6 :Figure 7 :

 67 Figure 6: Scatterplot of the NW solutions ratio in L {nand} (2,3) (left part) and L {xor ; not} (2,3) (right part).

Figure 8 :

 8 Figure 8: Scatterplot of the NW solutions ratio vs. the NI solutions ratio in L {xor ; not} (2,3)

Figure 9 :

 9 Figure 9: The pseudo-code describing the horizontal expansion of our sampling methodology.

Figure 10 :Figure 11 :

 1011 Figure 10: Fitness distribution of the sampled L {nand} (4,8) (left part) and L {xor ; not} (4,8) (right part).

Figure 12 :

 12 Figure 12: Scatterplot of average ∆-fitness in the sampled L {nand} (4,8) (left part) and L {xor ; not} (4,8) (right part).

Figure 13 :

 13 Figure 13: Scatterplot of NI solutions ratio in the sampled L {nand} (4,8) (left part) and L {xor ; not} (4,8) (right part).

Figure 14 :

 14 Figure 14: Scatterplot of NW solutions ratio in the sampled L {nand} (4,8) (left part) and L {xor ; not} (4,8) (right part).

L {nand} ( 2 , 3 )Figure 15 :

 2315 Figure 15: Scatterplot of NW vs. NI solutions ratio in the sampled L {xor ; not} (4,8).

Figure 16 :

 16 Figure 16: Scatterplot of NW vs. NI ratio in the sampled L {nand} (4,8) .

  [START_REF] Collins | Counting solutions in reduced boolean parity[END_REF]

	No. of individuals	5552	1446
	No. of optimal solutions	660	8
	No. of neutral networks	1389	31
	Average network size	3.99	46.64
	cal observations presented in section 3, L

{xor ; not}

[START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF][START_REF] Collins | Counting solutions in reduced boolean parity[END_REF]

Table 2 :

 2 Parameters used to sample the L

	{nand} (4,8) it varies over a more limited range of values. Our inter-), whereas in L
	pretation is that to significantly improve a solution is more
	difficult in L ity of the mutations generate solutions with similar fitness. {nand} (4,8) {xor ; not} (4,8) because the major-than in L
	{nand} (4,8) nerating individuals of many different fitness values, i.e. GP can be found by GP only ge-Thus the optimum in L
	cannot perform "large jumps" as in L	{xor ; not} (4,8)	.

If we set pm = 0 and f (P ) is equal to 0.5, then the algorithm is likely to never terminate. Thus, a value of pm larger than zero, even though "as small as possible", has to be used.


Leonardo Vanneschi

Philippe Collard

Marco Tomassini

Sébastien Verel

Yuri Pirola

Giancarlo Mauri

A Comprehensive View of Fitness Landscapes with Neutrality and Fitness Clouds

We define a set of measures that capture some different aspects of neutrality in evolutionary algorithms fitness landscapes from a qualitative point of view. If considered all together, these measures offer a rather complete picture of the characteristics of fitness landscapes bound to neutrality and may be used as broad indicators of problem hardness. We compare the results returned by these measures with the ones of negative slope coefficient, a quantitative measure of problem hardness that has been recently defined and with success rate statistics on a well known genetic programming benchmark: the multiplexer problem. In order to efficacely study the search space, we use a sampling technique that we have recently introduced and we show its suitability on this problem.

Introduction

Neutrality of Evolutionary Algorithms (EAs) fitness landscapes has been widely studied in the last few years. Nevertheless, many contributions that have appeared use very different concepts and measures between them to express neutrality. For instance, in [START_REF] Reidys | Neutrality in fitness landscapes[END_REF], Reidys and Stadler define the notion of additive random landscapes as a framework for tuning both neutrality and ruggedness of fitness landscapes; in [START_REF] Toussaint | Neutrality: A necessity for self-adaptation[END_REF], Toussaint and Igel talk of the suitability of the design of neutral encodings to improve the efficiency of EAs; in [START_REF] Collard | Synthetic neutrality for artificial evolution[END_REF], Collard et al. introduce the concept of synthetic neutrality and study its effects on the evolvability of Genetic Algorithms (GAs); in [START_REF] Yu | Finding needles in haystacks is not hard with neutrality[END_REF][START_REF] Yu | Six degrees of separation" in boolean function networks with neutrality[END_REF][START_REF] Yu | Neutrality and the evolvability of boolean function landscape[END_REF][START_REF] Yu | The role of neutral and adaptive mutation in an evolutionary search on the onemax problem[END_REF], Yu and Miller show that increasing the search space's size by artificially introducing neutral neighbors to some individuals, can help Cartesian Genetic Programming (GP) to navigate some restricted fitness landscapes, focusing on the choice of the representation and how it affects the amount of neutral neighborhood in a fitness landscape (these results have been recently criticized by Collins in [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF]). If on the one hand this multiplicity of different concepts and formalisms has contributed to fortify the belief that neutrality plays an important role in the search process of EAs from many different points of view, on the other we think that uniformity in treating neutrality is missing and we fear that this may lead to ambiguous and sometimes confusing conclusions. In other words, we strongly agree with Geard [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] that the way in which neutrality is defined is crucial in determining its role and that the choice of different neutrality frameworks and formalizations may lead to different, and in some cases even conflicting, conclusions.

One of the main goals of this paper is establishing a precise set of neutrality measures, each of which aimed at formalizing a particular aspect of fitness landscapes bound to neutrality. These measures (some of which already introduced in [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF]) are: the average neutrality ratio, the average ∆-fitness, the non-improvable and "non-worsenable" solutions ratio and the profitable and unprofitable mutations ratio. Each of them is calculted on neutral networks. None of them brings a sufficient amount of information if considered alone, since each of them focus only on a particular feature of the landscape, but the joint analysis of all of them should allow us to have a rather complete picture of fitness landscapes, especially those related to neutrality. Furthermore, even though a bound between neutrality and problem difficulty has often been hypothesized, neutrality has never been presented together with other difficulty measures before, in order to check if the respective results are consistant between each other or not. In this paper, we compare the qualitative results returned by our neutrality measures with the quantitative results returned by the Negative Slope Coefficient (NSC) (a hardness measure that has recently been proposed in [START_REF] Vanneschi | Negative slope coefficient. a measure to characterize genetic programming fitness landscapes[END_REF][START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]) and we hope that the results returned by our neutrality measures may support and strengthen the ones of the NSC. For our empirical study, we use two different versions of the multiplexer problem, induced by two different sets of functional operators: {IF} and {NAND}. Finally, as discussed in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF], the shape and features of the boolean functions fitness landscapes make them hard to study by means of uniform random samplings and thus more sophisticated sampling methods are needed. In this paper we use a new, and more elaborate, sampling methodology that has been first defined in [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF].

This paper is structured as follows: in section 2 we introduce some notions that will be used in this paper and we present NSC results for the two chosen instances of the multiplexer problem. Section 3 presents the view of neutrality features of these two landscapes, as offered by our quantitative neutrality measures. Finally, section 4 discusses the results, concludes the paper and offers hints for future research activity.

Definitions and Preliminary Results

Fitness Landscapes and Neutrality. Using a landscape metaphor to gain insight about the workings of a complex system originates with the work of Wright on genetics [START_REF] Wright | The roles of mutation, inbreeding, crossbreeding and selection in evolution[END_REF]. A simple definition of fitness landscape in EAs is a plot where the points in the horizontal plane represent the different individual genotypes in a search space (placed according to a particular neighborhood relationship) and the points in the vertical direction represent the fitness of each one of these individuals [START_REF] Langdon | Foundations of Genetic Programming[END_REF]. Generally, the neighborhood relationship is defined in terms of the genetic operators used [START_REF] Vanneschi | Fitness distance correlation in structural mutation genetic programming[END_REF][START_REF] Langdon | Foundations of Genetic Programming[END_REF][START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. This can be done easily for unary genetic operators like mutation, but it is clearly more difficult if binary or multi-parent operators, like crossover, are considered. Formal definitions of fitness landscape have been given (e.g. in [START_REF] Stadler | Fitness landscapes[END_REF]). Following these definitions, in this work a fitness landscape is a triple L = (S , V , f ) where S is the set of all possible solutions, V : S → 2 S is a neighborhood function specifying, for each s ∈ S, the set of its neighbors V (s), and f : S → IR is the fitness function. Given the set of variation operators, V can be defined as V (s) = {s ∈ S|s can be obtained from s by a single variation}.

In some cases, as for many GP boolean problems, even though the size of the search space S is huge, f can only assume a limited set of values. Thus, a large number of different solutions have the same fitness. In this case, we say that the landscape has a high degree of neutrality [START_REF] Reidys | Neutrality in fitness landscapes[END_REF]. Given a solution s, a particular subset of V (s) can be defined: the one composed by neighbor solutions that are also neutral. Formally, the neutral neighborhood of s is the set N (s) = {s ∈ V (s)| f (s ) = f (s)}. The number of neutral neighbors of s is called the neutrality degree of s and the ratio between neutrality degree and cardinality of V (s) is the neutrality ratio of s. Given these definitions, we can imagine a fitness landscape as being composed by a set of (possibly large) plateaus. More formally, a neutral network [START_REF] Schuster | From sequences to shapes and back: a case study in RNA secondary structures[END_REF] can be defined as a graph connected component

(S , E N ) where E N = {(s 1 , s 2 ) ∈ S 2 |s 2 ∈ N (s 1 )}.
Finally, we define the fitness of a neutral network (or network fitness) as the fitness value shared by all individuals of this neutral network.

Negative Slope Coefficient. Evolvability [START_REF] Altenberg | The evolution of evolvability in genetic programming[END_REF] can be studied by plotting the fitness values of individuals against the fitness values of their neighbours. Such a plot has been presented in [START_REF] Collard | Local search heuristics: Fitness cloud versus fitness landscape[END_REF][START_REF] Barnett | Evolutionary Search on Fitness Landscapes with Neutral Networks[END_REF] and called fitness cloud. A possible algorithm to generate fitness clouds was proposed in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. This algorithm essentially corresponds to the sampling produced by a set of n stochastic hill-climbers at their first iteration after initialisation. The Negative Slope Coefficient (NSC) has been defined to capture with a single number some interesting characteristics of fitness clouds. It can be calculated as follows: the abscissas of a fitness cloud can be partitioned into a certain number of separate bins {I 1 , I 2 , . . . , I m }. Let X 1 , X 2 , . . . , X m be the averages of the abscissas of the points contained in bins I 1 , I 2 , . . . , I m , respectively, and let Y 1 ,Y 2 , . . . ,Y m be the averages of the ordinates of the points in I 1 , I 2 , . . . , I m . The set of points (X i ,Y i ) can be seen as the vertices of a polyline, which effectively represents the "skeleton" of the fitness cloud. For each of the segments of this, we can define a slope, S i = (Y i+1 -Y i )/(X i+1 -X i ). Finally, the negative slope coefficient is defined as NSC = ∑ m-1 i=1 min (0, S i ). The hypothesis proposed in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF] is that the NSC should classify problems in the following way: if NSC= 0, the problem is easy; if NSC< 0 the problem is difficult and the value of NSC quantifies this difficulty: the smaller its value, the more difficult the problem. The justification put forward for this hypothesis was that the presence of a segment with negative slope would indicate a bad evolvability for individuals having fitness values contained in that segment as neighbours would be, on average, worse than their parents. Pros and cons of this measure have been discussed in [START_REF] Vanneschi | Negative slope coefficient. a measure to characterize genetic programming fitness landscapes[END_REF][START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]. Genetic Operators and Neighborhood. Standard crossover or subtree mutation [START_REF] Koza | Genetic Programming[END_REF] generate very complex neighborhoods. In this paper, we consider a simplified version of the inflate and deflate mutation operators first introduced in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF][START_REF] Vanneschi | Fitness distance correlation in structural mutation genetic programming[END_REF] (also called structural mutation operators in those works): (1) Strict deflate mutation, which transforms a subtree of depth 1 into a randomly selected leaf chosen among its children. (2) Strict inflate mutation, which transforms a leaf into a tree of depth 1, rooted in a random operator and whose children are a random list of variables containing also the original leaf.

(3) Point terminal mutation, that replaces a leaf with another random terminal symbol. This set of genetic operators (already introduced in [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF] and called Strict-Structural, or StSt, mutation operators) is easy enough to study and provides enough exploration power to GP. For instance, StSt mutations present two important properties: (i) each mu-tation has an inverse: let M be the set of StSt mutation operators and let S be the set of all the possible individuals (search space). For each pair of individuals (i, j) ∈ S, if an operator m ∈ M exists such that m(i) = j, then an operator m -1 ∈ M such that m -1 ( j) = i always exists; (ii) for each pair of solutions (i, j) ∈ S, a sequence of mutations which transforms i into j exists. See [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF] for the formal proofs of these properties. Thus, the associated graph (S , V ) of fitness landscape is undirected (given the (i) property) and connected (given the (ii) property) graph.

The Multiplexer Problem. The goal of the k-multiplexer [START_REF] Koza | Genetic Programming[END_REF] problem is to design a boolean function with k inputs and one output. The first x of the k inputs can be considered as address lines. They describe the binary representation of an integer number. This integer chooses one of the 2 x (= kx) remaining inputs. The correct output for the multiplexer is the input on the line specified by the address lines. The terminals are the k variable inputs to the function. The fitness function of a GP individual E is calculated as the number of input data for which E does not return the same value as the target function. In this paper, the fitness values have always been normalized into the [0, 1] range, by dividing them by 2 k , where k is the problem's order. Thus, from now on a solution with fitness equal to 0 represents an optimal solution, while 1 is the worst possible fitness value. In this paper, we have used two different sets of non-terminals: {IF} (where IF(x, y, z) is a ternary boolean function which returns y if x is true and z otherwise) and {NAND}. We have chosen these two sets because they are small enough to limit the cardinality of the search space but rich enough to represent some perfect solutions. These two sets of boolean operators induce two landscapes (indicated by

L {IF} (k,h) and L {NAND} (k,h)
from now on, where k is the problem order and h is the prefixed tree depth limit) the first of which is generally easy for GP, while the second is hard. This fact is confirmed by the experimental results shown in table 1, where the values of the success rate (SR) for three different mutation rates and NSC are reported for both landscapes. The success rate results have been obtained by executing 100 indepen- dent GP runs using the 6-multiplexer problem, maximum tree depth for the individuals equal to 6 for the landscape induced by {NAND} and to 5 for the landscape induced by {IF} (the choice of these values for the tree depths are motivated later), population of size 100, ramped half-and-half population initialization, tournament selection of size 10, StSt mutations as genetic operators. Only one StSt mutation operator has been applied with a certain probability p m . 100 GP runs have been executed with p m = 0.95 (column 2 of table 1), 100 separate runs have been executed with p m = 0.5 (column 3)

and 100 further runs have been executed with p m = 0.25 (column 4). The choice of the particular mutation operator has been done each time uniformly at random between the three StSt mutations. A run has been considered successful when an individual with a lower fitness than 0.15 has been found. The results related to the NSC reported in table 1 (column 5) have been obtained by generating a sample of 40000 individuals with the Metropolis-Hastings algorithm and, for each of them, a neighbor by applying one StSt mutation. Once again, the choice of the particular mutation operator to generate each neighbor has been done uniformly at random between the three StSt mutations.

Sampling Methodology. In [START_REF] Langdon | Foundations of Genetic Programming[END_REF] uniform random samplings have been used for studying boolean function landscapes. In [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF] importance sampling techniques such as Metropolis and Metropolis-Hastings [START_REF] Madras | Lectures on Monte Carlo Methods[END_REF] have been proposed. Even though the resuls obtained were satisfactory for the purposes of those works, still those samples did not capture some important characteristics of the fitness landscape (see [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF] for a detailed discussion). In this paper, we use a methodology aimed at generating samples containing trees of many (possibly all) different fitness values and forming connected neutral networks, if possible. This technique is composed by three steps: modified Metropolis, vertical expansion and horizontal expansion. Modified Metropolis generates a sample S of individuals with as many different fitness values as possible. The vertical expansion tries to enrich S by adding to it some non-neutral neighbors of its individuals. Finally, the horizontal expansion tries to enrich S by adding to it some neutral neighbors of its individuals. This methodology has been presented in [START_REF] Vanneschi | A quantitative study of neutrality in GP boolean landscapes[END_REF] and it is not described here to save space.

Neutrality Results

In this section we present a study of neutrality of L {NAND} (6,6)

and L {IF} (6,5) , which are the largest search spaces respectively induced by {NAND} and {IF} that we have been able to study with our computational resources. The difference in the tree depth limit for the two landscapes is due to the fact that NAND is an operator with arity 2 while IF is an operator of arity 3. Thus, given a fixed tree depth, the trees that can be built with IF are on average larger than the ones that can be built with NAND. Figure 1 shows the fitness distributions of the samples of L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] and L {IF} (6,5) that we have generated with our sampling technique. For L {IF} (6,5) , all the sampled fitness values are included into the range [0, 0.7]; in other words, no bad individual has been sampled. This is probably a characteristic of the complete search space (and it is not due to a bias of our samplig technique); in fact, we have exhaustively generated all the possible individuals of L {IF} (3,2) and we have observed that no tree with fitness larger than 0.7 exists also in that (similar, although much smaller) search space. On the other hand, for L {NAND} to generate individuals with many different fitness values, which is quite unusual for boolean landscapes (as pointed out, for instance, in [START_REF] Vanneschi | Theory and Practice for Efficient Genetic Programming[END_REF]). Figure 2 neutrality ratio, r is defined as the mean of the neutrality ratios (as defined in section 2) of all the individuals in a network. High values of r (near to 1) correspond to a large amount of neutral mutations. As figure 2 clearly shows, L {IF} (6,5) has a higher neutrality ratio than L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] , in particular for networks at good fitness values. In other words,

L {IF} (6,5) is "more neutral" than L {NAND} (6,6)
in good regions of the fitness landscape. In this figure, as in all the subsequent ones, to guide the eye, a gray line is drawn, joining all the average points for each considered fitness value. These averages have been weighted according to the size of networks representing each point. Furthermore, points at the same coordinates have been artificially (slightly) displaced, so that they can be distinguished.

The second measure we study is the average ∆-fitness of the neutral networks. This measure is the average fitness gain (positive or negative) achieved after a mutation of the individuals belonging to the network. Formally, let N be a neutral network, then its average ∆-fitness can be defined as:

∆ f (N) := 1 |N| • ∑ s∈N ∑ v∈V (s) ( f (v) -f (s)) |V (s)|
This measure is clearly related to the notions of evolvability [START_REF] Altenberg | The evolution of evolvability in genetic programming[END_REF] and innovation rate [START_REF] Huynen | Exploring phenotype space through neutral evolution[END_REF]. It also helps to statistically describe the graph (S , V ). A negative value of ∆ f corresponds to a fitness improvement (because it reduces the error) while a positive one corresponds to a worsening (because it increases the error). The average ∆-fitness scatterplots are not reported here to save space, but we have studied them and we have observed that improving good individuals for L {IF} (6,5) is easier than for L {NAND}

, in fact, for neutral networks at good fitness values, the value of the average ∆-fitness for

L {NAND} (6,6)
is positive and much larger than the one for L {IF} (6,5) . Now, we present two measures that we have called Non Improvable (NI) Solutions ratio and Non Worsenable4 (NW) Solutions ratio. The first one is defined as the number of non-improvable solutions, or non-strict local optima (i.e. individuals i which cannot generate offspring j by applying a StSt mutation such that the fitness of j is better than the fitness of i) that are contained into a network divided by the size of the network. The second one is the ratio of the individuals i which cannot generate offspring j (by applying a StSt mutation) such that the fitness of j is worse than the fitness of i. The scatterplots of NI solutions ratios are reported in figure 3. L {NAND} solutions ratios larger than 0.2 for some good fitness values (see for instance the picks at fitness values approximately equal to 0.1, 0.125, 0.375). This indicates the presence of some trap neutral networks at this fitness values. This is not the case for L {IF} (6,5) where NI solutions ratios are always equal to zero, except the obvious case of fitness equal to zero, where the NI solutions ratio is, of course, equal to one. In other words, for L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] some good individuals exist that cannot be improved by means of mutation, while this is not the case for L {IF} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF] . NW solutions ratios scatterplot are not reported here to save space. Nevertheless, we have studied them and we point out that neutral networks in L {IF} (6,5) contain more NW solutions than for the ones in L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] .

Figure 4 shows the scatterplot of unprofitable mutations ratios: for L {NAND} not generate better offspring and divided it by the total number of possible mutations of the individuals in that network. Values of the unprofitable mutation ratios are higher for good fitness values in L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] than in L {IF} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF] . In particular, for fitness values between 0 and 0.25, the majority of the possible mutations in L {NAND} [START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] are unprofitable, while for L {IF} (6,5) only about half of the possible mutations appear to be unprofitable.

All the neutrality measures that we have studied indicate that L {IF} landscapes lead us to the same conclusions. Thus we hypothesize that our sampling technique is a suitable one to study our neutrality measures (i.e. the qualitative trends of our neutrality measures are kept as in the original complete landscape by our sampling technique).

Conclusions and Future Work

Some new characteristics of fitness landscapes related to neutrality have been defined in this paper and studied for two different versions of the multiplexer problem. In particular, we have defined: the average neutrality ratio, the average ∆-fitness, the nonimprovable and "non-worsenable") solutions ratio and the profitable and unprofitable) mutations ratio of neutral networks. Each one of these measures, if considered alone, gives too a particular vision of the fitness landscape to allow us to draw strong conclusions about its difficulty. But considered all together, they have allowed us to have a clear and rather complete picture of the characteristics of multiplexer functions landscapes. In particular, all these measures have contributed to give an interpretation of the fact that the set of operators {IF} induces an easier fitness landscape than {NAND} for the multiplexer problem. This facts have also been experimentally demonstrated by executing 100 independent GP runs for each one of these problems and calculating the success rate. As a further confirmation, we have also calculated the value of another GP hardness indicator, called Negative Slope Coefficient. Another interesting result that we have obtained with our measures is that the landscapes induced by {IF} appear to be "more neutral" than the corresponding ones induced by {NAND}, in particular in correspondance of neutral networks with good (although not optimal) fitness values. Thus, in these particular case studies, neutrality (as expressed by the average neutrality ratio measure) has revealed helpful for GP, in particular when located in good regions of the fitness landscape. In many recent contributions, a bound between neutrality and GP performance has been hypothesized and neutrality has been presented as a profitable [START_REF] Toussaint | Neutrality: A necessity for self-adaptation[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Yu | Finding needles in haystacks is not hard with neutrality[END_REF] or unprofitable [START_REF] Collins | Finding needles in haystacks is harder with neutrality[END_REF] characteristic of fitness landscapes. What may often be misleading in these discussions is, in our opinion, what kind of neutrality is being considered: many different ways of intending and formalizing the concept of neutrality may exist and each one of them may lead to different, and in some cases conflicting, conclusions. All our results considered, we argue that our measures may be helpful in establishing some good tools to study neutrality and relate it to GP problem hardness, or at least to investigate some important features of fitness landscapes bound to neutrality. Results shown in this paper hold both for "small" fitness landscapes, that we have been able to study by exhaustively generating all the individuals, and for "large" fitness landscapes, obtained by increasing the problem order and the maximum size of the individuals, and that we have sampled using a new methodology defined in this paper. This methodology is based on a modified version of the Metropolis algorithm (in which we have changed the probability of accepting a new individual into the sample), enriched by two further algorithms that we have called vertical and horizontal expansion. By means of our sampling strategy, it has been possible to generate and to study a large number of individuals that would not (or would very rarely) have been generated by means of a uniform random sampling or a standard Metropolis algorithm. Furthermore, our sampling technique has allowed us to generate individuals with approximately all the possible fitness values, thus giving us a more complete view of the fitness landscapes. Since our techniques are general and can be used for any GP program space, future work includes extending this kind of study to other problems and possibly defining new measures of problem hardness based on neutrality.

( 6 , 6 )Fig. 1 .

 661 Fig. 1. Fitness distribution of L {NAND} (6,6)

Fig. 2 .

 2 Fig.2. Scatterplot of the average neutrality ratio in L {NAND}[START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF]

Fig. 3 .

 3 Fig. 3. Scatterplot of NI solutions ratio in L {NAND} (6,6)

( 6 , 5 )Fig. 4 .

 654 Fig. 4. Scatterplot of unprofitable mutations ratio in L {NAND} (6,6)

( 6 , 5 )

 65 should be easier than L {NAND}[START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF][START_REF] Geard | A comparison of neutral landscapes -nk, nkp and nkq[END_REF] for GP. Furthermore, separate studies that we have done exhaustively generating all the possible individuals of the similar but smaller L {IF} (3,2) and L {NAND} (3,3)

Table 1 .

 1 Set Of Operators SR(p m = 0.95) SR (p m =0.5) SR (p m =0.25) NSC Values of the success rate for three different mutation rates and of the NSC for the 6-multiplexer problem using two different sets of operators to build the individuals. The fitness landscapes induced by these two sets of operators clearly have different difficulties for GP.

	{IF}	1	0.98	0.71	0
	{NAND}	0	0	0	-0.21

We are aware that the word "worsenable" does not exist in the English dictionary. Nevertheless we use it here as a contrary of "improvable", i.e. as something that cannot be worsened.