Measuring Neutrality of Fitness Landscapes
Based on the Nei’s Standard Genetic DistanceYoshiaki Katada1 , Kazuhiro Ohkura2 , and Kanji Ueda3
1

Graduate School of Science and Technology, Kobe University, Kobe, JAPAN2
Faculty of Engineering, Kobe University, Kobe, JAPAN
Phone/Fax: +81-78-803-6135
Email: {katada, ohkura}@rci.scitec.kobe-u.ac.jp
3
RACE (Research into Artifacts, Center for Engineering),
The University of Tokyo, Meguro, JAPAN
Phone: +81-3-5453-5887 Fax:+81-3-3467-0648
Email: ueda@race.u-tokyo.ac.jp

Abstract. In recent years, not only ruggedness but also neutrality has
been recognized as an important feature of a ﬁtness landscape for genetic
search. Since the traditional theories based on the schema theory are
not useful for problems including neutrality, new theoretical guidelines
should be developed for eﬀective genetic search. This research direction
has been introduced almost for ten years, but the progress is not very
fast. For instance, only a few methods have been proposed or tested
for measuring neutrality on the problem to be solved. In this paper, we
propose the use of the Nei’s standard genetic distance, which originatesfrom population genetics, for measuring the neutrality of a landscape.
Several computer simulations are conducted by using a standard genetic
algorithm in order to investigate the validity of the proposed approach.
The terraced NK landscape, which is a popular test function in this ﬁeld,
is adopted for a test function. The results suggest to us that the Nei’s
genetic distance in natural evolution is a reliable method for measuring
neutrality in artiﬁcial evolution after minor modiﬁcations.

1Introduction

Neutrality have attracted much research interest in recent years [1][2]. This feature, caused by highly redundant mappings from genotype to phenotype, is also
found in natural systems, and has been of particular interest to evolutionary theorists and molecular biologists [3]. Neutrality has been found in many real-world
applications of artiﬁcial evolution, such as evolution of neural network controllers
in robotics [4], on-chip electronic circuit evolution [5]. Landscapes which include
neutrality have been conceptualized as containing neutral networks. Harvey [6]ﬁrst introduced the concept of neutral networks into the GA community. Hedeﬁned it as follows: “A neutral network of a ﬁtness landscape is deﬁned as aset of connected points of equivalent ﬁtness, each representing a separate genotype: here connected means that there exists a path of single (neutral) mutations

Best
MeanFitness

Transient period

Equilibrium period

Generation

Fig. 1. Typical evolutionary dynamics on a ﬁtness landscape featuring neutral networks: Instead of being stuck in a local optimum, a population is exploring in thegenotype space during the equilibrium period.

which can traverse the network between any two points on it without aﬀectingﬁtness.”
The evolutionary dynamics on neutral networks can be classiﬁed into two
kinds of period, i.e., a transient period and an equilibrium period (Fig. 1) [7][8].
During an equilibrium period, a population is located around the dominant phenotype in the genotype space maintaining in a cluster, analogously to quasispecies [9], and moves along the neutral pathway until it ﬁnds a portal to a next
higher neutral network (Fig. 1). The discovery of the portal leads to a transientperiod which is expected to be very short compared to the equilibrium period.
This evolutionary dynamics is clearly diﬀerent from the traditional explanations
based on the schema theory.
In the GA community, the majority of ﬁtness landscape descriptions havebased on ruggedness and modality [10–12]. This is because GA practioners customarily avoid redundancy in the coding of problems for genetic search. However,Nimwegen et al. [7] suggested that the building block hypothesis[10][13] does nothold for systems that mainly show equilibrium periods. This means that the traditional theories based on the schema theory[10][13] are not useful for problems
including neutrality. If equilibrium periods seem dominative, ruggedness is notenough to measure the search diﬃculty. Another measure, i.e., neutrality is required.
To the best of our knowledge, the Smith’s fitness evolvability portraits [2]are only the method for measuring neutrality. This is deﬁned as the probability
that the oﬀspring ﬁtness is greater than or equal to the parent ﬁtness. In theirmeasurement, a certain distinctive characteristic deﬁned to be neutral between
two ﬁtness values must be set by GA practioners. This value has a great inﬂuenceon this measure, especially in the case that the ﬁtness is evaluated as a real value
or in a noisy environment. However, it has not been shown which distinctive
characteristic should be considered to be neutral.
According to Kimura’s neutral theory [3] and Ohta’s nearly neutral theory[14][15], the number of gene substitutions of each genotype increases with the increase of neutrality. In population genetics, there are several statistical methods

