Estimating the Degree of Neutrality in Fitness Landscapes by
the Nei’s Standard Genetic Distance– An Application to Evolutionary Robotics –Yoshiaki Katada, Setsunan University, and Kazuhiro Ohkura, Hiroshima University

Abstract— In recent years, not only ruggedness but also
neutrality has been recognized as an important feature of afitness landscape for genetic search. As it has been reported thatthe evolutionary dynamics on a fitness landscape with neutrality
is clearly different from the canonical explanations, ruggedness
alone might be inadequate describing it. Another measure,i.e., neutrality is required. In this paper, we proposed the useof the Nei’s standard genetic distance, which originates from
population genetics, for estimating the degree of neutrality infitness landscapes after minor modifications. Several computer
simulations were conducted with an evolutionary robotics problem in order to investigate the validity of the proposed approach.
The results suggest to us that the Nei’s genetic distance is areliable method for estimating the degree of neutrality on realworld problems.

I. I NTRODUCTION
In early works of the theoretical GA community, problem
difficulties for a GA have been discussed in terms of thegeography of a fitness landscape: isolation, deception andmultimodality. Their factors affecting the performance of
the GA to solve optimization problems are still contentious
issues. However, several counterexamples on the latter two
factors were found, showing that they are neither necessary
nor sufficient to make a problem difficult [1][2][3].
Another attempt to characterize difficulty has been doneby measuring the feature of a fitness landscape, epistasis or
ruggedness. Most of the works in this area are based on thecorrelation between a parent fitness and the offspring one todescribe a fitness landscape [1][4][5][6][7][8]. Therefore, it
is derived from the average of fitness correlations between
parents and offspring or the fitness distance autocorrelation
function obtained by using a random walk. In the GA
community, the majority of fitness landscape descriptions
have based on ruggedness.
In recent years, the existence of problem domains has beenreported where evolutionary dynamics is clearly different
from the canonical explanations based on the schema theory
and the building block hypothesis [9][10]. Those kinds ofproblem, such as the evolution of neural network controllers
in robotics [11][12][13][14] and on-chip electronic circuit
evolution [15][16][17], mainly show equilibrium period, neutral evolution in their evolutionary dynamics. This characterYoshiaki Katada is with the Faculty of Engineering, Setsunan University,
17-8 Ikeda-nakamachi, Neyagawa, Osaka 572-8508, JAPAN (phone/fax: +81
728 39 9148; email: katada@ele.setsunan.ac.jp).
Kazuhiro Ohkura is with the Graduate School of Engineering, Hiroshima
University, 1-4-1 Kagamiyama, Higashi-Hiroshima, Hiroshima 739-8527,
JAPAN (email: kohkura@hiroshima-u.ac.jp).

