WCCI 2010 IEEE World Congress on Computational Intelligence
July, 18-23, 2010 - CCIB, Barcelona, Spain

CEC IEEE

Tracking the Red Queen Effect by Estimating Features ofCompetitive Co-Evolutionary Fitness Landscapes
Yoshiaki KATADA, Member, IEEE and Yuta HANDA

Abstract— Open-ended evolution is considered to be causedby several factors, one of which would be co-evolution. Competitive co-evolution can give rise to the “Red Queen effect”,
where the fitness landscape of each population is continuously
changed by the competing population. Therefore, if such continuous changes are captured, co-evolutionary progress would
be measured. In this paper, we estimate features of competitiveco-evolutionary fitness landscapes on a predator-prey problem
in computer simulations and investigate the Red Queen effecton the fitness landscape. Two types of method were proposed toestimate features, ruggedness and neutrality. One was calculated
based on accumulated data so far at each generation, and theother was based on accumulated data during a certain period.
The results suggest to us that our method can track the progressof fitness landscapes on competitive co-evolutionary robotics.

I. I NTRODUCTION
Open-ended evolution is considered to be caused by several factors, one of which would be co-evolution [1]. In
competitive co-evolution, “Red Queen hypothesis” has been
discussed where a species must evolve for its existence and it
becomes extinct if it stops evolving. In the simplest scenarioof two competing species, an advantage of one species mightlead to the disadvantage of the other species, then the otherspecies also responds with counter-adaptive strategies to get
its own advantage, which appear “a co-evolutionary arms
race”.
In competitive co-evolution, the fitness landscapes of competing populations might be continuously changed by sucharms races. These changes could prevent populations frombeing stuck on local areas of the landscape [2] as well as
stimulate them to move better regions. Therefore, if suchchanges could be captured, co-evolutionary progress would
be measured.
In the Evolutionary Computation community, the geography of a fitness landscape has been discussed withrespect to problem difficulties. These are conceptualized as isolation, deception, multimodality and flatness.
In recent years, those are measured as the features ofa fitness landscape, ruggedness (epistasis) and neutrality[3][4][5][6][7][8][9][10][11][12][13]. Ebner et al. [14] investigated the dynamics of competitive co-evolution by asimple model where fitness landscapes are deformed by theexistence of other species. Within the limit of our knowledge,
however, there is no literature to investigate competitive coevolutionary dynamics with respect to the features of a fitness
landscape.
Yoshiaki Katada and Yuta HANDA are with the Department of Electricaland Electronic Engineering, Setsunan University, 17-8 Ikeda-nakamachi,
Neyagawa, Osaka 572-8508, JAPAN (phone: +81 728 39 9148; email:katada@ele.setsunan.ac.jp).

978-1-4244-8126-2/10/$26.00 c 2010 IEEE

In this paper, we propose methods to estimate features ofcompetitive co-evolutionary fitness landscapes on a predatorprey problem in computer simulations in order to investigate
the Red Queen effect on the fitness landscape. Pursuitand evasion have been studied in various fields, behavioral
biology, neuroethology, game theory and embodied cognitive
science. This is straightforward to study competitive coevolution. Predator-prey problems in our computer simulations are implemented in the context of evolutionary robotics
where a mobile agent has its own neural controller withsensory-motor architectures and interacts with the competing
agent and the environment. It has been known that such
evolutionary robotics fitness landscapes include both ruggedness and neutrality [10][11][12][13]. In [13], we proposed amethod to estimate the degree of neutrality and ruggedness
in fitness landscapes, then confirmed the validity of the
proposed approach in an evolutionary robotics problem.
However, that was a problem with single species. Therefore, we need to make some modifications of the proposed
method[13] in order to capture changes of fitness landscapesfor competitive co-evolutionary problems.
The paper is organized as follows. The next section describes the method to estimate the degree of ruggedness andneutrality in fitness landscapes, which we proposed in [13],and then extends it for competitive co-evolution. Section III
describes an experimental setup for predator-prey in a robot
control problem. Section IV gives the results of our computer
simulations. Section V discusses performances of the bestindividuals across generations. Conclusions are given in thelast section.
II. M ETHODS FOR MEASUREMENTS OF F EATURES OFF ITNESS L ANDSCAPESIn this section, the procedure for estimating features of afitness landscape is described. Features to be measured areruggedness and neutrality. Ruggedness is estimated based on
the Smith’s measurement [12] and neutrality is based on our
measurement, the Standard Genetic Distance[15][13].
A. Measure of Ruggedness
In real-world problems, ruggedness of a fitness landscapeis predicted by fitness correlation [5][12]. In this paper, themeasurement proposed by Smith et al. [12] was employed
for the measure of ruggedness because fitness correlation canbe expressed as a scalar value in their measurement. In [12],it has been reported that fitness correlation is expressed by
the gradient of the expected offspring fitness versus parent

