Tuning Genetic Algorithms for Problems Including Neutral Networks- The Simplest Case: The Balance Beam Function 1

Yoshiaki Katada1 , Kazuhiro Ohkura2 and Kanji Ueda3
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 research interest in recent years. In this work, we applied a standard GA
and an extended GA with a variable mutation rate
strategy to an abstract model of neutral networks inorder to investigate the eﬀects of selection pressure
and mutation rate on the speed of population movement. Our results demonstrate that speed has an
optimal mutation rate and an error threshold sinceplotting speed against mutation rate results in a concave curve. Increasing selection pressure increased
the speed of a population’s movement on a neutralnetwork. The variable mutation rate strategy of theextended GA improved the eﬃciency of the search.
For both GAs, we found that high selection pressure
was preferable, both for increasing the speed of population movement and for avoiding the eﬀects of anerror threshold on a neutral network.

1Introduction

Selective neutrality has been found in many realworld applications of artiﬁcial evolution, such as theevolution of neural network controllers in robotics[1], and on-chip electronic circuit evolution [2]. This
characteristic, caused by highly redundant mappingsfrom genotype to phenotype, is also found in natural systems, and has been of particular interest to
evolutionary theorists and molecular biologists [3].
Landscapes which include neutrality have been conceptualized as containing neutral networks.
Harvey [4] ﬁrst introduced the concept of neutral
networks into the GA community. His deﬁnition is
as follows: “A neutral network of a ﬁtness landscapeis deﬁned as a set of connected points of equivalentﬁtness, each representing a separate genotype: here
connected means that there exists a path of single(neutral) mutations which can traverse the network
between any two points on it without aﬀecting ﬁt-ness.”
It has been shown that there is a clear transitionin evolutionary dynamics for populations on neutral
networks over the mutation rate range. At a very
low mutation rate, the population is maintained in acluster on the neutral network, analogously to quasispecies [5]. As the mutation rate increases, the population gradually loses the current network. That is,some individuals fall to lower neutral networks. At
a certain critical mutation rate, the whole population will have fallen to lower neutral networks. Thismutation rate is called the phenotypic error threshold1 [7][8]. Generally, the error threshold sets theupper limit for a mutation rate that will enable eﬃcient search. This implies that if we adopt a constantmutation rate strategy, we should set a low mutation
rate so as to avoid any error threshold eﬀects during the process of evolution. From a practical pointof view, however, it would be eﬃcient to shorten theequilibrium period2 which dominates the whole computation (Fig. 1). One approach would be to employ
variable mutation rate strategies, which change theeﬀective mutation rate adaptively during the processof evolution. Another would be to investigate the effects of the constant (base) mutation rate, selection
pressure and population size on search eﬃciency.
In this paper, we employ a standard GA, whichemploys a constant mutation rate, and an extended
GA, which can change its mutation rate strategy, inorder to investigate the eﬀect of the selection pressure and mutation rate on the speed of populationmovement. Section 2 describes an abstract modelof very simple neutral networks, called the Balance
Beam Function, which is used as a test problem inthis work. Section 3 gives the results of our computer
simulations. Section 4 discusses the eﬀect of selection pressure and the variable mutation rate strategy
1 These concepts originate from molecular evolution [6].

2 An equilibrium period is a period during which mean fitness of the population does not change [8].

Best
MeanFitness

Transient period

Equilibrium period

GenerationFigure 1: Typical evolutionary dynamics on a ﬁtnesslandscape featuring neutral networks, which can beclassiﬁed into transient periods and equilibrium periods [8]: Instead of being stuck in a local optimum,
populations may be exploring in the genotype space.
on the evolutionary dynamics on the simple neutral
networks. Conclusions are given in the last section.

2Abstract Model of Simple Neutral
Networks

