An Approach to Evolutionary Robotics Using a
Genetic Algorithm with a Variable Mutation
Rate Strategy
Yoshiaki 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. Neutral networks, which occur in ﬁtness landscapes containing neighboring points of equal ﬁtness, have attracted much researchinterest in recent years. In recent papers [20, 21], we have shown that, inthe case of simple test functions, the mutation rate of a genetic algorithm
is an important factor for improving the speed at which a population
moves along a neutral network. Our results also suggested that the beneﬁts of the variable mutation rate strategy used by the operon-GA [5]increase as the ruggedness of the landscapes increases. In this work, we
conducted a series of computer simulations with an evolutionary robotics
problem in order to investigate whether our previous results are applicable to this problem domain. Two types of GA were used. One was thestandard GA, where the mutation rate is constant, and the other was theoperon-GA, whose eﬀective mutation rate at each locus changes independently according to the history of the genetic search. The evolutionary
dynamics we observed were consistent with those observed in our previous experiments, conﬁrming that the variable mutation rate strategy isalso beneﬁcial to this problem.

1

Introduction

Selective neutrality has been found in many real-world applications of artiﬁcial
evolution, such as the evolution of neural network controllers in robotics [1,2] and on-chip electronic circuit evolution [3, 4]. This characteristic is causedby highly redundant mappings from genotype to phenotype or from phenotype
to ﬁtness. With these kinds of problems, redundancy is inevitable. Even forproblems where redundancy is largely absent, it may be useful to introduce it. A
number of researchers have been trying to improve the performance of artiﬁcial
evolution on more traditional problems by incorporating redundancy in genotype
to phenotype mappings[5–8]. Neutrality is also found in natural systems, and has

Best
Mean

Fitness

Transient period

Equilibrium period

Generation

Fig. 1. Typical evolutionary dynamics on a ﬁtness landscape featuring neutral networks, which can be classiﬁed into transient periods and equilibrium periods.

been of particular interest to evolutionary theorists [9] and molecular biologists[10, 11].
Landscapes which include neutrality have been conceptualized as containing
neutral networks [6, 12, 13]. This concept is central to the majority of researchin this ﬁeld. Harvey [12] ﬁrst introduced the concept of neutral networks into
the GA community. His deﬁnition is as follows: “A neutral network of a ﬁtness
landscape is deﬁned as a set of connected points of equivalent ﬁtness, each representing a separate genotype: here connected means that there exists a pathof single (neutral) mutations which can traverse the network between any two
points on it without aﬀecting ﬁtness.”
Evolutionary dynamics on neutral networks can be classiﬁed into transientperiods and equilibrium periods (Fig. 1) [14, 15]. During an equilibrium period,
the population is clustered in genotype space around the dominant phenotype,analogously to quasi-species [16], and moves around until it ﬁnds a portal toa neutral network of higher ﬁtness. The discovery of a portal leads to a transient period, which is expected to be very short in comparison to an equilibrium
period. It has been shown that there is a clear transition in evolutionary dynamics for populations on neutral networks over the mutation rate range. At avery low mutation rate, the population is maintained in a cluster on the neutral network. As the mutation rate increases, the population gradually loses thecurrent network. That is, some individuals fall to lower neutral networks. At acertain critical mutation rate, the whole population will lose the current neutral
network. This mutation rate is called the phenotypic error threshold4 [14, 17, 18].
Generally, the error threshold sets the upper limit for a mutation rate thatwill enable eﬃcient search. This implies that if we adopt a constant mutation
rate strategy, we should set a relatively low mutation rate so as to avoid any error
threshold eﬀects during the process. From a practical point of view, however, it
would be eﬃcient to shorten the equilibrium period which dominates the whole
computation (Fig. 1). Additionally, in landscapes which include ruggedness, individuals can easily get trapped on local optima if there is a low mutation rateand high selection pressure. It has been demonstrated in a tunably neutral NK
4