4417

fitness graph. The expected offspring fitness for parent fitness
k is given byPg∈Gk f (g)
k
¯
f =
(1)
|Gk |
where, Gk is the set of offspring from parents with the fitness
k over generations, g is an offspring genotype and f (· ) is thefitness function. It has been also reported in [12][13] that thegradient, r, increases with the decrease of ruggedness, that
this gradient is independent of neutrality and that r ≃ 1.0
without any epistatic linkages between genes and r ≃ 0.0
with maximum epistatic linkages.
B. Standard Genetic Distance and its characteristics
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[15] is adopted in our method[13].
The Nei’s standard genetic distance is defined as follows.
Consider two populations, X and Y . Let xil = nil /Mand yil = nil /M be the frequencies of the l-th alleles(i = 1, · · · , N , N , the length of the genotype, l ∈ {1, 2} ina binary coded GA, nil , the number of the l-th allele, M , thepopulation size) in X and Y , respectively. The probability ofidentity of two randomly chosen genes is jxi = x2i1 + x2i2 in22
the population X, while it is jyi = yi1+yi2
in the population
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 defined
as
jxyi
(2)
Ii = √ p ,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
√ ,
(3)
JX JY
PL
PL
where, JX =jxi /L, JY =i=1i=1 jyi /L, JXY =
PL
j
/L
and
L
is
the
numberofloci. The genetic
i=1 xyidistance between X and Y is defined asI=√

D = − loge I.

(4)

The above definition cannot be applied to the GAs directly,
because it is assumed that a new allele always appears on
a locus when a mutation occurs, while “back mutations[16]” frequently occur in the GAs, due to the binary coding
scheme. Therefore, the genetic distance of GAs between
populations at the initial generation and at the last generation
is calculated as:tX
l −1
Dt,t+1(5)
D1,tl =
t=1

where tl 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.

In [17], we investigated the characteristics of the Nei’sstandard genetic distance (equation (5)) in the fitness landscapes with ruggedness and neutrality. These characteristics
can 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.
Due to the characteristics 1) and 2), the gradient of thegenetic distance over generations, α, can be an index of
the increase of neutrality. Moreover, we need to consider
the effect of ruggedness on the genetic distance due to 3).
Considering these, we proposed a method to estimate thedegree of neutrality in fitness landscapes on a real-world
problem [13]. The next subsection shows the procedure indetails.
C. Procedure for Estimating the Degree of Neutrality
In this paper, r and α which are described in previous
subsection II-A and II-B are calculated by using the methodof least squares on the result of each run (For details, readers
may refer to [13][17]). Thus, the procedure for estimating thedegree of neutrality in a fitness 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, (r, α), from each run on the realworld problem.
iii) Calculate a set of r-α curves in test functions withdifferent levels of ruggedness and neutrality.
iv) By using a set of r-α curves as a baseline, judge wherea point, (r, α), obtained from the real-world problem
locates in the graph of (r, α). Then estimate indirectly
the degree of neutrality on the real-world problem.
The reason why the step iii) and iv) are conducted isthat the genetic distance is affected by both neutrality andruggedness as mentioned in Section II-B. Test functions, theNKp[18] and NKq[19] fitness landscapes (see the details inAppendix), are adopted for obtaining a set of r-α curves.
The landscape parameters of the NKp and the NKq should be
decided at the step iii) for conducting the step iv). Addition tothis, the parameters of the GAs (a mutation rate, a population
size, a tournament size, etc.) for test functions should be
the same as those for a real-world problem due to thecharacteristics of the standard genetic distance.
D. Small Modifications for Competitive Co-evolution
The previous subsection described the measurement for
single species. Because they assume a fixed fitness landscape,only average features of a fitness landscape are calculated4418

