Measurements of Features of Fitness Landscapes on Competitive
Co-Evolutionary Robotics
Yoshiaki Katada and Yuta Handa
Department of Electrical and Electronic Engineering, Setsunan University, Neyagawa, Osaka, JAPAN
Phone/Fax: +81 728 39 9148
Email: katada@ele.setsunan.ac.jp

ABSTRACT– Open-ended evolution is considered to be caused by several factors, one of which would
be co-evolution. Competitive co-evolution can give rise to the “Red Queen eﬀect”, where the ﬁtness
landscape of each population is continuously changed by the competing population. Therefore, if suchchanges are captured, co-evolutionary progress would be measured. In this paper, we investigatedfeatures of competitive co-evolutionary ﬁtness landscapes on a predator-prey problem in computer
simulations. The results suggest to us that ﬁtness landscapes on competitive co-evolutionary robotics
have no correlation with respect to the genetic data obtained at each generation in the evolutionaryruns.
Key Words: Competitive Co-Evolution, Evolutionary Robotics, Fitness Landscapes

1.

INTRODUCTION

Open-ended evolution is considered to be caused by several factors, one of which would be co-evolution.
In competitive co-evolution, “Red Queen hypothesis” has been discussed where a species must evolve forexistence and it becomes extinct if it stops evolving. In the simplest scenario of two competing species,
an advantage of one species might lead the disadvantage of the other species, then the other species also
responds with counter-adaptive strategies to get its own advantage, which appear “a co-evolutionaryarms race”.
In competitive co-evolution, the ﬁtness landscapes of competing populations might be continuously
changed by such arms races. These changes could prevent populations from being stuck on local areasof the landscape [1] as well as stimulate them to move better regions. Therefore, if such changes could
be captured, co-evolutionary progress would be measured.
In the Evolutionary Computation community, the geography of a ﬁtness landscape has been discussedwith respect to problem diﬃculties. These are conceptualized as isolation, deception, multimodality andflatness. In recent years, those are measured as the features of a ﬁtness landscape, ruggedness (epistasis)and neutrality [2][3][4].
Recently, we have proposed two methods to estimate features of competitive co-evolutionary ﬁtness
landscapes on a predator-prey problem in computer simulations and investigated the Red Queen eﬀect
on the ﬁtness landscape [5]. Our results can be summarized as follows:– In the metric where the features of ﬁtness landscapes are calculated based on the accumulated datafrom the initial generation to the current one, transition of the features in the ﬁtness landscapealmost converged during the process of evolution. Thus, we can not conﬁrm ever-changing ﬁtness
landscapes in this metric.
– In the metric where the features of ﬁtness landscapes are calculated based on the accumulated datafor certain generations, we conﬁrm the transition of the features over generations.
These were calculated based on the accumulated data for certain generations. We are also interested
in whether these are observed through the metric calculated based only on genetic data obtained ateach generation. This is because this metric seems natural for competitive co-evolution. In this paper,
we investigated features of competitive co-evolutionary ﬁtness landscapes calculated by genetic data

“World Automation Congress”
obtained at each generation. The paper is organized as follows. The next section describes the method
to estimate the degree of neutrality and ruggedness in ﬁtness landscapes, which we proposed in [4], andthen extends it for competitive co-evolution. Section 3 describes an experimental setup for a predatorprey problem in a robot control problem. Section 4 gives the results of our computer simulations.
Section 5 discusses characteristics of the features of the ﬁtness landscapes obtained in the experiments.
Conclusions are given in the last section.

2. METHODS FOR MEASUREMENTS OF FEATURES OF FITNESS LANDSCAPESIn this section, the procedure for estimating features of a ﬁtness landscape is described. Features to bemeasured are ruggedness and neutrality. Ruggedness is estimated based on the Smith’s measurement[3]and neutrality is based on our measurement, the standard genetic distance[6, 4].

2.1

Measure of Ruggedness

In real-world problems, ruggedness of a ﬁtness landscape is predicted by the ﬁtness correlation [2][3].
In this paper, therefore, the Smith’s measurement [3] was employed for the measure of ruggedness
because ﬁtness correlation can be expressed as a scalar value in their measurement. In [3], it has beenreported that ﬁtness correlation is expressed by the gradient of the expected oﬀspring ﬁtness versus
parent ﬁtness graph. The expected oﬀspring ﬁtness for parent ﬁtness k is given by:∑f¯k =f (g)g∈Gk|Gk |(1)