istic is caused by highly redundant mappings from genotype
to phenotype or phenotype to fitness. With these kinds ofproblems, redundancy is inevitable although it is customaryamong GA practioners deliberately to avoid redundancy inthe genetic coding of artificial evolution problems. Therefore,ruggedness alone is not enough to measure the search difficulty if equilibrium periods seem dominative in the processof evolution.
To the best of our knowledge, statistical measurementswith respect to neutrality are found only in the references[16][18]. Vassilev et al., studied the structure of on-chipelectronic circuit evolution landscapes [16]. They proposed
the information analysis of fitness landscapes, which isdefined over a time series obtained by a walk on a landscape. Their entropic measure of the time series makes it
possible to confirm the existence of neutrality in a landscapeand which feature, neutrality or ruggedness is dominant in
the landscape. Smith et al., [18] proposed a method formeasuring neutrality in a landscape as one of the fitness
evolvability portraits. This is defined as the probability that
an offspring fitness is equal to the parent fitness. In theirmeasurement, a certain distinctive difference, ε, between two
fitness values considered to be neutral must be set by GA
practioners, that is, |fx − fy | ≤ ε (fx is a parent fitness
and fy is the offspring one). However, the reference [16]has reported that Smith’s measure is very sensitive to ε.
Especially in the case that the fitness is evaluated as a realvalue or in a noisy environment, a great influence of thevalue on the measure of neutrality would be predicted. For
these problems, Smith proposed the use of neutral fitness
band [12] or the significance level for the Student t-test [19]as the value. However, no significant difference between two
fitness landscapes was detected although introducing suchstatistical neutrality [19]. This implies the difficulty to use
fitness data for measuring neutrality.
Population geneticists have been trying to explain thechange of gene frequency in a population. That is, they haveused genotype data for their explanations. Recently, we havebeen motivated by this to investigate the characteristics of the
Nei’s standard genetic distance[20], which is one of statisticalmethods for estimating gene differences between populationsin population genetics, in artificial evolution [21]. The results
show some consistencies with the neutral theory [22] and thenearly neutral theory [23][24] in population genetics.
The characteristics of the Nei’s standard genetic distancecan be summarized as follows:When the mutation rate per locus is sufficiently small,
1) The genetic distance increases approximately linearlyover generations in fitness landscapes with neutrality.
2) The genetic distance increases with the increase ofneutrality.
3) The genetic distance decreases with the increase ofruggedness in landscapes with neutrality.
4) The genetic distance decreases with the increase of the
population size.
From the viewpoint of measuring neutrality, the characteristics 1) and 2) show the possibility of a genetic distanceas an index of neutrality, while the characteristics 3) shows
the difficulty to apply the genetic distance directly to themeasure of neutrality.
This paper investigates how well the Nei’s genetic distanceapplies to estimate the degree of neutrality in fitness landscapes. The greatest advantage of our approach is that thedifficulty to use fitness data for measuring neutrality, which
was mentioned above, need not to be taken into accountbecause it uses genotype data for it. The paper is organized asfollows. The next section describes the Nei’s standard genetic
distance. Section III applies the Nei’s genetic distance totunably neutral landscapes and shows the characteristics ofthe genetic distance. Section IV shows some guidelines for
estimating the degree of neutrality in a fitness landscape on areal-world problem as well as investigates the validity of the
proposed approach on a robot control problem. Conclusions
are given in the last section.

Genetic distance is a term of population genetics used for
estimating gene differences per locus between populations.
Although there are several definitions for this, the Nei’sstandard genetic distance [20] is adopted in this paper.
The Nei’s standard genetic distance is defined as follows.
Consider two populations, X and Y . Let xik = nik /M andyik = nik /M be the frequencies of the k-th alleles (i =1, · · · , N , N , the length of the genotype, k ∈ {1, 2} in abinary coded GA, nik , the number of the k-th allele, M , thepopulation size) in X and Y , respectively. The probability ofidentity of two randomly chosen genes is jxi = x2i1 + x2i2 in22+yi2
in the population
the population X, while it is jyi = yi1
Y . The probability of identity of a gene from X and a genefrom Y is jxyi = xi1 yi1 + xi2 yi2 . The normalized identityof genes between X and Y with respect to a locus is definedasjxyi
Ii = √  ,(1)
jxi jyiwhere, Ii = 1.0 if the two populations have the samealleles in identical frequencies, and Ii = 0.0 if they have nocommon alleles. The normalized identity of genes between
X and Y with respect to the average in all loci is defined as
JXY
√ ,
JX JY

D = − loge I.

(3)

The above definition 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 “backmutations [23]” frequently occur in the standard GA, due tothe binary coding scheme. Therefore, the genetic distance ofGAs between the population at the initial generation and theone at the last generation is calculated as:D(T ) =

T−1


Dt,t+1(4)t=1where T is the number of the last generation and Dt,t+1 isthe genetic distance between the population in the t-th andthe (t + 1)-th generation.
III. T HE N EI ’ S S TANDARD G ENETIC D ISTANCE IN
T UNABLY N EUTRAL NK L ANDSCAPESIn this section, we apply the standard GA (SGA)[25]
to tunably neutral landscapes and obtain the genotype datafrom it. Considering to apply to real-world problems, weinvestigate the characteristics of the Nei’s genetic distancefor ruggedness measured by a canonical method.
A. Terraced NK Landscapes

II. T HE N EI ’ S S TANDARD G ENETIC D ISTANCE

I=√

N
N
where, JX = i=1 jxi /N , JY = i=1 jyi /N and JXY =N
i=1 jxyi /N . The genetic distance between X and Y is
defined as(2)