based on the accumulated data from the initial generation
to the last generation at the end of each run. In order tomeasure changing features of competitive co-evolutionary
fitness landscapes, we did two kinds of modification for thenumber of generations over which calculations are made in
Equation (1) and (5) as follows;
Metric A) The first metric is similar to the original one,
where changing features are measured based on the accumulated data from the initial generation to the current
generation, tc . f¯1,tc is calculated based on Equation (1) as
follows:
P
f (g)
g∈Gk
1,tc
k
=
f¯1,t
(6)
c
|Gk1,tc |where, Gk1,tc is the set of offspring from parents with thefitness k over tc generations, In the same way, D1,tc is calculated based on Equation (5) using the following equation:
D1,tc =tX
c −1

Dt,t+1(7)t=1Thus, r1,tc and α1,tc are calculated by using Equation (6)and (7), respectively.
Metric B) In the second metric, features are measured only
based on the accumulated data for certain generations. f¯ts ,teis calculated using the following equation,
P
f (g)
g∈Gk
ts ,tek¯
fts ,te =(8)|Gkts ,te |where, Gkts ,te is the set of offspring from parents with thefitness k from ts to te generation, and ts is the first generation
for the certain generations and te is the last one. In the sameway, Dts ,te is calculated using the following equation:
Dts ,te =tX
e −1

Dt,t+1 .

(9)

t=ts

Thus, rts ,te and αts ,te are calculated by using Equation (8)and (9), respectively.
In the remainder of this paper, for simplicity, we occasionally denote r1,tc or rts ,te by r, and α1,tc or αts ,te by
α.

Fig. 1.

PredatorPrey(a) Two species evolvedin a square arena withwalls(b) Simulated models of the sensors for
predator and prey robots.

Experimental setup for a predator-prey problem

walls. The agent’s behavior is controlled by artificial neutral
networks (ANN), which details are described in Section IV.
Employing a mathematical model of a mobile robot,
the displacement of the agent (the position: xm , ym , theorientation: θm ) was computed as follows:
VR + VLcos θm2
VR + VLsin θm(10)
ym+1 = ym +2VR − VL,θm+1 = θm +2R
where VR and VL are the velocities applied to the right andleft wheel respectively, R is the radius of an agent, 2R is theinterval between the wheels. The maximum speed is equally
set for both agents. The system error was not assumed due
to simple analysis.
At the beginning of each trial, the predator and prey werealways positioned on a horizontal line at the four randomorientations in the middle of the environment at a distancecorresponding to half the environment width (Figure 1(a)).
One trial ended either when the predator hits the prey orwhen 400 steps are performed without the hit. Based on thefitness function used by [2], the performance measure to be
maximized for the predator, pr, and the prey, py, were as
follows:xm+1

F itnesspr=

III. CONTROL TASK AND FITNESS FORMULA
The control task used in this paper was a predator-prey
problem, and is based on a task originally implemented
by Floreano [2]. Following the setting given in [2], thisproblem was implemented in the context of evolutionary
robotics. The simulated environment is shown in Figure 1(a),where a predator seeks to hit (capture) a prey. Generally,
predators and preys are set belonging to different species
which have different sensors and motors. Following thissetting, two kinds of sensor arrangement were employed, one(the predator) is equipped with linear while the other (theprey) is equipped with omni-direction (Figure 1(b)). Bothagents were equipped with 18 infrared proximity sensors: the9 ones for detecting the other agent and the other ones for theSensor㪧㫉㪼㪻㪸㫋㫆㫉

㪧㫉㪼㫐

F itnesspy== xm +

N umT
Xrialsi=1
N umT
Xrialsi=1

1 − Stepi /M axStep, (11)
N umT rials
Stepi /M axStep.
N umT rials(12)

where N umT rials is the number of trials for an individual(16 trials for each individual) and M axStep is set at 400.
The fitness function increases as the predator catches theprey more quickly while the prey escapes longer before beingcaught by the predator.
IV. COMPUTER SIMULATIONS
A. Simulation Conditions
In the general settings of competitive co-evolution, an
individual I from generation t is evaluated against representatives of I’s opponent population from each previous