for estimating the number of gene substitutions. From the viewpoint of measuring neutrality, the number of gene substitutions could be an index of neutrality.
This idea would be beneﬁcial in artiﬁcial evolution because there is no need totreat any ﬁtness values.
This paper examines whether the Nei’s standard genetic distance is adequate
for measuring neutrality of ﬁtness landscapes. The next section describes theNei’s standard genetic distance. Section 3 applies the Nei’s genetic distance todescribe one of tunably neutral landscapes called the Terraced NK landscapeand shows the validity of the Nei’s genetic distance for measuring neutrality.
Section 4 discusses the condition that the Nei’s genetic distance can be used.
Conclusions are given in the last section.

2The Nei’s Standard Genetic Distance

Genetic distance is a term of population genetics used for estimating gene diﬀerences per locus between populations. Although there are several deﬁnitions for
this, the Nei’s standard genetic distance [16] is adopted in this paper.
The Nei’s standard genetic distance is deﬁned as follows. Consider two populations, X and Y . Let xik and yik be the frequencies of the k-th alleles (i =1, · · ·, N , k ∈ {1, 2} in the standard GA) in X and Y , respectively. The probability of identity of two randomly chosen genes is jxi = x2i1 + x2i2 in the population
22X, while it is jyi = yi1+ yi2
in the population Y . The probability of identityof a gene from X and a gene from Y is jxyi = xi1 yi1 + xi2 yi2 . The normalized
identity of genes between X and Y with respect to a locus is deﬁned asjxyi
Ii = √  .
jxi jyi(1)

It is equal to 1.0 if the two populations have the same alleles in identical frequencies, and 0.0 if they have no common alleles. The normalized identity ofgenes between X and Y with respect to the average in all loci is deﬁned asJXY(2)
I=√ √ ,JX JYNNNwhere, JX =i=1 jxi /N , JY =i=1 jyi /N and JXY =i=1 jxyi /N . The
genetic distance between X and Y is deﬁned as
D = − loge I,(3)

under the assumption that the mutation rate per locus is suﬃciently small. However, the above deﬁnition cannot be applied to the standard GA directly, because
it is assumed that a new allele always appears on a locus when a mutation occurs, while “back mutations [14]” frequently occur in the standard GA, due tothe binary coding scheme. Therefore, the genetic distance between the population at the initial generation and the one at the last generation is calculated

as:
Df inal =T−1
Dt,t+1(4)

1

where T is the number of the last generation and Dt,t+1 is the genetic distance
between the population in the t-th and the (t + 1)-th generation. The rate ofgene substitution is deﬁned as the genetic distance per generation.
Based on the studies of population genetics, the following hypotheses areneeded:(1) The number of substitutions increases with the increase of neutrality.
(2) The number of substitutions is largest when random sampling is applied asa selection method.
(3) The mutation rate per locus is small so that the above two expectations
hold.
The Nei’s genetic distance can be applied as the measure of neutrality in
artiﬁcial evolution as long as the above hypotheses hold.

3Neutrality in a Tunably Neutral NK Landscape

3.1

A Terraced NK LandscapeA terraced NK landscape was employed as the test function in our computer simulations. This is the tunably neutral landscape proposed by Newman et al. [17].
A terraced NK landscape has three parameters: N , the length of the genotype;K, the number of epistatic linkages between genes; and w, the contribution of alocus to the ﬁtness of the entire genotype.
The ﬁtness value is calculated as follows: The ﬁtness contribution of the ith locus, wi , is an integer generated randomly in the range 0 ≤ wi < F, i =1, · · ·, N . To calculate the ﬁtness, W , of a genotype, the ﬁtness contribution ofeach locus is averaged, and then divided by F − 1, normalizing W to the range
0.0 to 1.0. More formally:
W =N1wi .
N (F − 1) i=1(5)The neutrality of the landscape can be tuned by changing the value of F . The
neutrality of the landscape is maximized when F = 2, and is eﬀectively nonexistent as F → ∞.
3.2

Simulation Conditions