where, Gk is the set of oﬀspring from parents with the ﬁtness k over generations, g is an oﬀspring
genotype and f (· ) is the ﬁtness function. It has been also reported in [4][3] that the gradient, r,increases with the decrease of ruggedness, that this gradient is independent of neutrality and thatr ' 1.0 without any epistatic linkages between genes and r ' 0.0 with maximum epistatic linkages.
In order to measure features of competitive co-evolutionary ﬁtness landscapes from genetic data obtained at each generation, as mentioned in Section 1, we did small modiﬁcation to the original one asfollows:∑f (g)g∈Gktcf¯tkc =(2)|Gktc |
where, Gktc is the set of oﬀspring from parents with the ﬁtness k at the current generation, tc . The
gradient, r, of f¯tkc for k is calculated by using the method of least squares for each generation.

2.2

Measure of Neutrality

2.2.1

Standard Genetic Distance and its characteristics

Genetic distance is a term of population genetics used for estimating gene diﬀerences per locus betweenpopulations. Although there are several deﬁnitions for this, the Nei’s standard genetic distance[6] isadopted in our method [4].
The Nei’s standard genetic distance is deﬁned as follows. Consider two populations, X and Y . Let
xil = nil /M and yil = nil /M be the frequencies of the l-th alleles (i = 1, · · · , N , N , the length of thegenotype, l ∈ {1, 2} in a binary coded GA, nil , the number of the l-th allele, M , the population size)in X and Y , respectively. The probability of identity of two randomly chosen genes is jxi = x2i1 + x2i2
22
in the population X, while it is jyi = yi1+ yi2
in the population Y . The probability of identity of agene from X and a gene from Y is jxyi = xi1 yi1 + xi2 yi2 . Theidentity of genes between√√ normalized
X and Y with respect to a locus is deﬁned as Ii = jxyi /( jxi jyi ) where, Ii = 1.0 if the two
populations have the same alleles in identical frequencies, and Ii = 0.0 if they have no common alleles.

Measurements of Features of Fitness Landscapes on Competitive Co-Evolutionary Robotics
The normalizedof genes between
to the average in∑all loci is deﬁned∑NX and Y with respect∑N√ identity√Nj /N , JY =j /N and JXY =j /N . The
as I = JXY /( JX JY ), where, JX =i=1 xii=1 yii=1 xyigenetic distance between X and Y is deﬁned as D = − loge I. The above deﬁnition cannot be applied tothe standard GA directly, because it is assumed in population genetics that a new allele always appears
on a locus when a mutation occurs while “back mutations [7]” frequently occur in the standard GAdue to the binary coding scheme. Therefore, the genetic distance of GAs between the population at theinitial generation and the one at the last generation is calculated as:∑T −1

D(T ) =Dt,t+1

(3)

t=1

where T is the number of the last generation and Dt,t+1 is the genetic distance between the populationin the t-th and the (t + 1)-th generation.
In [8], we investigated the characteristics of the Nei’s standard genetic distance mentioned above inthe ﬁtness landscapes with neutrality and ruggedness. The characteristics of the Nei’s standard genetic
distance can be summarized as follows:
When the mutation rate per locus is suﬃciently small,
1. The genetic distance increases with the increase of neutrality.
2. The genetic distance decreases with the increase of ruggedness in landscapes with neutrality.
Considering these, we proposed a method for estimate the degree of neutrality in ﬁtness landscapeswith single species evolution [4]. That is, we estimate indirectly the degree of neutrality by measuring
the gradient of the genetic distance over generations, α, as well as r in Section 2.1.

2.2.2

Estimation of the Degree of Neutrality

In order to measure the degree of neutrality of competitive co-evolutionary ﬁtness landscapes, wecalculate the genetic distance from genetic data obtained at each generation as follows:
Dtc = Dtc −1,tc ,(4)where Dtc −1,tc is the genetic distance between the population in the current generation, tc , and theprevious generation, tc − 1. Thus, the gradient of the genetic distance over generations, α, is Dtc itself
in this metric.

3.

CONTROL TASK AND FITNESS FORMULA