4419

B. Simulation Results
Figure 2 shows the maximum fitness at each generationfor each evaluation. Although dominance of pr against py inthe fitness level does not completely correspond to the one
in the behavioral level due to the environmental settings, thepredators always outperformed the preys over generations in
all the runs.
Figure 3 shows the r-α curves obtained in the NKp and theNKq, where F and P are constant for each curve. These were1.0

Fitness

0.8
0.6
0.4
0.2

Pr
Py

0.0
0

1000

2000

3000

4000

5000

4000

5000

4000

5000

Generation(a) SG

1.0

Fitness

0.8
0.6
0.4
0.2

Pr
Py

0.0
0

1000

2000 3000
Generation(b) BP1

1.0
0.8
Fitness

generation t − t′ : t′ ∈ T , T ⊂ {0, 1, · · · , t} [20]. In
Last Elite Opponent (LEO) evaluation[20], each individual’s
fitness is evaluated only in trials against the best individualfrom the previous generation of the opponent population,
T ∈ {1}: we refer to this as BP1. In [2][21][22], eachindividual is evaluated against the best competitors of theten previous generations, T ∈ {1, 2, · · · , 10}: BP10. For
T ∈ {0}, each individual is evaluated only against an
individual selected randomly from the same generation of
the opponent population: SG. In this paper, we employedthese three evaluations.
In this work, the agent controller was constructed by the
ANN with 18 sensory neurons, 2 fully interconnected motor
neurons and 3 fully interconnected hidden neurons. The
connection weights among neurons were genetically encodedand evolved. The total number of parameters is equal to115. The parameters were mapped linearly with the range,ω ∈ [−1.0, 1.0]. The output of neurons is given by the
sigmoid function, f (x) = 1/(1 + exp(−x)).
In computer simulations, the simple GA (SGA) [23] wereadopted to evolve ANN parameters as well as calculate thegenetic distance. Each individual was encoded as binary
strings with 10 bits for each parameter. Therefore, the total
length of the genotype is L = 1150. The genetic operation
for the SGA was standard bit mutation following the setting
given in [13]. Based on the assumption of the genetic
distance in Section II-B, the per-bit mutation rate was set
at 1/L. A set of landscape parameters of the NKp and theNKq for the step iii) in Section II-C was decided in the
preliminary computer simulations. In this experiment, thefollowing landscape parameters were adopted: N = 20,
K ∈ {0, 1, · · · , 19} for the NKp and NKq. P = 0.99 for
the NKp and F = 2 for the NKq. With these parameters,
the NKp includes a higher degree of neutrality than theNKq does. According to the procedures in Section II-C,
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. A generational model was used. Each run lasted 5,000
generations. The parameters in Metric A and B were as follows: tc ∈ {1, 2, · · · , 500}, ts ∈ {1, 1001, 2001, 3001, 4001}
and te = ts + 999. We conducted 10 independent runs.
We did not notice significant differences among these runs
with respect to all the measures and analyses reported here.
Therefore, for clarity of explanation, we give data for a single
run, which will be described below.

0.6
0.4
0.2

Pr
Py

0.0
0

1000

2000 3000
Generation(c) BP10

Fig. 2.

Maximum fitness at each generation for each evaluation

used as a baseline when compared to the results obtained ineach run on the predator-prey problem. Figure 4(a), 4(c) and4(e) show r and α at each generation for each evaluation in
Metric A. Compared to Figure 3, the degree of neutrality inthe landscapes for all evaluations were estimated indirectly.
The points, (r, α), for pr and py in the early generations
locate above the curve for P = 0.99. This means that
their fitness landscapes in the early generations include highneutrality. During the process of evolution, the points forpr locate in the high r region, that is, high correlation while
those for py locate in the low r region except for py for BP1.

4420

0.0010P=0.99F=20.0008α0.00060.00040.00020.0000
0.0

0.2

0.4

0.6

0.8

1.0

r

α as a function of the correlation, r for the NKp with P = 0.99 and the NKq with F = 2

0.020

0.00100.015

0.00080.010

0.0006ααFig. 3.

0.005

0.00040.000