We applied two genetic algorithms: the standard GA (SGA) and the (randomsampling, q)-algorithm. The (random-sampling, q)-algorithm employs standard
bit mutation at the rate of q as the genetic operation and random samplingas a selection method where M oﬀsprings are sampled from M ancestors withreplacements. This model was used to investigate the eﬀect of random sampling
and mutation on the genetic distance and the rate of gene substitution of apopulation. This model is approximately equivalent with Kimura’s stochastic
genetic models to study random genetic drift and the expected time of ﬁxationof a mutant gene [3]. Kimura has suggested that the rate of gene substitution islargest when the selective advantage of a new mutation over the original allele
is zero except that the new mutation is deleterious in a small population.
Computer simulations were conducted using a population size of 50. The
SGA used standard bit mutation as the genetic operation. For both algorithms,
the per-bit mutation rate, q, was set at 0.008, based on the hypothesis (3) inSection 2. Crossover was not employed. Tournament selection was adopted for
the SGA. The tournament size was set at 2. Each run lasted 2,000 generations.
We conducted 50 independent runs for each problem under the landscape parameters, N = 20, K ∈ {0, 2, 6, 12, 19}, F ∈ {2, 3, 4, 6}. The results were averaged
over 50 runs.
3.3

Simulation Results

In this experiment, the number of substitutions increased approximately linearlyover generations in all runs. Therefore, the rate of substitution is shown byusing the method of least squares on the results of all runs because the rate ofsubstitution is equivalent to the gradient of the number of substitutions overgenerations.
Table 1 shows the rate of substitution for the SGA. Notice ﬁrst that the rateof substitution increased with the decrease of F with all Ks. This means thatthe rate of substitution increases with the increase of neutrality. This tendency
is consistent with the neutral theory. Second, the rate of substitution decreased
with the increase of K with all F s. This means that not only neutrality but
also ruggedness have an inﬂuence on the rate of substitution. This is consistent
with Ohta’s results for NK landscapes with weak selection based on the nearly
neutral theory, where the number of substitutions decreases with the increase ofK [15, 18].
The rate of substitution for (random-sampling, q)-algorithm was 0.004576.
Thus, the rate of substitution for (random-sampling, q)-algorithm was always
larger than any others for the SGA with K and F .
Table 1. The rate of substitution for the SGA with q = 0.008@KF@@
234602612190.002042 0.000666 0.000220 0.000131 0.0001060.001307 0.000421 0.000173 0.000102 0.000104
0.001063 0.000318 0.000130 0.000099 0.000087
0.000738 0.000235 0.000128 0.000090 0.000087

Relative rate of substitution

0.5

F=2
F=3
F=4
F=60.40.3
0.2
0.1
0.00246810 12 14 16 18KFig. 2. Relative rate of substitution for the SGA and the (random-sampling, q)algorithm with q = 0.008

Relative rate of substitution

In order to summarize the results obtained in this experiment, the relative
rate of substitution, γ, for the SGA and the (random-sampling, q)-algorithm wascalculated. This is formulated as follows: γ = α/α random, where α is the rateof substitution for the SGA and αrandom is the one for the (random-sampling,q)-algorithm. When γ < 1.0, the rate of substitution for the SGA is less thanthe one for the (random-sampling, q)-algorithm. When γ > 1.0, the rate of substitution for the SGA is more than that for the (random-sampling, q)-algorithm.
The results are shown in Fig. 2. We can recognize the tendencies for K and F
more clearly. Thus, the hypothesis (1) and (2) hold when the landscape includes
neutrality.
In real-world problems, the increase of ruggedness of a ﬁtness landscape ispredicted by the decrease in the correlation length [2, 11]. Fig. 3 shows the relative rate of substitution at each correlation coeﬃcient corresponding to K with
all F s in our results, where the correlation coeﬃcient was calculated as a ﬁtness
correlation between genotypes at Hamming distance 1 [12]. Thus the relative rateof substitution predicts the increase of neutrality for F s around each correlationcoeﬃcient.

0.4
0.3

F=2
F=3
F=4
F=60.2
0.1
000.1

0.2

0.3

0.4

0.5

0.6

Correlation

Fig. 3. Relative rate of substitution as a function of the correlation coeﬃcientRelative rate of substitution

1.2
1.1
1.0
F=2
F=3
F=4
F=60.90.8
02468

10 12 14 16 18KFig. 4. Relative rate of substitution for the SGA and the (random-sampling, q)algorithm with q = 0.1

4Discussion

Additional computer simulations were conducted to observe the transition of theNei’s genetic distance in the condition of a large mutation rate, which induces
the inconsistency with the hypotheses at Section 2. The simulation settings werethe same as Section 3.2 except that q was set at 0.1 for the two algorithms.
The results are shown in Fig. 4. Surprisingly, γ increased with the increase of
K with all F s. In addition to this, no signiﬁcant diﬀerences were found between
the graphs of diﬀerent F s.
The rate of substitution for the SGA was higher than that for the (randomsampling, q)-algorithm when K > 6, because γ > 1.0 with all F s. This would
be caused by the eﬀect of the larger mutation rate than the error threshold[7]which changes artiﬁcial evolution into a random search.
From the above, we conﬁrmed that the Nei’s genetic distance can be used aslong as the mutation rate is suﬃciently small compared with the error threshold.