These concepts originate from molecular evolution [10, 11]landscape [17, 19] that increasing neutrality does not aﬀect the ruggedness, although it does reduce the number of local optima [13, 17, 19]. This means that theeﬀects of ruggedness must be taken into account even if landscapes include neutral networks. Using a high mutation rate can shorten equilibrium periods andhelp a population avoid becoming trapped on local optima. However, as noted
above, using a high mutation rate can be counterproductive because of the effects of error thresholds. One approach to overcoming these problems would beto adopt variable mutation rate strategies, which change the eﬀective mutation
rate adaptively during the process of evolution.
Recently, we have investigated the eﬀect of mutation rate and selection pressure on the speed of population movement on very simple neutral networks with
diﬀerent levels of neutrality [20]. We also examined the performance of GAs
using terraced NK landscapes with diﬀerent levels of ruggedness and diﬀerent
selection pressures. [21]. Our results can be summarized as follows:– For a ﬁxed population size, the speed of a population plotted as a functionof the mutation rate yields a concave curve with an optimal mutation rate
and an error threshold.
– Increasing the selection pressure will improve the speed at which a population
moves on a neutral network.
– The variable mutation rate strategy used by the operon-GA [5] is not only
beneﬁcial with simple test functions but also with complex test functions.
The beneﬁts increase as the ruggedness of the landscapes increases.
We are interested in whether these observations are consistent with more
complex problems. This is because we want to solve complex real-world problems.
This paper investigates how well our previous results apply to the evolution ofartiﬁcial neural networks for robot control by comparing a standard GA [22] andthe operon-GA on an evolutionary robotics task using a simulated robot. The
paper is organized as follows. The next section describes the neural networks
adopted in a robot control problem. Section 3 deﬁnes the robot control problem
where the evolved neural networks are evaluated. Section 4 gives the resultsof our computer simulations. Section 5 discusses the relationship between thecorrelation of the landscape and the overall GA performance. Conclusions are
given in the last section.

2

The Neural Controller –Spike Response Model–

The agent’s behavior is controlled by a spike response model network [23], which
is a form of Pulsed Neural Network (PNN). A neuron emits a spike when the total
amount of excitation due to incoming excitatory and inhibitory spikes exceeds
its ﬁring threshold, θ. After ﬁring, the membrane potential of the neuron is
set to a low negative voltage, it then gradually returns to its resting potential;
during this refractory period, a neuron cannot emit a new spike. The function
ηi , accounting for neuronal refractoriness, is given by:r(1)
ηi (r) = − exp(− )H(r)
τm

(f )

Here r = t − ti is the diﬀerence between the time t and the time of ﬁring t(f )of neuron i, τm is a membrane time constant and H(r) is the Heaviside step
function which vanishes for r < 0 and gives a value of 1 for r > 0.
The function εij describes the response to postsynaptic spikes: (2).
εij (r) = [exp(−r − ∆axr − ∆ax)(1 − exp(−))]H(r − ∆ax )
τm
τs

(2)

where τs is a synaptic time constant, ∆ax is the axonal transmission delay.
The membrane potential of a neuron i at time t is given by:

 
(f )
(f )
ui (t) =ηi (t − ti ) +ωij εij (t − tj )
(3)
(f)

ti

j∈Γi t(f) ∈F

∈Fi

j

j

where Fi is the set of ﬁring times in a neuron i. The neuron i may receive theinput from presynaptic neurons j ∈ Γi . The weight ωij is the strength of theconnection from the jth neuron, and scales the amplitude of the response given
in eq.(2).

3

The Task and the Fitness Function

The control task used in this paper was motion pattern discrimination [24], and isbased on a task originally implemented by Beer [25]. The agent must discriminate
between two types of vertically falling object based on the object’s period ofhorizontal oscillation; it must catch (i.e., move close to) falling objects that havea long period whilst avoiding those with a short period (see Fig. 2). 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 tothe distance between the object and the agent. The agent can move horizontally
along the bottom of the arena. In our experiment, the agent of 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 toLong Period[12 Steps]

Short Period[4 Steps]

Catch

Avoid

Catch? Avoid?

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

the sum of the opposing horizontal forces produced by a pair of eﬀectors. It has
maximum velocity of 8. Each falling object was circular, with diameter 30, anddropped from the top of the arena with a vertical velocity of 4, a horizontal
amplitude of 30 and an initial horizontal oﬀset of ±50. An object’s horizontal
velocity was ±10 (12 steps in a period) for a long period and ±30 (4 steps in aperiod) for a short period.
The performance measure to be maximized was as follows:
F itness = 1000

N umT
rialsi=1

Pi
N umT rials(4)

where Pi = 1 − di for a long period and P i = di for a short period, di = 1 whenhdi > 60 and di = hdi /60 when hdi ≤ 60, hdi is the ﬁnal horizontal distance
between the center of the agent and the object, and N umT rials is the numberof trials for an individual (8 trials for each period).

4Computer Simulations

4.1

Simulation Conditions

