Tuning Genetic Algorithms for Problems Including Neutral Networks- A More Complex Case: The Terraced NK Problem 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 recentyears. In a recent paper [12], we have shown that, inthe case of a very simple test function, 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 a variable mutation rate strategy is beneﬁcial
for fast and stable genetic search. In this work, we
conduct a series of computer simulations with a more
complex test function, the terraced NK landscape,in order to investigate whether our previous results
generalize to this more complex case. Two typesof GA were used. One is the standard GA, wherethe mutation rate is constant, and the other is theoperon-GA, whose eﬀective mutation rate at each locus changes independently according to the historyof the genetic search. It is found that the variable
mutation rate strategy is also beneﬁcial with thismore complex test function, and that these beneﬁts increase as the ﬁtness landscape becomes morerugged.

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 [4][5][6].
It has been shown that there is a clear transitionin evolutionary dynamics for populations on neutralnetworks over the mutation rate range. At a low mu-tation rate, the population is maintained in a cluster on the neutral network. As the mutation rateincreases, 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. This mutation rate is called the phenotypic error threshold1 [8][9][10]. This implies that
if we adopt a constant mutation rate strategy, weshould set a low mutation rate so as to avoid any error threshold eﬀects during the process of evolution.
However, from a practical point of view, it would be
eﬃcient to minimize the duration of equilibrium periods; that is, periods during which the mean ﬁtnessof the population does not change [11].
Recently, we have investigated the eﬀect of selection pressure and mutation rate on the speed of population movement on very simple neutral networks,
using the Balance Beam Function (BBF) [12]. BBF
landscapes have no ruggedness. Our results can besummarized as follows:(1) For a given population size, plotting the speedof population movement against its mutation
rate resulted in a concave curve, demonstrating
the existence of an optimal mutation rate andan error threshold for speed .
(2) Without elitism, the optimal mutation rate wasjust below the error threshold.
(3) High selection pressure improved the speed atwhich a population moved on a neutral network.
(4) A variable mutation rate strategy [13] improved
the eﬃciency of the search when the constantmutation rate was less than the optimal constant mutation rate.
1 These concepts originate from molecular evolution [7].

We are interested in whether these observations
are consistent with more complex problems including not only neutrality but also ruggedness. This isbecause we want to solve complex real-world problems. However, because of their complexity, investigating such problems is unlikely to lead to generalizable conclusions. Therefore, in this paper, we investigate the eﬀect of ruggedness by employing a more
complex test function. Tunably neutral NK landscapes [8][9] incorporate both neutrality and ruggedness. It has been demonstrated that increasing neutrality does not aﬀect the ruggedness of a tunably
neutral NK landscape, although it does reduce thenumber of local optima [5][8][9]. Thus, we cannot
neglect the eﬀect of ruggedness. In this kind oflandscape, individuals can easily get trapped on local optima if there is a low mutation rate and highselection pressure. However, using a low selection
pressure may require setting a much lower mutation
rate in order to avoid the eﬀect of an error threshold[12], and as a result evolution would proceed moreslowly. One approach to overcoming this problem
would be to adopt variable mutation rate strategies.
In this paper, we employ a standard GA, whichemploys a constant mutation rate, and the operonGA [13], which can change its mutation rate strategy. We investigate the performance of both GAs
with diﬀerent selection pressures. Section 2.1 describes the terraced NK landscape, which is used asa test problem in this work. Section 2.2 describes thesimulation conditions. Section 2.3 gives the resultsof our computer simulations. Section 3 discusses theeﬀect of the error threshold and the variable mutation rate strategy on smooth and the rugged landscapes. Conclusions are given in the last section.

2

Computer Simulations

2.1

Test Functions

A terraced NK landscape was employed as thetest function in our computer simulations. This is
the tunably neutral landscape proposed by Newman
et al. [9]. A terraced NK landscape has three parameters: N , the length of the genotype; K, thenumber of epistatic linkages between genes; and w,
the contribution of a locus to the ﬁtness of the entiregenotype.
The ﬁtness value is calculated as follows: The ﬁtness contribution of the i-th locus, wi , is an integer,generated randomly in the range 0 ≤ wi < F, i =1, · · · , N . To calculate the ﬁtness, W , of a genotype,the ﬁtness contribution of each locus is averaged,
and then divided by F − 1, normalizing W to therange 0.0 to 1.0. More formally:
NW =


1wi .
N (F − 1)

(1)

i=1

The neutrality of the landscape can be tuned byvarying the value of F . The neutrality of the landscape is maximized when F = 2, and is eﬀectively
non-existent as F → ∞.
2.2