A terraced NK landscapes and an extended one were
employed as test functions in our computer simulations. The
former is the tunably neutral NK landscape (TNK) proposed
by Newman and Engelhardt [26] and the latter is the TNKp
landscape which we extended to increase neutrality of TNK.
A terraced NK landscape has three parameters: N , thelength of the genotype; K, the number of epistatic linkages
between genes; and v, the contribution of a locus to thefitness of the entire genotype. The fitness value is calculated
as follows: The fitness contribution of the i-th locus, vi ,is an integer generated randomly in the range 0 ≤ vi <F, i = 1, · · · , N . To calculate the fitness, V , of a genotype,the fitness contribution of each locus is averaged, and thendivided by F − 1, normalizing V to the range 0.0 to 1.0.
More formally:
V =

N

1
vi .
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 effectively non-existent as F → ∞.
TNKp is an extended form of TNK for F = 2 in order toincrease neutrality of TNK. For TNKp, vi in Equation (5) is
set at 0 with the probability, P (0 ≤ P ≤ 1), following theway to involve neutrality in NKp fitness landscapes [27].

B. Simulation Conditions
Computer simulations were conducted using populationsof size 50 by varying the landscape parameters. We applied
the SGA. The SGA used standard bit mutation as thegenetic operation. The per-bit mutation rate, q, was set at0.008, based on the assumption in Section I. Crossover
was not employed, following Nimwegen’s suggestion [10].
Tournament selection was adopted. The tournament size wasset at 2 because the SGA generally prefers low selection
pressure. A generational model was used. Each run lasted
2,000 generations. We conducted 50 independent runs foreach problem under the landscape parameters, N = 20,
K ∈ {0, 2, 6, 12, 19}, F ∈ {2, 3, 4}, P ∈ {0.9, 0.99}. The
results were averaged over 50 runs. As mentioned in Section
I, the genetic distance increases approximately linearly overgenerations in fitness landscapes with neutrality. Therefore,
the gradient of the genetic distance over generations, α, iscalculated as an index of increase of the genetic distance inthis experiment by using the method of least squares on the
results of all the runs.
C. Simulation Results
1) Measure of Ruggedness: In real-world problems,ruggedness of a fitness landscape is predicted by the fitness
correlation [5][18]. In this paper, therefore, the Smith’smeasurement [18] is employed for the measure of ruggedness
because its fitness correlation can be expressed as a scalarvalue. The average fitness of the offspring solutions, called
the Smith’s Eb , is given byg∈G(k) V (g)(6)
Eb (k) =|G(k)|
where, G(k) is the set of offspring from parents with thefitness k, g is an offspring genotype and V (· ) is the fitness
function. Figure 1 show Eb s in TNK for F = 2. It isfound that the gradient, Ėb , decreases with the increase of
K. It has been known that this gradient is independent ofF (neutrality), that it is proportional to the autocorrelation

0.8
0.6

IV. E STIMATING THE D EGREE OF N EUTRALITY IN
E VOLUTIONARY ROBOTICS F ITNESS L ANDSCAPES
A. Guidelines for Estimating the Degree of Neutrality
The procedure for estimating the degree of neutrality in afitness landscape on a real-world problem can be summarized
as follows:i) Confirm the existence of neutrality in a fitness landscape on a real-world problem by investigating transitions of the genetic distance over generations.
ii) Calculate a point, (Ėb , α), from runs on the real-world
problem.
iii) Calculate a set of Ėb -α curves in test functions withdifferent levels of neutrality and ruggedness.
iv) By using a set of Ėb -α curves as baselines, judge
where a point, (Ėb , α), obtained from the real-world
problem locates in the graph of (Ėb , α). Then estimate
indirectly the degree of neutrality on the real-world
problem.
The reason why the procedure iii) and iv) are conductedis that the genetic distance is affected by both neutrality andruggedness as confirmed in Section III. TNK and TNKp
are adopted as test functions for obtaining a set of Ėb α curves. The landscape parameters of TNK(p) should be
decided at the procedure iii) for conducting the procedure iv).

4.0e-03

K=0
K=2
K=6
K=12
K=19

3.0e-03
α

Average mutant fitness

1.0

function for the mutation operator applied, and that Ėb  1.0
when K = 0 and Ėb  0.0 when K = N − 1.
2) Characteristics of the Genetic Distance: Figure 2
shows α at each correlation, Ėb , corresponding to K with all
F s and P s in TNK(p). It is confirmed that α increased with
the increase of Ėb for all F s and P s, and increased withthe decrease of F and the increase of P for all Ėb s. These
are consistent with the results obtained in [21]. As a result, a
set of points (Ėb , α) forms a curve, which increases with theincrease of the correlation when F and P are constant. A setof curves is also found with different levels of neutrality. This
demonstrates that α would predict the increase of neutrality
combined with the measure of ruggedness.