For this experiment, an agent’s controller was a PNN with 7 sensory neurons, 2
fully interconnected motor neurons and Nh fully interconnected hidden neurons,
where Nh ∈ {1, 10}. The network’s connection weights and the ﬁring thresholdfor each neuron were genetically encoded and evolved. The total number ofparameters was either 33 (Nh = 1) or 240 (Nh = 10). The parameters were
mapped linearly onto the following ranges: connection weights, ω ∈ [−1.0, 1.0],
and thresholds, θ ∈ [0.0, 3.9]. The parameters of the neurons and synapses (seesection 2) were set as follows: τm = 4, τs = 10, ∆ax = 2 for all neurons and allsynapses in the network following the recommendations given in [26]. Computer
simulations were conducted using populations of size 50. Each individual was
encoded as a binary string with 10 bits for each parameter. Therefore, the total
length of the genotype was either L1 = 330 (Nh = 1) or L10 = 2400 (Nh = 10).
The standard GA (SGA) and the operon-GA (OGA) were employed to evolve
the PNN parameters. The OGA uses standard bit mutation and ﬁve additional
genetic operators: connection, division, duplication, deletion and inversion. The
probabilities for genetic operations were set at 0.3 for connection and division, 0.2
for duplication and 0.05 for deletion and inversion, based on our previous resultsin [21]. The length of the value list in a locus was 6. The genetic operation for the
SGA was standard bit mutation. For both GAs, the per-bit mutation rate, q, wasset at 1/L (0.003 for L1 and 0.000416 for L 10 ). Crossover was not used for either
GA, following Nimwegen’s suggestion [14]. Tournament selection was adopted.
Elitism5 was optionally applied. The tournament size, s, was set at {2, 6} because
the SGA prefers low selection pressure while the OGA prefers high selection
5

The ﬁttest individual of each generation was passed un-mutated to the next generation (if several individuals had the highest ﬁtness, one was randomly chosen.)

1000

1000
oga
Fitness

Fitness

elitism-oga
elitism-sga

900
sga

oga
elitism-oga

sga
900
elitism-sga

800

800
0

1000 2000 3000 4000 5000 6000

0

Generation

1000 2000 3000 4000 5000 6000
Generation(a) s = 2(b) s = 6

Fig. 3. The maximum ﬁtness at each generation for Nh = 1

1000

1000

900

800

sga

oga

elitism-sga

700

Fitness

Fitness

elitism-oga

elitism-oga

oga
900

sga

800
elitism-sga
70001000 2000 3000 4000 5000 6000
Generation(a) s = 201000 2000 3000 4000 5000 6000
Generation(b) s = 6

Fig. 4. The maximum ﬁtness at each generation for Nh = 10

pressure. A generational model was used. Each run lasted 6,000 generations. We
conducted 10 independent runs for each of the sixteen conditions. All results
were averaged over 10 runs.
4.2

Simulation Results

Fig. 3 shows the maximum ﬁtness at each generation for the SGA and OGA, withand without elitism, for controllers with N h = 1. Fig. 3(a) and 3(b) show theresults for the four GA conditions for s = 2 and 6 respectively. For s = 2, ﬁtness
increased faster with the OGA than with the SGA in the early generations.
In the ﬁnal generation, there was no signiﬁcant diﬀerence between the SGA
and the OGA. For s = 6, the SGA was trapped on local optima, whereas the
OGA continued to ﬁnd better regions of the search space. In addition, the SGA

performed better without elitism than with it. These results are consistent withthe results obtained using terraced NK landscapes [21]. With respect to ﬁnal
generation ﬁtnesses, there was no signiﬁcant diﬀerence between the SGA withs = 2 and the OGA for s = 6. However, a closer examination reveals that during
the process of evolution the OGA with s = 6 performed better than the SGA
with s = 2 and elitism.
Fig. 4 shows the maximum ﬁtness at each generation for the SGA and OGA,
with and without elitism, for s = 2 and 6 with N h = 10. With Nh = 10,
diﬀerences between the SGA and the OGA were much more pronounced thanwith Nh = 1. Even for s = 2, ﬁtness increased faster for the OGA than for
the SGA (Fig. 4(a)). This is consistent with the results obtained using simple
neutral networks when the mutation rate is below the optimal mutation rate[20]. As with N h = 1, for s = 6, the SGA with elitism was trapped on local
optima (Fig. 4(b)), whereas the OGA continued to ﬁnd better regions; also as
before, the SGA performed better without elitism than with it. The OGA fors = 6 also outperformed the SGA for s = 2.
Under all conditions, the OGA performed better than the SGA on this task,either by achieving higher ﬁnal ﬁtnesses, or by achieving high ﬁtnesses faster, or
both. This shows that the OGA’s variable mutation rate strategy was beneﬁcial
on this problem.

5

Discussion