Simulation Conditions

Computer simulations were conducted using a
population size of 50. The operon-GA [13] uses standard bit mutation and ﬁve additional genetic operators: connection, division, duplication, deletion andinversion. The probabilities for genetic operations
were set at 0.3 for connection and division, 0.2 forduplication and 0.05 for deletion and inversion, asrecommended by Ohkura and Ueda [13]. The lengthof the value list in a locus was 6. The genetic operation for the standard GA (SGA) was standard bitmutation. For both GAs, the per-bit mutation rate,q, was set at 0.01, based on Mühlenbein’s suggestion[16]. Crossover was not used with either GA. Tournament selection was adopted. Elitism2 was optionally applied. The tournament size s was set at {2, 6}
because low selection pressure is generally preferable with the SGA, whereas high selection pressure
is preferable with the OGA. A generational GA wasused. We conducted 50 independent runs for eachproblem under the landscape parameters, N = 100,K = {0, 5, 25, 50}, F = 2. Each run lasted 3,000generations (K = {0, 5, 25}) and 10,000 generations(K = 50). All results were averaged over 50 runs.
2.3

Simulation Results

Fig. 1 shows the maximum ﬁtness at each generation for the SGA and OGA, with and without
elitism, and for diﬀerent values of K and s.
For K = 0, there is no ruggedness, and the landscape is similar to simple neutral networks of theBBF. Figs. 1(a) and 1(b) show the results for thefour GA conditions for s = 2 and 6 respectively. No
signiﬁcant diﬀerences in performance were observed.
This is consistent with the results obtained with simple neutral networks using the BBF [12].
For K = 5, both GAs performed better withelitism than without it for s = 2. However, for s = 6
there was no signiﬁcant diﬀerence between the four
GA conditions. Fitness increased faster for s = 6than for s = 2.
For K = 25 and K = 50, diﬀerences between
the SGA and the OGA were much more pronounced
than at K = 0 and K = 5. As with K = 5, bothGAs performed better with elitism than without itfor s = 2. The OGA was outperformed by the SGA
for s = 2, however, the OGA outperformed the SGA
for s = 6. A closer examination reveals that theOGA performed better for s = 6 than the SGA didfor s = 2 with elitism.
2 An individual, randomly selected from those individuals
with the highest fitness value, is passed unmutated to thenext generation.

3Discussion

The evolutionary dynamics of the obtained resultsin the previous section can be explained as follows:- the eﬀect of the error threshold
When weak selection pressure is used, the SGA and
OGA both show poor performance. The OGA performs slightly worse than the SGA, as shown inFigs. 1(c), 1(e) and 1(g). This is due to the factthat the eﬀective mutation rate is more likely to
exceed the error threshold when selection pressure
is weak [10] (Fig. 2(a), 2(b)). This is consistent
with the results obtained using the BBF [12].
- the variable mutation rate strategy
The variable mutation rate strategy of the OGA is abetter approach on highly rugged landscapes whenselection pressure is high. For s = 6 and, withelitism, for s = 2, the SGA is easily trapped on
local optima when the landscape is highly rugged(K = 25 and K = 50); in contrast, on the samelandscapes, for s = 6, the OGA continues to ﬁnd
better regions. This improvement is due to the online adaptation of mutation rates during process ofevolution, as shown in Figs. 2(c) and 2(d).

4Conclusions

In this work, we applied the standard GA andthe operon-GA to terraced NK landscapes, and investigated their performance using diﬀerent levels ofruggedness and diﬀerent selection pressures. Our results can be summarized as follows:• The standard GA and the operon-GA show
very similar performance on landscapes with noruggedness. This is consistent with results ofour previous experiments using the BBF.
• Without elitism, both types of GA search inefﬁciently when landscapes are rugged and selection pressure is low.
• The beneﬁts of the variable mutation rate strategy used by the operon-GA become increasingly
clear as the ruggedness of the landscapes increases.
These results suggest some guidelines for tuning
the performance of GAs. Future work will investigate how well these tuning guidelines apply to realworld problems, such as the evolution of artiﬁcial
neural networks for robot control.