2.0e-030.4

1.0e-03

0.2

0.0e+00
0.0

0.0
0.0

0.2

0.4
0.6
Original fitness

0.8

1.0

Fig. 1. Expected offspring fitness value over all parent fitness values in
TNK for F = 2

P=0.99P=0.9
Fig. 2.

0.2

0.4
0.6
Correlation
F=2
F=3

0.8

F=4

α as a function of the correlation (E˙b )1.0

Addition to this, the parameters of the GAs (a mutation rate,
a population size, a tournament size, etc.) on test functions
should be the same as those on a real-world problem due tothe characteristics of the Nei’s standard genetic distance.
B. The Task and the Fitness Function
The control task used in this experiment was motion pattern discrimination [28][29], and is based on a task originallyimplemented by Beer [30]. The agent must discriminate
between two types of vertically falling object based on theobject’s period of horizontal oscillation; it must catch (i.e.,
move close to) falling objects that have a long period whilst
avoiding those with a short period (see Fig. 3). An arrayof proximity sensors allow the agent to perceive the falling
objects. If an object intersects a proximity sensor, the sensor
outputs a value inversely proportional to the distance between
the object and the agent. The agent can move horizontally
along the bottom of the arena. In our experiment, the agentof diameter 30 had 7 proximity sensors of maximum range
220 uniformly distributed over a visual angle of 45 degrees.
The horizontal velocity of the agent was proportional to thesum of the opposing horizontal forces produced by a pair ofeffectors. It has maximum velocity of 8. Each falling object
was circular, with diameter 30, and dropped from the top of
the arena with a vertical velocity of 4, a horizontal amplitudeof 30 and an initial horizontal offset of ±50. An object’s
horizontal velocity was ±10 (12 steps in a period) for a long
period and ±30 (4 steps in a period) for a short period.
The performance measure to be maximized was as follows:
F itness = 1000

N umT
rialsi=1

Hi
N umT rials(7)

where Hi = 1 − di for a long period and Hi = di for ashort period, di = 1 when hdi > 60 and di = hdi /60 whenhdi ≤ 60, hdi is the final horizontal distance between thecenter of the agent and the object, and N umT rials is thenumber of trials for an individual (8 trials for each period).
C. Simulation Conditions
For this experiment, the agent controller was a spike
response model network [31], which is a form of PulsedLong Period[12 Steps]

Short Period[4 Steps]

Neural Network (PNN) with 7 sensory neurons, 2 fullyinterconnected motor neurons and Nh fully interconnected
hidden neurons, where Nh ∈ {0, 1, 5, 10, 15} in order toestimate and compare the features among the fitness landscapes with each Nh . The network’s connection weights
and the firing threshold for each neuron were geneticallyencoded and evolved. The total number of parameters isequal to {20, 33, 105, 240, 425} corresponding to each Nh .
The parameters were mapped linearly with the following
ranges: connection weights ω ∈ [−1.0, 1.0], thresholds θ ∈[0.0, 3.9]. The parameters of the neurons and synapses wereset as follows: τm = 4, τs = 10, ∆ax = 2 for all neurons andall synapses in the network following the recommendations
given in [32].
Computer simulations were conducted using populationsof size 50. Each individual was encoded as a binary stringwith 10 bits for each parameter. Therefore, the total length of
the genotype was L = {200, 330, 1050, 2400, 4250} for each
Nh . The SGA were adopted to evolve PNN parameters. The
genetic operation for the SGA was standard bit mutation.
Based on the assumption of the Nei’s genetic distance inSection I, two types of mutation rate were set as follows:a)q = 1/LNh =15 , which is constant for each landscape, corresponding to 1/L for the longest genotype.
b)
q = 1/L, following the recommendation in theevolutionary computation community.
According to the procedures in the previous subsection,
all the parameters of the SGA must be the same among
fitness landscapes to compare the features. Thus, the otherparameters were set as follows. Tournament selection was
adopted. Elitism was applied. The tournament size was set
at 2. Each run lasted 6,000 generations. We conducted 10
independent runs for each landscape.
As the test functions, TNK and TNKp were adopted. A
set of landscape parameters of TNK(p) at the procedure iii)
was decided in the preliminary computer simulations withthe same SGA parameters as those of the PNNs. In thisexperiment, they were set at the same values as those of
TNK(p) in Section III. The reason to conduct the procedureiv) in these conditions is explained as follows: In the case ofa) there are cases in which it is not possible to estimate andcompare the degree of neutrality between fitness landscapeseven if combined with the measure of ruggedness (will be
described in the next subsection), and in the case of b) there
is no theoretical meaning to compare directly the featuresof the fitness landscape of the PNNs due to the different
mutation rates.
D. Simulation Results