0.0002
0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

r
Pr1-1000
Py1-1000

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000

Pr1-1000
Py1-10000.8

1.0Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000(b) SG in Metric B

0.020

0.00100.015

0.00080.010

0.0006αα(a) SG in Metric A

0.005

0.00040.000

0.0002
0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

r
Pr1-1000
Py1-1000

Pr1001-2000
Py1001-2000

0.6

0.8

1.0

r

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000

Pr1-1000
Py1-1000(c) BP1 in Metric A

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000(d) BP1 in Metric B

0.020

0.00100.015

0.00080.010

0.0006

α

α

0.6
r

0.005

0.00040.000

0.0002
0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

r
Pr1-1000
Py1-1000

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

0.6

0.8

1.0

r
Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000

Pr1-1000
Pr1001-2000(e) BP10 in Metric A
Fig. 4.

0.4Pr2001-3000
Pr3001-4000

Pr4001-5000
Py1-1000

Py1001-2000
Py2001-3000

Py3001-4000
Py4001-5000(f) BP10 in Metric B

α as a function of the correlation, r, for each generation calculated by Metric A and Metric B

4421

This means that it was easy for the predator to evolve while
it was difficult for the prey to evolve in these settings. With
respect to the change of the fitness landscape, we can confirm
the transition of the points in the early 1,000 generations.
After that, however, those almost converged at a certain
point. In the first metric (the equation (6)(7)), the amountof accumulated data becomes larger with the increase of thegeneration. In the last generations, the new data obtained in
one generation do not have large effect on the total amountof data obtained over the generations. Thus, it seems likelythat the transition of the points becomes smaller after the
1,000 generation. These results were completely different
from what we expected in Section I. This shows the difficulty
to confirm ever-changing fitness landscapes by Metric A.
Figure 4(b), 4(d) and 4(f) show r and α for each generations in Metric B. The points for pr locate in the high r
region while those for py locate in the relatively low r region.
These tendencies to locate in those regions were the same as
the results obtained in Metric A. Comparing those features inthe evaluations, those of SG and BP1 locate higher than thoseof BP10, that is, the degrees of neutrality for SG and BP1
were larger than the one for BP10. It seems likely that BP10
has the strongest selection pressure in the evaluations. Thiswas why the fluctuations in fitness for BP10 were smaller
than those for SG and BP1. Moreover, we can confirm thetransition of the points among all the periods in Metric B.
V. D ISCUSSION

prey problem in computer simulations in order to investigate
the Red Queen effect on the fitness landscape. Our results
can be summarized as follows:• In the metric calculated based on the accumulated datafrom the initial generation to the current one, transitionof the features in the fitness landscape almost converged
after the early generations. Thus, we can not confirm
ever-changing fitness landscapes in this metric.
• In the metric calculated based on the accumulated datafor certain generations, we confirm the transition of thefeatures over generations.
From these results, we can confirm ever-changing fitness
landscapes over generations by the proposed method. On
the other hand, there was no continuous progress in both
populations for the CIAO evaluations. Future work will
investigate which GA should be applied to this problem
according to the features of the fitness landscapes obtained inthis paper and which transition pattern of features of fitness
landscapes should appear in ideal co-evolutionary progress.
A PPENDIX
The NKp and NKq fitness landscapes are the tunably
neutral NK landscapes, which are extended forms of Kauffman’s NK fitness landscape[4]. The former was proposedby Barnett [18] and the latter proposed by Newman andEngelhardt [19].
A. NKp Fitness LandscapeIn the previous section, we can confirm ever-changing
fitness landscapes over generations by one of the proposed
methods. However, the evolutionary dynamics of the obtained results in Figure 2 show that one species py were
overcome by the other species pr over generations. Therefore,
we need to investigate whether co-evolutionary progresshas generated by a complementary method. Figure 5, 6,
7 show CIAO (Current Individual vs. Ancestral Opponents[20]) plots for SG, BP1, BP10, respectively, where thebrightest cells represent the highest scores and the darkest
the worst, and each row represents fitness scores of the elitein one species at the generation against all of their ancestral
opponents. We can confirm some patterns (e.g. pr fareslightly badly against py from the generation 1700 to 2000
in Figure 5(a) , py do well against pr around the generation
1000 and 3900 in Figure 6(b) and py do well against pr
around the generation 2000 in Figure 7(b)). In ideal coevolutionary progress, where there is continuous progress inboth populations, a CIAO plot would show specific patterns:
the darker (low-score) cells towards the diagonal edge while
the lighter (high-score) cells towards the left-hand edge [20].
In Figure 5, 6 and 7, we cannot find any such patterns.
These results mean that an ever-changing fitness landscape isa necessary condition for ideal competitive co-evolutionary
progress, open-ended evolution, but it is not a sufficient one.
VI. C ONCLUSIONSIn this paper, we proposed methods to estimate features ofcompetitive co-evolutionary fitness landscapes on a predator-