The Balance Beam Function, proposed by Yasuda
et al. [9], was employed as the test function in our
computer simulations. It is relatively easy to investigate evolutionary dynamics with this function,
because it has a landscape composed of only twoneutral networks, each of a diﬀerent ﬁtness—one ofwhich has the shape of a “balance beam”. The Balance Beam Function (BBF) is formulated as follows:lF = 1.0, if (A ≤ i=1 si ≤ B) and F = 0.0, otherwise, where F , l and si ∈ {0, 1} are the ﬁtness value,
the length of the genotype and the value of the i-thlocus, respectively. A and B (0 < A < B ≤ l)are constant integers. The neutrality is tunable bychanging A and B. The abstract width, w, of aneutral pathway is calculated as B − A. We focus
on the moving speed of the individuals which keep
remaining on the higher neutral network (F = 1.0).
As the initial setting, all individuals in the population are placed on a particular point on the higher
neutral network, for instance, si = 1, i = 1, . . ., dand si = 0, i = d + 1, . . . , l, where d is a constantinteger between A and B. This would be a situation similar to a population just after a transition
period. In the process of evolution, each individual
moves along the pathway by ﬂipping the values ofloci. Distance is deﬁned as the number of 0s between the 1st locus and the d-th locus if the individual is on the higher neutral network. Distanceis not deﬁned for an individual on the lower neutral
network. Therefore, the moving speed of a population can be measured as the number of generations(for generational GAs), or the number of evaluations(for steady state GAs) for one of individuals to reachthe furthest distance, d. For the BBF, the optimal
mutation rate, q o , is identiﬁed as the mutation ratewhich results in the fastest speed over the mutation

rate range. The phenotypic error threshold, qerr , isidentiﬁed as the mutation rate where the transition
mentioned in Section 1 occurs.

3

Computer Simulations

3.1

Simulation Conditions

Computer simulations were conducted by setting
the population size to 50 and the length of the genotype to 200. The extended GA used in this paperis called the operon-GA [10]. The operon-GA 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.1
for duplication and 0.05 for deletion and inversion,
as recommended by Ohkura and Ueda [10]. The
length of the value list in a locus was 6. The genetic operation for the standard GA was standard
bit mutation. For both GAs, the per-bit mutation rate, q, was set between 0.00001 and 0.1 withstep sizes of ∆q = 0.0001 (if q < 0.001), 0.001 (if0.001 ≤ q ≤ 0.01) and 0.01 (if 0.01 < q ≤ 0.1).
Crossover was not used for either GA. Tournament
selection was adopted. Elitism3 was optionally applied. The tournament size was set at s = 2, 4and 6. A generational GA was used. Each run
lasted 10,000 generations4 . We conducted 10 independent runs for each problem with the parameters(A, B) = (19, 20), (19, 24), (19, 29) and (19, 39); thatis, with neutral pathways of width w = 1, 5, 10 and
20. d was set at 19. All results were averaged over
10 runs.
3.2

Simulation Results

Fig. 2 and 3 show the average number of generations to reach the furthest distance, d, with s ={2, 4, 6} and w = {1, 5, 10, 20}, for non-elitism andelitism, for the standard GA (SGA) and the operonGA (OGA) respectively. The curves are U-shaped
as a function of the mutation rate, q, and have an
optimal mutation rate and an error threshold.
With non-elitism, the speed falls sharply when q
exceeds qo . Moreover, the optimal mutation rate isjust below the error threshold (Fig. 2(a), 2(b) andFig. 3(a), 3(b)). With elitism, both the optimal mutation rate and the error threshold increase, and sodoes the distance between them (Fig. 2(c), 2(d) andFig. 3(c), 3(d)).
Increasing the tournament size increases the optimal mutation rate and the error threshold. It also
results in improved speeds over the mutation rate
range qo < q < qerr (Fig. 2(a), 2(c) and Fig. 3(a),3(c)). Due to space restrictions we only show results
3 An individual, randomly selected from those individuals
whose fitness value is 1.0, is passed unmutated to the next
generation.
4 If no individual reaches the furthest distance by the final
generation, the number of generations to reach the furthest
distance is taken to be 10, 000.

