
## 2. The Autocorrelation Of Evolvability

Evolvability **is defined by Altenberg [1] as "the ability of**
random variations to sometimes produce improvement". As enlighten by Turney [5] the concept of evolvability is difficult to define. As he puts it: "if s and s
′
are equally fit, s **is more**
evolvable than s
′
if the fittest offspring of s **is more likely**
to be fitter than the fittest offspring of s
′
**". Following this**
idea the evolvability of a solution is defined by a function ef that assigns to every s ∈ S **a real number which measure the**
evolvability. For examples, the evolvability function could be the maximum fitness from the neighborhood ef(s) = max{f(s
′

) | s
′

∈ V(s)}.

We define the autocorrelation of evolvability **for a neutral**
network N **as the autocorrelation function of evolvability on**
neutral networks.

The autocorrelation of evolvability **on the neutral network**
N is the autocorrelation of series (ef(s0), ef(s1)**, . . .**)
where (s0, s1, . . .**) is a neutral random walk on** N.

A neutral random walk is a series of solutions (s0, s1**, . . .**)
such as si+1 ∈ V(si) and f(si+1) = f(si**). To extend this**
measure to the set of all neutral networks, the average of autocorrelation coefficient is computed. Several choices could be made to define evolvability function; in particular we call autocorrelation of maximal evolvability **the autocorrelation when the evolvability is the maximum fitness from the**
neighborhood of a solution.

The evolvability gives the fitnesses of neutral network in the neighborhood. For example, the maximum evolvability of a solution is the fitness of the higher NN in the neighborhood. The autocorrelation of evolvability allows to describe the distribution of neutral networks around. If the correlation is large, the fitness in the neighborhood of a NN is distributed regularly, whereas if the correlation is low, the NNs around a NN is randomly distributed.

## 3. First Results On The Max-K-Sat Problem

In the following we present the first measures of autocorrelation of evolvability. The MAX-k-SAT is defined from the SAT optimization problem. SAT is a decision problem that asks whether a binary tuple can be found that satisfies all clauses in normal conjunctive form. Many studies deal with the solution space of the SAT problem [3], such phase transistion arround the threshold αc **defined as the ratio between the number of clauses and the number of variables.**
For k = 3, αc **is equal to 4**.3.

The experiments are led in the same way as for preview landscapes with random instances of MAX-3-SAT. The number of variables is set to N = 16 and N **= 64, the number**
of literals by clause is k **= 3 and the number of clauses** m describe respectively the sets {39, 59, 64, 69, 74, 79, 99} and
{200, 250, 265, 275, 285, 300, 350}. The average neutral degree decreases when m **increases.** The figure 1 shows the correlation length of maximal evolvability. For all the parameters, the correlation is significant.

The correlation length is around 2 for N **= 16 and around 5**
for N **= 64. For all the value of the number of clauses, the**
autocorrelation functions are nearby and the variations of correlation length are weak according to the parameter α.

The correlation decreases slowly according to the number of clauses, which is linked to the neutrality. The autocorrelation of maximal evolvability do not shows a phase transition around the threshold αc = 4.**3. The neutral networks are**
not randomly distributed in the fitness landscapes. Those first experiments show that the autocorrelation of evolvability is one of characteristic of applicative neutral fitness landscapes.

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

## 4. Conclusion

From the metaphor of neutral fitness landscapes, the neutral networks (NN) are the plateaus. For each NN, we have defined the autocorrelation function of evolvability. The first studies on applicative MAX-SAT problem has showed a new characteristic of those problem which can be compared to the preview additive landscapes.

The autocorrelation of evolvability is an useful measure which highlight a new characteristic of neutral fitness landscapes which could be study in real optimization problems.

In spite of a lack of differential between fitness in a NN,
evolvability could be exploit to guide the search process on a network. Futures works could take into account this information to design new metaheuristics adapted to neutral fitness landscapes.

5. REFERENCES
[1] G. Wagner. Complexes adaptations and the evolution of evolvability. In Evolution**, pages 967–976, 1996.**
[2] M. Kimura. **The Neutral Theory of Molecular**
Evolution**. Cambridge University Press, Cambridge,**
UK, 1983.

[3] M. Mezard and R. Zecchina. The random k-satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E**, 66(056126), 2002.**
[4] P. F. Stadler. Fitness landscapes. In M. L¨assig and Valleriani, editors, **Biological Evolution and Statistical** Physics, volume 585 of Lecture Notes Physics**, pages**
187–207, Heidelberg, 2002. Springer-Verlag.

[5] P. D. Turney. Increasing evolvability considered as a large scale trend in evolution. In P. Marrow and al, editors, **GECCO'99 , Workshop Program on**
evolvability**, pages 43–46, 1999.**
[6] E. D. Weinberger. Correlated and uncorrelatated fitness landscapes and how to tell the difference. In Biological Cybernetics, pages 63:325–336, 1990.