The evolutionary dynamics observed in these experiments can be explained in
the same way as in [21].
The evolutionary dynamics that were observed showed phases of neutral evolution, implying that the ﬁtness landscapes include neutral networks. However,large ﬂuctuations that sometimes cause the best individuals to be lost were notobserved under any of the four GA conditions. That is, there was no inﬂuenceof the error threshold at the mutation rate q = 1/L. Therefore, we can assume
that the eﬀective mutation rate of q = 1/L was below the error threshold undereach condition.
The correlation of the landscapes was analyzed in order to investigate overall
GA performance. Fig. 5(a) and 5(b) show the correlation coeﬃcient [27] as afunction of the Hamming distance between parents and oﬀspring for the SGA
with and without elitism, with N h = 1 and 10 respectively. They suggest highﬁtness correlation in both landscapes, with the Nh = 10 landscape being more
highly correlated that the Nh = 1 landscape.
As predicted, with s = 6, the SGA with and without elitism was trapped on
local optima when N h = 1, due to the low mutation rate and high selection pressure. With s = 6 and Nh = 10, the SGA with elitism was also trapped on local
optima. However, the SGA without elitism for s = 6 and N h = 10 was not obviously trapped. Based on the analysis of ruggedness shown in Fig. 5(b), it seems
likely that ﬁtnesses would continue improving if the runs were extended beyond
their ﬁnal generation. Further computer simulations were therefore conducted1

sga
elitism-sga

0.8Correlation

0.8
Correlation

1

sga
elitism-sga

0.6
0.4
0.2

0.6
0.4
0.2

0

0
0

1

2

3

4

5

6

7

0

Hamming distance

1

2

3

4

5

6

7

Hamming distance(a) Nh = 1(b) Nh = 10

Fig. 5. The correlation coeﬃcient as a function of the Hamming distance between
parents and oﬀspring for the SGA

Fitness

1000

sga

900

elitism-sga

800

700
0

2000

4000

6000

8000 10000

Generation

Fig. 6. The maximum ﬁtness over 10,000 generations for the SGA for s = 6 andNh = 10in order to observe the SGA runs over an additional 4,000 generations. Fig. 6
shows the maximum ﬁtness for 10,000 generations of the SGA with Nh = 10.
The SGA without elitism continued to ﬁnd better regions of the search space.
This indicates that the SGA without elitism can escape from local optima withthis level of ruggedness.
When compared on the same landscapes, the OGA continued to ﬁnd muchbetter regions of search space than the SGA. The continued improvement observed with the OGA was due to the online adaptation of mutation rates during
the process of evolution. In addition to this, with the OGA, the eﬀective mutation rate will have been below the error threshold even with low selection
pressure (i.e. when s = 2). This is why the variable mutation rate strategy of
the OGA was a better approach on this problem with both high and low selection
pressure.

6

Conclusions

In this work, we applied the standard GA and the operon-GA to evolution ofartiﬁcial neural networks for robot control, and investigated their performanceusing diﬀerent selection pressures. Our results can be summarized as follows:– This evolutionary robotics problem does show phases of neutral evolution.
– The standard GA with low selection pressure and the operon-GA were able
to continually ﬁnd better regions of the search space.
– The standard GA can easily get trapped on local optima under conditionsof high selection pressure and a low mutation rate.
– The beneﬁts of the variable mutation rate strategy used by the operon-GA
were more pronounced with a larger genetic search space.
These results are consistent with the results of our previous experiments using
simple neutral networks and terraced NK landscapes.
The ﬁtness landscape of this evolutionary robotics problem is relatively smooth.
Future work will investigate whether these results are applicable to real-world
problems which are expected to have more rugged landscapes.

References
1. Harvey, I.: Artiﬁcial Evolution for Real Problems. In Gomi, T. (ed.): Evolutionary
Robotics: From Intelligent Robots to Artiﬁcial Life (ER’97), AAI Books (1997)
2. Smith, T., Husbands, P., O’Shea, M.: Neutral Networks in an Evolutionary
Robotics Search Space. In Proceedings of the 2001 IEEE Congress on Evolutionary
Computation (2001) 136–145
3. Thompson, A.: An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics.
In Proceedings of the First International Conference on Evolvable Systems: From
Biology to Hardware (1996) 390–405
4. Vassilev, V. K., Fogarty, T. C., Miller, J. F.: Information Characteristics and theStructure of Landscapes. Evolutionary Computation, 8(1) (2000) 31–60
5. Ohkura, K.,Ueda, K.: Adaptation in Dynamic Environment by Using GA with
Neutral Mutations. International Journal of Smart Engineering System Design, 2(1999) 17–31
6. Ebner, M., Langguth, P., Albert, J., Shackleton, M., Shipman, R.: On Neutral Networks and Evolvability, In Proceedings of the 2001 IEEE Congress on Evolutionary
Computation: CEC2001, IEEE Press (2001) 1–8
7. Knowles, J. D., Watson, R. A.: On the Utility of Redundant Encodings in
Mutation-based Evolutionary Search. In Merelo, J.J., Admidis, P., Beyer, H.-G.,
Fernandes-Villacanas, J.-L., Schwefel, H.-P. (eds.): Proceedings of Parallel Problem
Solving from Nature - PPSN VII, Seventh International Conference, LNCS 2439
(2002) 88–98
8. Rothlauf, F., Goldberg, D.: Redundant Representations in Evolutionary Computation. Evolutionary Computation, 11(4) (2003) 381–415
9. Kimura, M.: The Neutral Theory of Molecular Evolution, Cambridge University
Press, New York (1983)
10. Huynen, M., Stadler, P., Fontana, W.: Smoothness within Ruggedness: The Roleof Neutrality in Adaptation. In Proceedings of the National Academy of Science
USA, 93 (1996) 397–401