The control task used in this paper was a predator-prey problem, and is based on a task originallyimplemented by Floreano [1]. Following the setting given in [1], this problem was implemented in thecontext of evolutionary robotics. The simulated environment is shown in Fig. 1(a), where a predator
seeks to hit (capture) a prey. Generally, predators and preys are set belonging to diﬀerent species
which have diﬀerent sensors and motors. Following this setting, two kinds of sensor arrangement wereemployed, one (the predator) is equipped with linear while the other (the prey) is equipped with omnidirection (Fig. 1(b)). Both agents were equipped with 18 infrared proximity sensors for detecting theopponent agent and walls. The agent’s behavior is controlled by an ANN.
Employing a mathematical model of a mobile robot, the displacement of the agent was computed asfollows: xk+1 = xk + cos θk (VR + VL )/2, yk+1 = yk + sin θk (VR + VL )/2, θk+1 = θk + (VR − VL )/2R
where VR and VL are the velocities applied to the right and left wheel respectively, R is the radius ofan agent, 2R is the interval between the wheels. The maximum speed is equally set for both agents.
The system error was not implemented due to simple analysis.
At the beginning of each trial, the predator and prey were always positioned on a horizontal line at
the four random orientations for each in the middle of the environment at a distance corresponding tohalf the environment width (Fig. 1(a)). One trial ended either when the predator hits the prey or when
400 steps are performed without the hit. Based on the ﬁtness function used by [1], the performance

“World Automation Congress”

㪧㫉㪼㫐㪧㫉㪼㪻㪸㫋㫆㫉(a)
Twospecies
evolved in a squarearena with walls㪪㪼㫅㫊㫆㫉㪧㫉㪼㫐㪧㫉㪼㪻㪼㫋㫆㫉(b) Simulated models of the sensors for
predator and prey robots.

Fig. 1. Experimental setup for a predator-prey problem.

∑N umT rials

measure to be maximized for the predator, pr, and the prey, py, were as follows: Fpr = i=1{1−∑N umT rials
Stepi /M axStep}/N umT rials, Fpy ={Step/MaxStep}/NumTrials
whereNumTrials
ii=1
is the number of trials for an individual (16 trials for each individual) and M axStep is set at 400. Theﬁtness function increases as the predator catches the prey more quickly while the prey escapes longer
before being caught by the predator.

4.

COMPUTER SIMULATIONS

4.1

Simulation Conditions

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 amongneurons were genetically encoded and evolved. The total number of parameters is equal to 115. Theparameters 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 the general settings of competitive co-evolution, an individual I from generation g is evaluated against
representatives of I’s opponent population from each previous generation [10]. In this experiment,
however, each individual was evaluated only against an individual selected randomly from the samegeneration of the opponent population. This is because features of ﬁtness landscapes are measured
through genetic data obtained at each generation.
Computer simulations were conducted by setting the population size 50 for each species. Each individual
was encoded as binary strings with 10 bits for each parameter. Therefore, the total length of thegenotype is L = 1150. The simple GA (SGA) were adopted to evolve ANN parameters as well as
calculate the genetic distance. The genetic operation for the SGA was standard bit mutation according
to the setting in our previous results in [4]. Based on the assumption of the genetic distance in Section
2.2.1, the per-bit mutation rate, q, was set at 10/L. Tournament selection was adopted. Elitism wasapplied. The tournament size was set at 2. A generational model was used. Each run lasted 5,000generations. We conducted 10 independent runs. We did not notice signiﬁcant diﬀerences among theseruns 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.

1.0

1.0

0.8

0.8

0.6

0.6

Fitness

Fitness

Measurements of Features of Fitness Landscapes on Competitive Co-Evolutionary Robotics0.40.4

0.2

0.2

0.0

0.001000

2000

3000

4000

5000

01000

Generation

2000

3000

4000

5000

2.0

3.0

Generation(a) for pr(b) for py

0.05

0.05

0.04

0.04
Genetic distance (α)

Genetic distance (α)

Fig. 2. Maximum ﬁtness at each generation

0.03

0.02

0.01

0.00
-3.0

0.03

0.02

0.01

-2.0

-1.0

0.0

1.0

2.0

3.0

0.00
-3.0

-2.0

-1.0

Correlation (r)Pr1-1000

Pr1001-2000

Pr2001-3000(a) for pr

0.0

1.0

Correlation (r)Pr3001-4000