for w = 1. However, increasing tournament size had
the same eﬀect for all widths.
The OGA produced higher speeds than the SGA
when q was below qo both with non-elitism andelitism (Fig. 4). Fig. 5 shows the average eﬀective
mutation rate in an OGA population for non-elitismand elitism, with s = 6, w = 1 and a per-bit mutation rate q = 0.001. (The evolutionary dynamics
shown are representative of all OGA runs in thisstudy.) The eﬀective mutation rate is calculated as
the number of ﬂipped bits per genotype after the genetic operators have been applied. It is distributed
around the optimal mutation rate q o = 0.006 (fornon-elitism) and qo = 0.01 (for elitism).

4Discussion

Our results suggest that optimal mutation rates
and error thresholds are strongly correlated with selection pressure. With non-elitism, the optimal mutation rate will be just below the error threshold.
If the mutation rate is set by estimating the optimal mutation rate, a misjudgement could result in
the error threshold being exceeded, and thus lead topoor performance. With higher selection pressure,the optimal mutation rate and error threshold bothincrease. Elitism improves the moving speed whenq is larger than qo . Note that extreme elitism (e.g.
50% of oﬀspring are identical to their parents) will
reduce the moving speed, since the population willtend to repeatedly sample the same genotypes [11].
This may be related to the eﬀects of sampling ﬂuctuation. Nimwegen et al. [8] have suggested that
there is an appreciable chance that all individuals
on higher neutral networks will be lost through sampling ﬂuctuations5 . From these results, we can saythat high selection pressure decreases the probability
with which the individuals are lost through sampling
ﬂuctuation, with the result that the optimal mutation rate and error threshold are shifted to higher
mutation rates. This would explain why, when q exceeds qo , the moving speed improves if (relatively)
high selection pressure is applied.
We have also shown that, for the BBF, the variable mutation rate strategy of the OGA improves
the eﬃciency of the search when q is less than qo , asa result of adaptively varying the eﬀective mutation
rate.

5Conclusions

We have investigated the eﬀect of the selection
pressure and the mutation rate on the speed of population movement on landscapes with diﬀerent levelsof neutrality, using a standard GA and the operonGA. Our results can be summarized as follows: (1)For a given population size, the speed of a population plotted as a function of the mutation rate
5 Higher neutral networks will tend to have narrower neutral pathways, with more bits on the genotype being subject
to selective constraints.

yields a concave curve with an optimal mutation rate
and an error threshold. (2) When non-elitism is employed, the optimal mutation rate will be just below
the error threshold. (3) If the mutation rate exceeds
the optimal mutation rate, increasing the selection
pressure will improve the speed at which a population moves on a neutral network. (4) The variable
mutation rate strategy in the operon-GA improves
search eﬃciency when the constant mutation rate isless than the optimal constant mutation rate.
Establishing the generality of these results will require investigating the performance of the standard
GA and the operon-GA on more complex problems.
However, our recent experiments with a more complex problem, terraced NK landscapes, suggest thatthese results may generalize well [12].