11. Reidys, C., Stadler, P., Schuster, P.: Generic Properties of Combinatory Maps Neutral Networks of RNA Secondary Structures. Bulletin of Mathematical Biology,
59 (1997) 339–397
12. Harvey, I., Thompson, A.: Through the Labyrinth Evolution Finds a Way: A Silicon
Ridge. In Proceedings of the First International Conference on Evolvable Systems:
From Biology to Hardware (1996) 406–422
13. Smith, T. Husbands, P. Layzell, P. O’Shea, M.: Fitness Landscapes and Evolvability. Evolutionary Computation, 10(1) (2002) 1–34
14. Nimwegen, E., Crutchﬁeld, J., Mitchell, M.: Statistical Dynamics of the RoyalRoad Genetic Algorithm. Theoretical Computer Science, Vol. 229, No. 1 (1999)
41–102
15. Barnett, L.: Netcrawling - Optimal Evolutionary Search with Neutral Networks.
In Proceedings of the 2001 IEEE Congress on Evolutionary Computation (2001)
30–37
16. Eigen, M., McCaskill, J., Schuster, P.: The Molecular Quasi-species. Advances in
Chemical Physics, 75 (1989) 149–263
17. Barnett, L.: Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with
Neutrality. MSc. dissertation, School of Cognitive and Computing Sciences, Sussex
University, UK (1997)
18. Nimwegen, E., Ctrutchﬁeld, J.: Optimizing Epochal Evolutionary Search:
Population-size Dependent Theory. SFI Working Paper 9810-090, Santa Fe Institute (1998)
19. Newman, M. Engelhardt, R.: Eﬀect of Neutral Selection on the Evolution of Molecular Species. In Proceedings of the Royal Society of London B, Morgan Kaufmann,
256 (1998) 1333–1338
20. Katada, Y., Ohkura, K., Ueda, K.: Tuning Genetic Algorithms for Problems Including Neutral Networks -The Simplest Case: The Balance Beam Function-. In
Proceedings of the 7th Joint Conference on Information Sciences (2003) 1657–1660
21. Katada, Y., Ohkura, K., Ueda, K.: Tuning Genetic Algorithms for Problems Including Neutral Networks -A More Complex Case: The Terraced NK Problem-. In
Proceedings of the 7th Joint Conference on Information Sciences (2003) 1661–1664
22. Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning.
Addison-Wesley (1989)
23. Maass, W., Bishop, C.M.: Pulsed Neural Networks, MIT press (1998)
24. Katada, Y., Ohkura, K., Ueda, K.: Artiﬁcial Evolution of Pulsed Neural Networks on the Motion Pattern Classiﬁcation System. In Proceedings of 2003 IEEE
International Symposium on Computational Intelligence in Robotics and Automation(CIRA) (2003) 318–323
25. Beer, R.: Toward the Evolution of Dynamical Neural Networks for Minimally Cognitive Behavior. In Maes, P., Mataric, M., Meyer, J., Pollack, J., Wilson, S. (eds.):
Proceedings of From Animals to Animats 4, MIT press (1996) 421–429
26. Floreano, D., Mattiussi, C.: Evolution of Spiking Neural Controllers. In Gomi, T.
(ed.): Evolutionary Robotics: From Intelligent Robots to Artiﬁcial Life (ER’01),
AAI Books, Springer-Verlag (2001) 38–61
27. Manderick, B., Weger, M., Spiessens, P.: The Genetic Algorithm and the Structureof the Fitness Landscape. In Belew, R., Booker, B. (eds): Proceedings of the FourthInternational Conference on Genetic Algorithms, Morgan Kaufmann (1991) 143–
150