The NKp fitness landscape has three parameters: N , thelength of the genotype; K, the number of epistatic linkages
between genes; and P , the parameter to tune the degree ofneutrality. The fitness value is calculated as follows: The
fitness contribution of the i-th locus, vi , is an real value generated randomly in the range 0.0 ≤ vi ≤ 1.0, i = 1, · · · , N
based on its allele and the alleles of K other loci. At the sametime, vi is set at 0.0 with the probability, P (0.0 ≤ P ≤ 1.0)
for involving neutrality in the landscapes. To calculate thefitness, V , of a genotype, the fitness contribution of eachlocus is averaged.
N

V =

1 X
vi .
N i=1

(13)

The degree of ruggedness of the landscape can be tuned bychanging the value of K. The ruggedness of the landscapeis maximized when K = N − 1, and is minimized whenK = 0. Also, the degree of neutrality of the landscape canbe tuned by changing the value of P . The neutrality of thelandscape is maximized when P = 1.0, and is minimized
when P = 0.0.
B. NKq Fitness Landscape
The NKq fitness landscape also has three parameters:
N , K, which are the same as those of the NKp and F ,the parameter to tune the degree of neutrality. The fitness
contribution of the i-th locus, vi , is an integer generated
randomly in the range 0 ≤ vi < F, i = 1, · · · , N based

4422

5000

5000
1

4000

1
4000

0.8

0.8

3000

0.6
Generation-py

Generation-pr

0.6
0.4
0.2
2000

0

1000

3000

0.4
0.2

2000

0

1000

1

1
1

1000

2000

3000

4000

5000

1

1000

2000

3000

4000

5000

Generation-py

Generation-pr(a) pr: predator generations 0 to 5000 run bottom to
top in steps of 10, prey generations 0 to 5000 run left
to right in steps of 10.

(b) py: prey generations 0 to 5000 run bottom to top
in steps of 10, predator generations 0 to 5000 run left
to right in steps of 10.

Fig. 5.

Current individual vs. ancestral opponents for SG.

5000

5000
1

4000

1
4000

0.8

0.8

3000

0.6
Generation-py

Generation-pr

0.6
0.4
0.2
2000

0

1000

3000

0.4
0.2

2000

0

1000

1

1
1

1000

2000
3000
Generation-py

4000

5000

1

(a) pr: predator generations 0 to 5000 run bottom to
top in steps of 10, prey generations 0 to 5000 run left
to right in steps of 10.
Fig. 6.

1000

2000
3000
Generation-pr

4000

5000

(b) py: prey generations 0 to 5000 run bottom to top
in steps of 10, predator generations 0 to 5000 run left
to right in steps of 10.

Current individual vs. ancestral opponents for BP1

5000

5000
1

4000

1
4000

0.8

0.8

3000

0.6
Generation-py

Generation-pr

0.6
0.4
0.2
2000

0

1000

3000

0.4
0.2

2000

0

1000

1

1
1

1000

2000

3000

4000

5000

1

1000

2000

3000

4000

5000

Generation-py

Generation-pr(a) pr: predator generations 0 to 5000 run bottom to
top in steps of 10, prey generations 0 to 5000 run left
to right in steps of 10.

(b) py: prey generations 0 to 5000 run bottom to top
in steps of 10, predator generations 0 to 5000 run left
to right in steps of 10.

Fig. 7.

Current individual vs. ancestral opponents for BP104423