Catch

Avoid

Catch? Avoid?

Fig. 3. Experimental setup for the discrimination of the motion patterns.
Two kinds of period used in the discrimination experiments (left) and theagent in the arena with its array of the proximity sensors (right).

a) q = 1/LNh =15
Figure 4 shows the genetic distance at each generation for
Nh = 15. The approximately linear increases were observedin all runs. For other Nh s, the same transition were observed.
From the results obtained in [21], this might indicate thepresence of neutrality in the fitness landscape of the PNN.

0.00016

1.0
0.000140.8
0.6

αGenetic distance

1.2

0.000120.4
0.000100.2
0.0

0.0000801000 2000 3000 4000 5000 6000

0
1
5
10 15
Num. of hidden neurons (Nh)Generation
Fig. 6.

Fig. 4. Genetic distance at each generation for the SGA with q = 1/L
for Nh = 15 in 10 runs

2.0e-04
Nh=15

1.00

α

1.5e-04

0.95
Correlation

α for each Nh at q = 1/LNh =15

Nh=11.0e-04

Nh=10
Nh=5

Nh=0

5.0e-050.90

0.0e+00
0.7

0.85

0.8

0.9

1.0

Correlation
0.80
0
1
5
10
15
Num. of hidden neurons (Nh)Fig. 5.

Correlation (E˙b ) for each Nh at q = 1/LNh =15

Thus, the gradient of the genetic distance over generations,α, is shown by using the method of least squares on the
results of all the runs in the following parts.
Figure 5, 6 and 7 show the features of the fitness landscapefor each Nh . Figure 5 plots the correlation, Ėb , for each Nh .
In this experiment, the correlation increased with the increaseof Nh except of Nh = 15. That is, ruggedness decreased
with the increase of Nh . In Figure 6, α increased with theincrease of Nh . When the fitness landscape for Nh = 1 wascompared with the one for Nh = 0, there was no significant
differences in the correlation but α increased so much. For
another instance, when the fitness landscape for Nh = 15
was compared with the one for Nh = 10, the correlation
decreased but α increased. In these cases, the increase ofneutrality can be estimated based on the results obtained in[21]. Note that the increase of neutrality cannot be estimatedeither when the fitness landscape for Nh = 5 was comparedwith the one for Nh = 1 or when the fitness landscapefor Nh = 10 was compared with the one for Nh = 5,
because the increase of α coincided with the increase of thecorrelation.
By using the Ėb -α curves obtained in TNK(p), where FNN
P=0.99

P=0.9
F=2

F=3
F=4

Fig. 7. α as a function of the correlation (E˙b ) for each Nh and TNK(p)at q = 1/LNh =15

and P are constant for each curve, as baselines, the degreeof neutrality in the landscapes for all Nh s were estimatedindirectly (Figure 7). The points, (Ėb , α), for Nh = 0 and
Nh = 1 locate between the Ėb -α curves for P = 0.99 and
P = 0.9. The point for Nh = 1 is nearer to the curve for
P = 0.99 than the point for Nh = 0. The points for Nh = 5
and Nh = 15 locate on the curve for P = 0.9. The points
for Nh = 10 locates between the the curves for P = 0.9 andF = 2. Therefore, we confirmed that neutrality increased inorder of Nh = 10 → {5, 15} → 0 → 1.
In the cases of Nh = 0 → 1, 10 → 15, the increasesof neutrality were observed. These are consistent with theresults of the direct comparison between the landscapes
mentioned above. Additionally, the decreases of neutrality
were also observed in the cases of Nh = 1 → 5, 5 → 10
although it was not possible to estimate them by the directcomparison.
Figure 8 shows the maximum fitness at each generation
for Nh . Except of Nh = 1, the fitness increased faster as
the decrease of Nh , that is, the decrease of the genotypic
search space. The poor performance in the SGA for Nh = 1
cannot be predicted by the comparison with Nh = 0 only on