5Conclusions

In this paper, we have proposed the use of the Nei’s standard genetic distance,
which treats only genotype data, for measuring neutrality of a landscape, andshown the validity of this approach by applying it to the Terraced NK landscapes.
The characteristic of the rate of substitution estimated by the Nei’s genetic
distance can be summarized as follows:
When the mutation rate per locus is small,– The number of substitutions is largest when random sampling is appliedwith mutation.
– The number of substitutions increases with the increase of neutrality.
– The number of substitutions decreases with the increase of ruggedness where
the landscape includes neutrality.
Our results suggest that the genetic distance can provide a guideline for measuring neutrality and ruggedness. As for the next step, we will investigate how
well our method applies to real-world problems whose ﬁtness landscape includes

neutral networks, such as the evolution of artiﬁcial neural networks for robotcontrol.

References
1. Ebner, M., Langguth, P., Albert, J., Shackleton, M., Shipman, R. (2001) ”On
Neutral Networks and Evolvability,” In Proceedings of the 2001 IEEE Congress on
Evolutionary Computation: CEC2001, IEEE Press pp. 1–8.
2. Smith, T. Husbands, P. Layzell, P. and O’Shea, M. (2002) ”Fitness Landscapesand Evolvability,” Evolutionary Computation, 10(1):1-34.
3. Kimura, M. (1983) ”The Neutral Theory of Molecular Evolution,” Cambridge University, Press, New York.
4. Harvey, I. (1997) ”Artiﬁcial Evolution for Real Problems,” In Gomi, T., editor,
Evolutionary Robotics: From Intelligent Robots to Artificial Life (ER’97), AAI
Books.
5. Thompson, A. (1996) ”An Evolved Circuit, Intrinsic in Silicon, Entwined withPhysics,” In Proceedings of the first International Conference on Evolvable Systems:
From Biology to Hardware, pp. 390–405.
6. Harvey, I., Thompson, A. (1996) ”Through the Labyrinth Evolution Finds a Way:A Silicon Ridge,” In Proceedings of the first International Conference on Evolvable
Systems: From Biology to Hardware, pp. 406–422.
7. Nimwegen, E., Crutchﬁeld, J., and Mitchell, M. (1999) ”Statistical dynamics of theroyal road genetic algorithm,” In Theoretical Computer Science, Vol. 229, No. 1,
pp. 41-102.
8. Barnett, L. (2001) ”Netcrawling - Optimal Evolutionary Search with Neutral Networks,” In Proceedings of the 2001 IEEE Congress on Evolutionary Computation,
pp. 30–37.
9. Eigen, M., McCaskill, J. and Schuster, P. (1989) ”The Molecular Quasi-species,”
In Advances in Chemical Physics, 75, pp. 149-263.
10. Goldberg, D. (1989) ”Genetic Algorithms in Search, Optimization and Machine
Learning,” Addison-Wesley.
11. Weinberger, E. D. (1990) ”Correlated and uncorrelated ﬁtness landscapes and how
to tell the diﬀerence,” Biological Cybernetics, 63:325-336.
12. Manderick, B., Weger, M. and Spiessens, P. (1991) ”The Genetic Algorithm andthe Structure of the Fitness Landscape,” In Belew, R. and Booker, B, editors,
Proceedings of the Fourth International Conference on Genetic Algorithms, pp.
143–150, Morgan Kaufmann, San Mateo, California.
13. Holland, J. H. (1975) ”Adaptation in Natural and Artiﬁcial Systems,” Universityof Michigan Press.
14. Ohta, T. (1992) ”The nearly neutral theory of molecular evolution,” In Annu. Rev.
Ecol. Syst., 23:263-286.
15. Ohta, T. (1998) ”Evolution by nearly-neutral mutations,” In Genetica, 102/103,pp. 83-90.
16. Nei, M. (1972) ”Genetic Distance between Populations,” In The American Naturalist, Vol. 106, pp. 283-292.
17. Newman, M. and Engelhardt, R. (1998) ”Eﬀect of neutral selection on the evolution of molecular species,” In Proceedings of the Royal Society of London B,Morgan Kaufmann, 256, pp. 1333-1338.
18. Ohta, T. (1997) ”Role of random genetic drift in the evolution of interactive systems,” In Journal of Molecular Evolution, Vol. 44, pp. S9-S14.