References[1] Smith, T., Husbands, P., O’Shea, M.: Neutral Networks
in an Evolutionary Robotics Search Space. Proceedingsof the 2001 IEEE Congress on Evolutionary Computation, (2001) 136–145[2] Thompson, A.: An Evolved Circuit, Intrinsic in Silicon,
Entwined with Physics. Proceedings of the first International Conference on Evolvable Systems: From Biologyto Hardware, (1996) 390–405[3] Kimura, M.: The Neutral Theory of Molecular Evolution. Cambridge University, Press, New York, (1983)[4] Harvey, I., Thompson, A.: Through the Labyrinth Evolution Finds a Way: A Silicon Ridge. Proceedings ofthe first International Conference on Evolvable Systems:
From Biology to Hardware, (1996) 406–422[5] Eigen, M., McCaskill, J., Schuster, P.: The Molecular
Quasi-species. Advances in Chemical Physics, 75, (1989)
149-263[6] Huynen, M., Stadler, P., Fontana, W.: Smoothness
within ruggedness: The role of neutrality in adaptation.
Proceedings of the National Academy of Science USA,93, (1996) 397–401[7] Barnett, L.: Tangled Webs: Evolutionary Dynamics onFitness Landscapes with Neutrality. MSc. dissertation,
School of Cognitive and Computing Sciences, Sussex
University, UK, (1997)[8] Nimwegen, E., Crutchfield, J., Mitchell, M.: Statistical
dynamics of the royal road genetic algorithm. TheoreticalComputer Science, Vol. 229, No. 1, (1999) 41-102[9] Yasuda, Y., Ohkura, K., Ueda, K.: The Balance Beam
Function : A New Test Function for the Real World
Problems. Proceedings of Intelligent Autonomous Vehicles (2001)[10] Ohkura, K.,Ueda, K.: Adaptation to Dynamic Environment using Genetic Algorithm with Neutral Mutations.
International Journal of Smart Engineering System Design, 2, (1999) 17–31[11] Bullock, S.: Will selection for mutational robustness significantly retard evolutionary innovation on neutral networks?. Standish, R., Bedau, M., Abbass, H. (eds.): Proceedings of the Eighth International Conference on Artificial Life, MIT Press, (2002) 192-201[12] Katada, Y., Ohkura K., Ueda, K.: Tuning Genetic Algorithms for Problems Including Neutral Networks - A
More Complex Case: The Terraced NK Problem -. Proceedings of the Sixth International Conference on Computational Intelligence and Natural Computing (2003)
will be published

6000
4000
2000

6000
4000

1.0e-010
1.0e-04(a) w = 1, non-elitism
w=1
w=5
w=10
w=20

8000
6000
4000

1.0e-031.0e-02
Mutation rate

1.0e-01

6000
4000

0
1.0e-04

1.0e-031.0e-02
Mutation rate

0.025

6000
4000

1.0e-010
1.0e-04(a) w = 1, non-elitism
w=1
w=5
w=10
w=20

8000
6000
4000

w=1
w=5
w=10
w=20

8000

(b) s = 6, non-elitism

1.0e-01

1000
1500
Generation2000(a) non-elitism

0.025

6000
4000

0.02
0.015
0.010.005

2000
1.0e-031.0e-02
Mutation rate

500

0.03

10000

2000
0
1.0e-04

01.0e-01(c) w = 1, elitism

Generation

10000

0.01

0
1.0e-031.0e-02
Mutation rate

Mutation rate

1.0e-031.0e-02
Mutation rate

0.02
0.015

0.005

2000

0
1.0e-04

1.0e-01

Figure 4: Comparison between theSGA and the OGA (w = 1, s = 6)

s=2
s=4
s=6

8000

2000

1.0e-031.0e-02
Mutation rate(b) elitism

Mutation rate

40000
1.0e-04

1.0e-01

0.03

10000Generation

Generation

6000

4000

(d) s = 6, elitism

s=2
s=4
s=6

8000

6000

2000

Figure 2: Average generations to reach the furthest
distance in ten runs by the SGA

10000

1.0e-01

sga
oga

8000

2000
1.0e-031.0e-02
Mutation rate

1.0e-031.0e-02
Mutation rate(a) non-elitism

w=1
w=5
w=10
w=20

8000

(b) s = 6, non-elitism

Generation0
1.0e-04

1.0e-01

10000

10000

2000
0
1.0e-04

4000(c) w = 1, elitism

Generation

10000

6000

2000

Generation

1.0e-031.0e-02
Mutation rate

sga
oga

8000

2000

0
1.0e-04

Generations=2
s=4s=68000
Generation

Generation

8000

10000

10000

s=2
s=4s=6

Generation

10000

0
1.0e-040
1.0e-031.0e-02
Mutation rate(d) s = 6, elitism

Figure 3: Average generations to reach the furthest
distance in ten runs by the OGA

1.0e-01

0500

1000
1500
Generation

2000(b) elitism

Figure 5: Eﬀective mutation rate by
the OGA (w = 1, s = 6, q = 0.001)