1000
Nh=0

Fitness

900
800
700

Nh=5
Nh=10
Nh=15
Nh=1

600
500
0

1000 2000 3000 4000 5000 6000
Generation

Fig. 8.

Maximum fitness at q = 1/LNh =15

the correlation in Figure 5. But it would be predicted by theincrease of neutrality observed in Figure 7 where equilibrium
periods were more dominative in the process of evolution.
b) q = 1/L
Figure 9 plots the correlation, Ėb , for each Nh . As observedin a), the correlation increased with the increase of Nh except
of Nh = 15. Because of different q among the landscapes,
the degree of neutrality in the landscapes for all Nh s canbe estimated indirectly by using the Ėb -α curves obtained in
TNK(p) (Figure 10). It was observed that neutrality increased
in order of Nh = 10 → 5 → {1, 15} → 0.
Figure 11 shows the maximum fitness at each generation
for Nh . The fitness increased faster as the decrease of Nh ,that is, the decrease of the genotypic search space. This
would be explained as follows; In the process of evolution, noerror threshold effects were observed 1 . This implies that theeffective mutation rate at q = 1/L would be below the error
threshold under each condition [29][34][35]. In addition,
1 Generally, an error threshold sets the upper limit for a mutation rate thatwill enable efficient search [10][27][33].

1.00

Correlation

0.95
0.90
0.85
0.80
0
1
5
10
15
Num. of hidden neurons (Nh)Fig. 9.

Correlation (E˙b ) for each Nh at q = 1/L

ruggedness were not so high in this problem (Figure 9)
Therefore, neutrality of the landscapes would not explicitly
have any influences on the performances of the SGA but thesize of the genotypic search space would have influences on
them.
From the viewpoint of the structure of evolutionary artificial neural networks, it was confirmed by the proposed
approach that the number of hidden neurons have a great
influence on the features of the fitness landscape of neuralnetworks.
V. C ONCLUSIONSIn this paper, we proposed the use of the Nei’s standard
genetic distance, which originates from population genetics,
for estimating the degree of neutrality in fitness landscapes
after minor modifications. We showed the guidelines to apply
our approach to a real-world problem. Several computer
simulations were conducted with an evolutionary robotics
problem in order to investigate the validity of the proposed
approach. Our results can be summarized as follows:• The existence of neutrality in an evolutionary robotics
fitness landscape was confirmed by investigating transitions of the genetic distance over generations.
• The proposed method can estimate and compare indirectly the degree of neutrality in the fitness landscapesby using the features of the fitness landscape of test
functions as baselines.
These results suggest the validity of the proposed approach. By using this, we might expect to explain evolutionary dynamics on problems where they have not been
explained by canonical fitness landscape descriptions.
This evolutionary robotics problem has redundant mappings from phenotype to fitness. Future work will investigate
whether our approach is applicable to real-world problems
which are expected to have redundant mappings from genotype to phenotype [36][37][38][39].
R EFERENCES[1] T. Jones and S. Forrest, “Fitness distance correlation as a measure of
problem difficulty for genetic algorithms,” Proc. the Sixth International
Conference on Genetic Algorithms, Edited by L. Eshelman, San Mateo,
California, pp. 184–192, 1995.
[2] J. Horn and D. E. Goldberg, “Genetic algorithm difficulty and themodality of fitness landscapes,” Foundations of Genetic Algorithms 3,
Edited by L. D. Whitley and M. D. Vose, San Francisco, CA: Morgan
Kaufmann, pp. 243–269, 1995.
[3] L. Kallel, “Inside GA dynamics: ground basis for comparison,” Proc.
the 4th Conference on Parallel Problem Solving from Nature, Lecture
Notes in Computer Science, pp. 57–66, 1998.
[4] S. Kauffman, The origins of order, Oxford University Press, 1993.
[5] E. D. Weinberger, “Correlated and uncorrelated fitness landscapes andhow to tell the difference,” Biological Cybernetics, 63, pp. 325–336,
1990.
[6] B. Manderick, M. D. Weger and P. Spiessens, “The genetic algorithm
and the structure of the fitness landscape,” Proc. the Fourth International
Conference on Genetic Algorithms, Edited by R. K. Belew and L. B.
Booker, San Mateo, California:Morgan Kaufmann, pp. 143–150, 1991.
[7] W. Hordijk, “A measure of landscapes,” Evolutionary Computation, Vol.
4, No. 4, pp. 335–360, 1994.
[8] P. F. Stadler, “Landscapes and their correlation functions,” J. Math.
Chem, Vol. 20, pp. 1–45, 1996.