References[1] Smith, T., Husbands, P., O’Shea, M.: Neutral Networks in an Evolutionary Robotics Search Space.
Proceedings of 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ﬁrst International Conference on Evolvable Systems: From Biology to Hardware, (1996) 390–405[3] Kimura, M.: The Neutral Theory of MolecularEvolution. Cambridge University, Press, New York,(1983)[4] Harvey, I., Thompson, A.: Through the Labyrinth
Evolution Finds a Way: A Silicon Ridge. Proceedings of the ﬁrst International Conference on Evolvable Systems: From Biology to Hardware, (1996)
406–422[5] Smith, T., Husbands, P., Layzell, P., O’Shea, M.:
Fitness Landscapes and Evolvability. Evolutionary
Computation, Vol. 10, No. 1. (2002) 1–34
[6] Ebner, M., Langguth, P., Albert, J., Shackleton,M., Shipman, R.: On Neutral Networks and Evolvability. Proceedings of the 2001 IEEE Congress on
Evolutionary Computation: CEC2001, IEEE Press(2001) 1–8[7] 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[8] Barnett, L.: Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality. MSc. dissertation, School of Cognitive and Computing Sciences, Sussex University, UK, (1997)[9] Newman, M., Engelhardt, R.: Eﬀect of neutral selection on the evolution of molecular species. Proceedings of the Royal Society of London B, 256,Morgan Kaufman, (1998) 1333–1338[10] Nimwegen, E., Ctrutchﬁeld, J.: Optimizing epochal
evolutionary search: Population-size dependent
theory. SFI Working Paper 9810-090, Santa Fe Institute, (1998)[11] Nimwegen, E., Crutchﬁeld, J., Mitchell, M.: Statistical dynamics of the royal road genetic algorithm.
Theoretical Computer Science, Vol. 229, No. 1,(1999) 41-102[12] Katada, Y., Ohkura K., Ueda, K.: Tuning Genetic Algorithms for Problems Including Neutral
Networks - The Simplest Case: The Balance Beam
Function -. Proceedings of the Sixth International
Conference on Computational Intelligence and Natural Computing (2003) will be published[13] 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[14] Eigen, M., McCaskill, J., Schuster, P.: The Molecular Quasi-species. Advances in Chemical Physics,
75, (1989) 149-263[15] Yasuda, Y., Ohkura, K., Ueda, K.: The Balance
Beam Function : A New Test Function for theReal World Problems. Proceedings of Intelligent
Autonomous Vehicles (2001)[16] Mühlenbein, H.: Evolutionary Algorithms: Theory and Applications. Technical paper: citeseer.nj.nec.com/110687.html (1993)

0.90

0.90
elitism-oga

0.80

sga

elitism-sga

oga

sga

0.70

oga

0.80

elitism-sga

elitism-oga

0.70

0.60

0.60
0500

1000 1500 2000 2500 3000

0500

1000 1500 2000 2500 3000

Generation

Generation(a) (K, s) = (0, 2)(b) (K, s) = (0, 6)

1.00

1.00
elitism-sga

0.95

elitism-sga

oga

0.95

0.90

0.90
elitism-oga

0.85

sga

sga

elitism-oga

0.85

0.80

0.80
oga

0.75

0.75

0.70

0.70
0500

1000 1500 2000 2500 3000

0500

1000 1500 2000 2500 3000

Generation

Generation(c) (K, s) = (5, 2)(d) (K, s) = (5, 6)

0.85

0.85

elitism-oga

elitism-sga
0.80

oga

0.80
elitism-oga

0.75
sga

0.700.65

sga

elitism-sga

0.75
0.70
0.65

oga

0.60

0.60
0500

1000 1500 2000 2500 3000
Generation

0500(e) (K, s) = (25, 2)1000 1500 2000 2500 3000
Generation(f) (K, s) = (25, 6)

0.65

0.65

oga

elitism-sga
0.60

elitism-oga

0.60
elitism-oga

0.55

elitism-sga

0.55

sga

sga
0.50

0.50
oga

0.45

0.45
02000

4000 6000
Generation8000

10000

02000

(g) (K, s) = (50, 2)4000 6000
Generation

8000

10000

(h) (K, s) = (50, 6)

0.05

0.05

0.04

0.04

0.04

0.03
0.02

0.03
0.02

0.03
0.02

0.01

0.01

0.01

0.00

0.00

0.00

02000

4000

6000

8000 10000

02000

Generation(a) s = 2, elitism

4000

6000

8000 10000

Generation(b) s = 2,without elitism

Mutation rate

0.05

0.04

Mutation rate

0.05

Mutation rate

Mutation rate

Figure 1: The maximum ﬁtness

0.03
0.02
0.01
0.00

02000

4000

6000

8000 10000

02000

Generation(c) s = 6, elitism

4000

6000

8000 10000

Generation(d) s = 6,without elitism

Figure 2: Average eﬀective mutation rate by Operon-GA for K = 50 in a typical run