Pr4001-5000

Py1-1000

Py1001-2000

Py2001-3000

Py3001-4000

Py4001-5000(b) for py

Fig. 3. Genetic distance α as a function of the correlation r

4.2

Simulation Results

Figure 2(a) and 2(b) show the maximum ﬁtness at each generation for pr and py, respectively. We
observed dominance of pr against py in almost every generation although a set of oscillations in ﬁtnessof py emerged.
Figure 3(a) and 3(b) show r and α at each generation for pr and py, respectively. The data were scatteredwidely around the value, r = 0, for each species. This seems less likely that there are correlation in
their ﬁtness landscapes. On the other hand, the genetic distances, α, were large. This means that thoseﬁtness landscapes include large neutrality.

5.

Discussion

The obtained results in the previous section show that their ﬁtness landscapes have no correlation fromthe view point of the short time period (for each generation). This means that evolutionary searchbecame random. This would be explained as follows:“World Automation Congress”– In the experiment, each individual was evaluated only against an individual selected randomly fromthe same generation of the opponent population. Therefore, representatives of opponent population
were substituted so frequently that ﬁtness landscapes changed radically at each generation. As aresult, both species could not adapt enough to each other.
– The features of the ﬁtness landscapes were calculated only from the genetic data obtained at eachgeneration. This seems likely that the amount of sampling data collected for each generation were
too small to estimate features of the ﬁtness landscapes adequately.
– The mutation rate set in the experiment was 10/L. Due to this rate, the eﬀective mutation rate
was likely to exceed a certain critical mutation rate[9] although we have conﬁrm the characteristics
mentioned in Section 2 at this mutation rate in our preliminary experiments using test functions.

6.

Conclusions

In this work, we investigated features of competitive co-evolutionary ﬁtness landscapes calculated bygenetic data obtained at each generation. Our results can be summarized as follows:– We conﬁrmed the radical transition of the features of ﬁtness landscapes but did not ﬁnd any trendsof them.
– The degree of ruggedness was so large that there were no correlation in their ﬁtness landscapes.
– Fitness landscapes include large neutrality.
In this work, we also cannot conﬁrm ideal co-evolutionary progress[10], where there is continuous
progress in both competing populations. On the other hand, the obtained knowledges in this paper canhelp us understand the results obtained in the same kinds of experiments where ﬁtness landscapes arechanged so frequently such as evolution in dynamical environments.

References
1. D. Floreano and S. Nolﬁ, “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, 1997, pp. 398–406.
2. E. D. Weinberger, “Correlated and uncorrelated ﬁtness landscapes and how to tell the diﬀerence,”
Biological Cybernetics, 63, 1990, pp. 325–336.
3. T. Smith, P. Husbands, P. Layzell and M. O’Shea, “Fitness landscapes and evolvability,” Evolutionary Computation, Vol. 10, No. 1, 2002, pp. 1–34.
4. Y. Katada and K. Ohkura, “Estimating the Degree of Neutrality in Fitness Landscapes by theNei’s Standard Genetic Distance – An Application to Evolutionary Robotics –”, In Proceedings ofthe 2006 IEEE Congress on Evolutionary Computation (CEC2006), 2006, pp. 1590–1597.
5. Y. Katada and Y. Handa, “Tracking the Red Queen Eﬀect by Estimating Features of Competitive
Co-Evolutionary Fitness Landscapes”, In Proceedings of the 2010 IEEE Congress on EvolutionaryComputation (CEC2010), submitted to.
6. M. Nei, “Genetic distance between populations,” The American Naturalist, Vol. 106, 1972, pp. 283–292.
7. T. Ohta, “The nearly neutral theory of molecular evolution,” Annu. Rev. Ecol. Syst., 23:263–286,1992.
8. Y. Katada, K. Ohkura and K. Ueda, “The Nei’s standard genetic distance in artiﬁcial evolution,” In
Proceedings of the 2004 IEEE Congress on Evolutionary Computation (CEC2004), 2004, pp. 1233–1239.
9. S. Kauﬀman, The origins of order, Oxford University Press, 1993.
10. D. Cliﬀ and G. F. Miller, “Tracking the Red Queen: Measurements of Adaptive Progress in CoEvolutionary Simulations”, In Proceedings of the Third European Conference on Artificial Life,
1995, pp. 200-218.