2.0e-03

1.5e-03

1.5e-031.0e-031.0e-03αα2.0e-035.0e-04

5.0e-04

0.0e+00

0.0e+00
0.6

0.8

1.0

0.6

0.8

Correlation
NN
P=0.99

P=0.9
F=2

F=3
F=4

NN
P=0.99

P=0.9
F=2

F=3
F=4

(b) Nh = 1

8.0e-04

6.0e-04

6.0e-04

4.0e-04

4.0e-04α8.0e-042.0e-042.0e-04

0.0e+00

0.0e+00
0.6

0.8
Correlation

1.0

P=0.9
F=2

0.6

F=3
F=4

0.8
Correlation

NN
P=0.99(c) Nh = 5

P=0.9
F=2
(d) Nh = 10

2.0e-04α1.5e-04
1.0e-04
5.0e-05
0.0e+00
0.6

NN
P=0.990.8
Correlation
P=0.9
F=2

1.0

F=3
F=4

(e) Nh = 15
Fig. 10.

α as a function of the correlation (E˙b ) for each Nh and TNK(p) at q = 1/L

1000

Nh=0
Nh=1
Nh=5
900

Fitnessα(a) Nh = 0NN
P=0.991.0

Correlation

Nh=10
800
Nh=15
700
600
0

1000 2000 3000 4000 5000 6000
Generation

Fig. 11.

Maximum fitness at q = 1/L

1.0

F=3
F=4