on its allele and the alleles of K other loci. To calculate
the fitness, V , of a genotype, the fitness contribution of eachlocus is averaged, and then divided by F − 1, normalizing
V to the range 0.0 to 1.0. More formally:
V =

N
X
1
vi .
N (F − 1) i=1(14)[21] D. Floreano and S. Nolfi, “Adaptive Behavior in Competing CoEvolving Species”, Proceedings of the fourth European Conferenceon Artificial Life, MIT Press, pp. 378–387, 1997[22] D. Floreano, S. Nolfi and F. Mondada, “Competitive co-evolutionary
robotics: from theory to practice”, Proceedings of the fifth international
conference on simulation of adaptive behavior on From animals toanimats 5, MIT Press, pp. 515–524, 1998.
[23] Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley 1989.

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 → ∞.
R EFERENCES[1] Barnett, L.: “Ruggedness and Neutrality – The NKp family of Fitness
Landscapes”, Artificial Life VI: Proceedings of the Sixth International
Conference on Artificial Life, The MIT Press, pp. 18–27, 1998.
[2] D. Floreano and S. Nolfi, “God Save the Red Queen! Competition
in Co-Evolutionary Robotics”, Genetic Programming 1997: Proceedings of the Second Annual Conference, Morgan Kaufmann, Stanford
University, CA, USA, pp. 398–406, 1997.
[3] T. Jones and S. Forrest, “Fitness distance correlation as a measureof problem difficulty for genetic algorithms,” Proceedings of the
Sixth International Conference on Genetic Algorithms, Edited by L.
Eshelman, San Mateo, California, pp. 184–192, 1995.
[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,” Proceedings of the FourthInternational 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.
[9] B. Derrida and L. Pelit, “Evolution in a Flat Fitness Landscape”, Bull.
Math. Bio, Vol. 53, No. 3, 1991, pp. 355–382[10] T. Smith, P. Husbands and M. O’Shea, “Neutral networks in an
evolutionary robotics search space,” Proceedings of the 2001 IEEE
Congress on Evolutionary Computation, pp. 136–145, 2001.
[11] T. Smith, A. Philippides, P. Husbands and M. O’Shea, “Neutrality andruggedness in robot landscapes,” Proceedings of the the 2002 IEEE
Congress on Evolutionary Computation, pp. 136–145, 2002.
[12] T. Smith, P. Husbands, P. Layzell and M. O’Shea, “Fitness landscapesand evolvability,” Evolutionary Computation, Vol. 10, No. 1, pp. 1–34,
2002.
[13] Y. Katada and K. Ohkura, “Estimating the Degree of Neutrality in
Fitness Landscapes by the Nei’s Standard Genetic Distance – An
Application to Evolutionary Robotics –”, Proceedings of the 2006
IEEE Congress on Evolutionary Computation (CEC2006), pp. 1590–
1597, 2006.
[14] M. Ebner, R.A Watson, and J. Alexander, “Co-evolutionary Dynamics
on a Deformable Landscape,” Proceedings of the 2000 IEEE Congress
on Evolutionary Computation (CEC2000), pp. 1284–1291, 2000.
[15] M. Nei, “Genetic distance between populations,” The American Naturalist, Vol. 106, pp. 283–292, 1972.
[16] T. Ohta, “The nearly neutral theory of molecular evolution,” Annu.
Rev. Ecol. Syst., 23:263–286, 1992.
[17] Y. Katada, K. Ohkura and K. Ueda, “The Nei’s standard genetic distance in artificial evolution,” Proceedings of the 2004 IEEE Congress
on Evolutionary Computation (CEC2004), pp. 1233–1239, 2004.
[18] L. Barnett: Tangled webs: Evolutionary dynamics on fitness landscapeswith neutrality; MSc. dissertation, School of Cognitive and Computing
Sciences, Sussex University 1997.
[19] M. Newman and R. Engelhardt: Effect of neutral selection on theevolution of molecular species; Proceedings of the Royal Society of
London B, 256, pp. 1333–1338, Morgan Kaufmann 1998
[20] D. Cliff and G. F. Miller, “Tracking the Red Queen: Measurementsof Adaptive Progress in Co-Evolutionary Simulations”, Proceedings of
the Third European Conference on Artificial Life, pp. 200-218, 1995.

4424