[9] M. Mitchell, S. Forrest and J. H. Holland, “The royal road for genetic algorithms: fitness landscapes and GA performance,” Towards a Practiceof Autonomous Systems: Proceedings of the First European Conferenceon Artificial Life, 1991, Edited by F. J. Varela and P. Bourgine, Paris:A
Bradford Book, The MIT Press, pp. 245–254, 1992.
[10] E. Nimwegen, J. Crutchfield and M. Mitchell, “Statistical dynamics ofthe royal road genetic algorithm,” Theoretical Computer Science, Vol.
229, No. 1, pp. 41–102, 1999.
[11] I. Harvey, “Artificial evolution for real problems,” Evolutionary
Robotics: From Intelligent Robots to Artificial Life (ER’97), Edited by
T. Gomi, AAI Books, 1997.
[12] T. Smith, P. Husbands and M. O’Shea, “Neutral networks in an
evolutionary robotics search space,” Proc. the 2001 IEEE Congress on
Evolutionary Computation, pp. 136–145, 2001.
[13] T. Smith, P. Husbands and M. O’Shea, “Neutral networks and evolvability with complex genotype-phenotype mapping,” Proc. the European
Conference on Artificial Life: ECAL2001, pp. 23–36, 2001.
[14] T. Smith, A. Philippides, P. Husbands and M. O’Shea, “Neutrality andruggedness in robot landscapes,” Proc. the the 2002 IEEE Congress on
Evolutionary Computation, pp. 136–145, 2002.
[15] A. Thompson, “An evolved circuit, intrinsic in silicon, entwinedwith physics,” Proc. the First International Conference on Evolvable
Systems: From Biology to Hardware, pp. 390–405, 1996.
[16] V. K. Vassilev, T. C. Fogarty and J. F. Miller, “Information characteristics and the structure of landscape,” Evolutionary Computation, Vol.
8, No. 1, pp. 31–60, 2000.
[17] V. K. Vassilev and J. F. Miller, “The advantages of landscape neutrality
in digital circuit evolution,” Proc. the Third International Conference
on Evolvable Systems: From Biology to Hardware, Edited by J. Miller
et al., pp. 252–263, 2000.
[18] T. Smith, P. Husbands, P. Layzell and M. O’Shea, “Fitness landscapesand evolvability,” Evolutionary Computation, Vol. 10, No. 1, pp. 1–34,
2002.
[19] T. Smith, The Evolvability of Artificial Neural Networks for Robot
Control, Ph.D. Dissertation, School of Biological Sciences, Universityof Sussex, 2002.
[20] M. Nei, “Genetic distance between populations,” The American Naturalist, Vol. 106, pp. 283–292, 1972.
[21] Y. Katada, K. Ohkura and K. Ueda, “The Nei’s standard genetic
distance in artificial evolution,” Proc. the 2004 IEEE Congress on
Evolutionary Computation (CEC2004), pp. 1233–1239, 2004.
[22] M. Kimura, The Neutral Theory of Molecular Evolution, Cambridge
University, Press, New York, 1983.
[23] T. Ohta, “The nearly neutral theory of molecular evolution,” Annu.
Rev. Ecol. Syst., 23:263–286, 1992.
[24] T. Ohta, “Evolution by nearly-neutral mutations,” Genetica, 102/103,
pp. 83–90, 1998.
[25] D. Goldberg, Genetic Algorithms in Search, Optimization and Machine
Learning, Addison-Wesley, 1989.
[26] M. Newman and R. Engelhardt, “Effect of neutral selection on theevolution of molecular species,” Proc. the Royal Society of London B,
Morgan Kaufmann, 256, pp. 1333–1338, 1998.
[27] L. Barnett, Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality, School of Cognitive and Computing Sciences,
Sussex University, 1997.
[28] Y. Katada, K. Ohkura and K. Ueda, “Artificial evolution of pulsed
neural networks on the motion pattern classification system,” Proc.
2003 IEEE International Symposium on Computational Intelligence in
Robotics and Automation(CIRA), pp. 318–323, 2003.
[29] Y. Katada, K. Ohkura and K. Ueda, “An Approach to Evolutionary
Robotics Using a Genetic Algorithm with a Variable Mutation Rate
Strategy,” Parallel Problem Solving from Nature (PPSN VIII), pp. 952–
961, 2004.
[30] R. Beer, “Toward the Evolution of Dynamical Neural Networks for
Minimally Cognitive Behavior,” Proc. From Animals to Animats 4,,
Edited by P. Maes, M. Mataric, J. Meyer, J. Pollack, S. Wilson, MITpress: pp. 421–429, 1996.
[31] W. Maass and C. M. Bishop, Pulsed Neural Networks, MIT press,
1998.
[32] D. Floreano and C. Mattiussi, “Evolution of Spiking Neural Controllers,” Evolutionary Robotics: From Intelligent Robots to Artificial
Life (ER’01), Edited by T. Gomi, AAI Books, Springer-Verlag, pp. 38–
61, 2001.

[33] E. Nimwegen and J. Ctrutchfield, “Optimizing Epochal Evolutionary
Search: Population-size Dependent Theory,” SFI Working Paper 9810090, Santa Fe Institute, 1998.
[34] Y. Katada, K. Ohkura and K. Ueda, “Tuning Genetic Algorithms for
Problems Including Neutral Networks -The Simplest Case: The Balance Beam Function-,” Proc. the 7th Joint Conference on Information
Sciences, pp. 1657–1660, 2003.
[35] Y. Katada, K. Ohkura and K. Ueda, “Tuning Genetic Algorithms for
Problems Including Neutral Networks -A More Complex Case: The
Terraced NK Problem-,” Proc. the 7th Joint Conference on Information
Sciences, pp. 1661–1664, 2003.
[36] K. Ohkura and K. Ueda, “Adaptation in Dynamic Environment byUsing GA with Neutral Mutations,” International Journal of SmartEngineering System Design, 2, pp. 17–31, 1999.
[37] M. Ebner, P. Langguth, J. Albert, M. Shackleton and R. Shipman, “On
Neutral Networks and Evolvability,” Proc. the 2001 IEEE Congress on
Evolutionary Computation: CEC2001, IEEE Press, pp. 1–8, 2001.
[38] J. D. Knowles and R. A. Watson, “On the Utility of Redundant
Encodings in Mutation-based Evolutionary Search,” Edited by J. J.
Merelo, P. Admidis, H. -G. Beyer, J.-L. Fernandes-Villacanas, H.-P.
Schwefel, Parallel Problem Solving from Nature (PPSN VII), LNCS
2439, pp. 88–98, 2002.
[39] F. Rothlauf and D. Goldberg, “Redundant Representations in Evolutionary Computation,” Evolutionary Computation, 11(4), pp. 381–415,
2003.