Evolutionary Dynamics of GAs in a Simple Model with
Dynamical Environment and Neutrality
Yoshiaki Katada1
1

Setsunan University, Osaka 572-8508, JAPAN
katada @ ele.setsunan.ac.jp

Abstract
Biological organisms have various mechanisms of copingwith the dynamical environments in which they live. Recent papers in computational biology show that individuals
reside in deferent regions of neutral networks according toenvironmental variation. This work investigated evolutionary
dynamics of GAs in dynamical environments with neutrality
using a simple model. The evolutionary dynamics observed
were consistent with those observed in the experiments of biological evolution, confirming that the genotype distributions
change depending on the rates of environmental variation as
well as mutation.

Introduction
The Neutral theory (Kimura, 1983) was developed by Motoo
Kimura in the 1960s. Neutrality is caused by highly redundant mappings from genotype to phenotype or from phenotype to fitness. Based on this, it was reported that biologicalorganisms make good use of genetic mechanisms which do
not appear in phenotype to adapt to environmental variations
on the evolutionary time scale.
The effects of neutrality has been discussed so much in
the EC community especially since Harvey introduced theconcept of neutral networks (Harvey and Thompson, 1996).
These researches can be classified into two types as follows. The former researches are based on redundant mappings from phenotype to fitness, where neutral networks
are included in a problem itself. Examples would be theevolution of neural network controllers in robotics (Harvey,
1997; Smith et al., 2001) and on-chip electronic circuit evolution (Thompson, 1996; Vassilev et al., 2000). In these researches, evolutionary dynamics are investigated (Barnett,
1997; Newman and Engelhardt, 1998; van Nimwegen et al.,
1999; Katada et al., 2004) or the degree of neutrality in fitness landscapes is estimated (Smith et al., 2002; Katada and
Ohkura, 2006). The latter based on redundant mappingsfrom genotype to phenotype, where redundancy, that is, neutrality has been intentionally incorporated by EC researchers
for problems where redundancy is largely absent to improve
the performance of artificial evolution (Ohkura and Ueda,

1999; Ebner et al., 2001; Knowles and Watson, 2002; Rothlauf and Goldberg, 2003).
To the best of my knowledge, in the former type of research, neither evolutionary dynamics nor useful genetic
operators in dynamical environment has been investigated.
Independently of neutrality, representations of polyploid
model in dynamical environment have been investigated
where useful genes in previous environments are preservedin some kind of memories (Branke, 2001). Apparently, thefeature of polyploidy is a redundant genetic material, that is,redundant mappings from genotype to phenotype. However,it seems likely that there is no research that investigate thisfrom the view point of neutrality.
GP, whose evolved programs include many introns andfunctionally redundant parts, would be classified into theformer research. That is why some GP researchers haveclaimed the importance of neutrality in recent years (Yu andMiller, 2006; Miller, 2009; Vanneschi, 2009).
Recent papers in computational biology show that individuals reside in deferent regions of neutral networks according to environmental variation. Meyers et al. (2005)
analyzed evolution in a periodically changing environment
using a simple model and a codon model where a locus
has several alleles and some of them are functionally equal,
and reported as follows: When environmental variations are
rare, most individuals are located in the center of the neutral network with the highest fitness value in each environment preparing for detrimental mutation (Fig. 1(a)). Thisphenomenon is called genetic robustness. When the rates
of environmental variation are intermediate, most individuals are located in the edge of the neutral network in orderto obtain a new phenotype which can adapt to an alternating environment with a few mutations (Fig. 1(b)). This iscalled genetic potential. When the rates of environmental
variation are high, they are settled in a phenotype with anintermediate fitness value in both environments (Fig. 1(c)).
This would mean that they have tolerances and adaptivity
for both environments but would never go to extremes. Thisis called organismal flexibility.
Based on these knowledges, Yu (2007) investigated evolu-

Fitness

Fitness

Neutralal networkn
Neutral network

Environmental
variation

Environmental
variation(a) small environmental variation(b) intermediate environmental variation

Fitness

Neutral network

Environmental
variation(c) large environmental variation

Figure 1: Distribution of individuals due to environmental variation

tionary dynamics of the GP in a boolean parity problem under environmental variations. It was reported that when thevariation rate is high, the length of a program tree became
long, that is, the effective mutation rate per individual became high, and when the variation rate is low, the length became short, that is, the effective mutation rate per individual
became low. Yu (2007) claimed that when the variation rate
becomes high, individuals of the GP tend to be located in
the edge of the neutral network because the effective mutation rate per individual becomes high and individuals easilychange their phenotype. However, we have trouble defining
a neutral network on GPs due to its representation. Therefore, it is difficult to discuss directly the consistency of theobtained results in the GP to the computational biology because we need the concept of location on a neutral network
for them.
Based on these results, the question arises as to whether
we can get the same kind of dynamics of GAs in dynamical environments with neutrality because neutral networks
have been found in GAs with highly redundant mappingsfrom phenotype to fitness. In the case of GAs with redundant mappings from genotype to phenotype (including polyploidy), we would get the same kind of results on the “GPs”
mentioned above because it would be difficult for the GAs
to devise a neutral network 1 and effective mutation rates of
1

It is possible to define a neutral network in GAs with redundantthem are variable.
This paper focuses on the former case, where GAs withredundant mappings from phenotype to fitness (more precisely, genotype to fitness) that can form neutral networks
and investigates evolutionary dynamics of them in a simple
model by varying the rates of environmental variation andthe mutation rate. The paper is organized as follows. The
next section describes a neutral network in a mathematicalform. Section III describes a simple model of dynamical
environments with neutrality where evolutionary dynamics
of GAs is investigated. Section IV gives the results of ourcomputer simulations. Section V discusses the consistencies
with the results obtained in computational biology. Conclusions are given in the last section.

A Formal Definition of a Neutral Network
Katada and Ohkura (2009) defined a neutral network in amathematical formula. The details are as follows;
In this study, it is assumed that genotypes are represented
as binary strings and the length of them is fixed. Thus, thegenetic distance between two different genotypes (xg , y g ∈Φg , xg 6= y g , Φg : the set of genotypes determined by thelength of the genotype, l) is described by the Hamming dismappings from genotype to phenotype (See the next section) but
difficult to make neutral networks emerge from genotype space inwhich neutrality is intentionally incorporated as mentioned earlier.

tance between them, H(xg , y g ). Thus, min H(xg , y g ) is
the smallest unit of mutation. For binary representations,min H(xg , y g ) = 1.
Based on the above consideration, I describe a neutral
network caused by redundant mappings from genotype tophenotype in a mathematical form. At first, two individuals, xg and z g , are connected, xg ∼ z g , if there exists{xgi }ni=0 ⊂ Φg , s.t.

Table 1: Set of genotype
Genotype (gi )
1011
1111
1101
1001
1010
0011
1110
1000
0111
0001
0100
0110
0010
0000
0101
1100

1. xg = xg0 , z g = xgn ,2. fg (xgi ) = fg (xg ),3. H(xgi , xgi+1 ) = 1,
where fg is the mapping from genotype to phenotype, fg :
Φg → Φp , and assumed to be surjective and not injective.
Φp is defined as the set of phenotypes.
Thus, a neutral network of a genotype z g is′

Φg (z g ) = {xg ∈ Φg |xg ∼ z g }.

(1)

We can extend this definition to redundant mappings fromphenotype to fitness.
Two individuals, xg and z g , are connected, xg ∼ z g , if there
exists {xgi }ni=0 ⊂ Φg , s.t.

0110
0010

ID (i)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

0111

0011
0100

Nickname
NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5
1110

1010
0101

1111

1011
1100

1101

1. xg = xg0 , z g = xgn ,2. (fp ◦ fg )(xgi ) = (fp ◦ fg )(xg ),0000

3. H(xgi , xgi+1 ) = 1,

1000

1001

Figure 2: Space of genotype

where fp is the mapping from phenotype to fitness, fp :
Φp → Φf , and assumed to be surjective and not injective.
Φf is defined as the set of fitness values. Addition to thisassumption, there would be two cases on fg , which is either bijective, or surjective and not injective. In both cases,
however, fp ◦ fg is surjective and not injective only if fp
is surjective and not injective. Thus, a neutral network of agenotype z g is described in the both cases as follows:Φ∗g (z g ) = {xg ∈ Φg |xg ∼ z g }.

0001

(2)

These may seem to be cumbersome at first. But this elegant definition allows us to understand clearly a setting forcomputational experiments in the following sections.

Simple Model with Dynamical Environment
and Neutrality
In this study, computer simulations were conducted in order
to compare evolutionary dynamics of GAs with those observed in the experiments of biological evolution (Meyers
et al., 2005). For performing simple analysis, the length ofa string is set at 4. According to the setting given in the reference (Meyers et al., 2005), a set of genotypes is definedas Table 1 and Fig.2. The fitness function is also defined asfollows:(0 ≤ i ≤ 5)
1 + swA (gi ) = 1 + ks (6 ≤ i ≤ 9)
(3)


1
(10 ≤ i ≤ 15)(0 ≤ i ≤ 5)
1wB (gi ) = 1 + ks (6 ≤ i ≤ 9)
(4)


1+s
(10 ≤ i ≤ 15),

where wA and wB are fitness functions for environments EA
and EB , respectively. s and k (s > 0, 0 ≤ k ≤ 1) are the parameters to adjust the highest and intermediate fitness values
given to certain genotypes in each environment, respectively.
These parameters were set as follows: s = 1, k = 0.5 following the recommendations given in (Meyers et al., 2005).
In this function, a fitness value is assigned to a genotype
directly so no phenotype is defined. Thus, it is consideredthat fg is bijective as mentioned in the previous section.
Then fp ◦ fg is investigated. According to the definition of
a neutral network (Eq.(2)), the genotypes with i = 0, · · · , 5

1.0

NN1
INVs
NN2

0.8

Phenotype distribution

and those with i = 10, · · · , 15 form a neutral network inboth environments, EA and EB , respectively. These neutral
networks show the highest fitness value and lowest fitness
value in Eqs. (3) and (4), respectively. In each neutral network, a genotype which does not mutate out of its neutral
network with 1 bit is considered to be located at the centerof its neutral network (NN1-c and NN2-c in Table 1) while agenotype which does mutate out of its neutral network with
1 bit is considered to be located on the edge of its neutral network (NN1-e and NN2-e in Table 1). For this setting, eachneutral network has only one genotype which is located at
the center of it. The other genotypes (i = 6, · · · , 9) show
the intermediate fitness value but do not form any neutral
networks.

0.6

0.4

0.2

0.0
10

20

30

40

50
60
Generation

70

80

90

100

90

100

(a) λ = 2
1.0

NN1
INVs
NN2

In this computer simulations, the GA (Goldberg, 1989) wereadopted to evolve individuals in both the environments, EA
and EB , mentioned in the previous section. The length of
the genotype is 4 as also mentioned in the previous section.
The population size was set at 10 according to the setting in(Yu, 2007). In this study, computer simulations were conducted in order to investigate evolutionary dynamics of GAs
in a simple model by varying the rates of environmental variation and the mutation rate. Thus, the genetic operations for
the GA were standard bit mutation and fitness proportionate
reproduction. The per-bit mutation rate, q, was set as follows: q ∈ {0.025, 0.05, 0.1, 0.2, 0.25, 0.3, 0.4, 0.5}. Eachrun lasted 2,000 generations. The initial environment was
set at EA . The environment was alternately switched every λ generations as follows: EA → EB → EA → · · · .
For each run, λ was set between 1 and 1000 as follows:λ ∈ {1, 2, · · · , 20, 30, · · · , 100, 200, · · · , 1000}. 50 independent runs were conducted for each parameter. All results
were averaged over 50 runs.
Fig. 3 shows the ratio of the individuals with the highest fitness value, f = 1 + s, the intermediate value, f =1 + ks, and the lowest value, f = 1 with q = 0.025 andλ = {2, 10, 100} 2 . For each λ, a population adapted to a
new environment to produce the individuals with the highest
fitness value. However, not all individuals converged to thehighest fitness value.
The distribution of the individuals were dependent on
λ. For short variable periods (e.g. λ = 2 in Fig. 3(a)),
more than the half of individuals never had the highest fitness value and the individuals with the intermediate fitness
value were dominant (approximately 45-50 %). This is because environmental variation was so rapid that there was
not enough time for the individuals to adapt to each environment. This might be considered that evolution supported theindividuals which can adapt faster to rapid environmental
2

I plot only the first 100 generations for λ = 2, 10 and the first
400 generations for λ = 100 because the similar patterns wererepeatedly observed after the generations.

0.6

0.4

0.2

0.0
10

20

30

40

50
60
Generation

7080(b) λ = 10
1.0

NN1
INVs
NN2

0.8

Phenotype distribution

Computer Simulation

Phenotype distribution

0.8

0.6

0.4

0.2

0.0
50

100

150

200
Generation

250

300

350

400

(c) λ = 100

Figure 3: Individual distributions at each generation (q =0.025)

variations, that is, the individuals which can mutate easily
to the one with the highest fitness value. Such individuals
with the intermediate fitness value would be considered to
be organismal flexibility as mentioned earlier.
For longer variable periods (e.g. λ = 10 in Fig. 3(b)),
the number of the individuals with the highest fitness value
increased while the number of the ones with the intermediate
fitness value decreased. For even longer variable periods(e.g. λ = 100 in Fig. 3(c)), there was enough time for theindividuals to adapt to each environment and the individuals
with the highest fitness value became dominant. In Fig. 3,
we can not find “where” the individuals are located in theneutral network with the highest fitness. The more details
can be found in Figs. 4 and 5.

Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2
Genotype frequency

0.3

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(a) q = 0.025, EA

Genotype frequency

0.2(b) q = 0.025, EB
0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2
Genotype frequency

0.3

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(c) q = 0.05, EA

Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(e) q = 0.1, EA

Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2

0.1

0
100

103

(f) q = 0.1, EB

Genotype frequency

0.3

103

(d) q = 0.05, EB

Genotype frequency

0.3

103

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

101
102
Length of environmental epoch(g) q = 0.2, EA

103

0
100

101
102
Length of environmental epoch(h) q = 0.2, EB

Figure 4: Individual distributions over variable periods for EA and EB (0.025 ≤ q ≤ 0.2)

103Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2
Genotype frequency

0.3

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(a) q = 0.25, EA

Genotype frequency

0.2(b) q = 0.25, EB
0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2
Genotype frequency

0.3

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(c) q = 0.3, EA

Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2

0.1

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

0
100

101
102
Length of environmental epoch

0
100

103

101
102
Length of environmental epoch(e) q = 0.4, EA

Genotype frequency

0.2

0.3

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.2

0.1

0
100

103

(f) q = 0.4, EB

Genotype frequency

0.3

103

(d) q = 0.3, EB

Genotype frequency

0.3

103

NN1-c
NN1-e1NN1-e2
NN1-e3
NN1-e4NN1-e5
INV-1
INV-2
INV-3
INV-4
NN2-c
NN2-e1NN2-e2NN2-e3NN2-e4NN2-e5

0.1

101
102
Length of environmental epoch(g) q = 0.5, EA

103

0
100

101
102
Length of environmental epoch(h) q = 0.5, EB

Figure 5: Individual distributions over variable periods for EA and EB (0.25 ≤ q ≤ 0.5)

103

Figs. 4 and 5 show the ratios of the genotypes over λs
for each q. Here, the ratio of a genotype was calculated by
dividing the sum of the values just before generations whenthe environment was switched with the number of switchingenvironments and the number of runs. The bold line shows
the ratio of the genotype which is located at the center of
its neutral network and the thin line shows the one of the
genotype which is located on the edge of its neutral network.
The horizontal axis is based on a logarithmic scale.
Over the mutation rate range 0.025 ≤ q ≤ 0.1 (Fig. 4(a)4(f)), for long variable periods, the ratio of the genotype
which was located at the center of the neutral network withthe highest fitness value was larger than the ones of theother genotypes in both environments. The genotypes whichwere located on the edge of the neutral network attained thesecond-largest rate. For shorter variable periods, the ratiosof the genotypes which were located on the edge of the neutral network were larger than the ones of the other genotypes. Among them, the ratios were different due to theirown locations on the edge. Thus, the ratios of them which
are adjacent to not only the genotypes with the intermediate
fitness value but also the ones with the lowest fitness value
were larger. The variable period range in which this phenomenon appears decreased with the increase of q. For evenshorter variable periods (approximately 1 ≤ λ ≤ 3), the ratio of the genotype with the intermediate fitness value waslargest. For these shortest variable periods, the same result
was obtained in Fig. 3(a).
Over the mutation rate range 0.2 ≤ q ≤ 0.4 (Fig. 4(g)4(h), Fig. 5(a)-5(f)), for long variable periods, the ratios of
the genotypes which were located at the center of the neutral
network and on the edge of it were large in this order. However, these values were not beyond 0.1. For even shorter
variable periods, the ratios of the genotypes with the lowest
fitness value were a few larger than or equal to the ones withthe highest and intermediate fitness value.
For q = 0.5 (Fig. 5(g)-5(h)), there was no significant difference between the genotypes, which were distributed randomly.

Discussion
In the earlier section, the loosely defined phenomena, genetic robustness, genetic potential and organismal flexibility,
were cited. In order to discuss the results obtained in the previous section, those are more accurately defined as follows:
genetic robustness: the state where the ratio of the genotype
which is located at the center of the neutral network withthe highest fitness value is largest in the environment, EA or
EB . genetic potential: the state where the ratio of the genotype which is located on the edge of the neutral network islargest in each environment. organismal flexibility: the state
where the ratio of the genotype with the intermediate fitness
value is largest.
According to these definitions, we can find such phasetransitions as organismal flexibility → genetic potential →genetic robustness for q ≤ 0.1, and organismal flexibility→ genetic robustness for 0.2 ≤ q ≤ 0.4 in Figs. 4 and5 with the increase of the variable period. Meyers et al.
(2005) described that we can find genetic potential in amuch wider variable period range when the mutation rate decreases because it takes more time to reach the state, genetic
robustness. This is consistent with the results in Figs. 4(a)4(f) in which we can find genetic potential in the ranges,
6 ≤ λ ≤ 20 for q = 0.025, 5 ≤ λ ≤ 10 for q = 0.05 and,3 ≤ λ ≤ 5 for q = 0.1. Meyers et al. did not mentioned
organismal flexibility for the high mutation rates. For the results obtained in this study, we can not find any organismal
flexibility when the mutation rate was high. This would beconsidered to be affected by the error threshold on the mutation rate (Kauffman, 1995); As the mutation rate increases,
the population gradually loses the current individuals. At
a certain critical mutation rate, the individuals become distributed randomly.
Meyers et al. (2005) also claimed that the mutation rate
per locus does not need to be variable if the phenotypicalmutation rate or the effective mutation rate per genotype isvariable as opposed to the argument that the variable mutation rate per locus is important for adaptation to environmental variations. This argument would be explained as follows.
When the mutation rate per locus is low, individuals mustchange their phenotypes (or obtain the higher fitness value)as soon as possible in order to adapt to environmental variation. Thus, the individuals which are located on the edgeof the neutral network are supported. When the mutation
rate per locus is high, individuals can change quickly theirphenotypes even though they are located at the center of theneutral network. Therefore, the dominance of the individuals which are located on the edge of the neutral network
becomes invisible at such a mutation rate.

Conclusions
This study investigated evolutionary dynamics of GAs in a
simple model by varying the rates of environmental variationand the mutation rate. The results can be summarized asfollows:• Two or three phase transitions were observed over thevariable period range. Especially when the mutation rate
is low, the results were consistent with the results obtainedin computational biology.
• For long variable periods, the frequency of the genotype
which was located at the center of the neutral networkwith the highest fitness value was largest in the population.
• For shorter variable periods, the frequency of the genotype which was located on the edge of the neutral network
was largest.

• For even shorter variable periods, the frequency of the
genotype with the intermediate fitness value was largest.

Kimura, M. (1983). The Neutral Theory of Molecular Evolution.
Cambridge University Press, New York.

In this study, four-bit binary strings were used to provide
simple explanatory examples. Additionally, a small population size and an alternating environment were set. Further
computer simulations will be conducted in order to investigate whether these observations are consistent with more
complex settings (Yang et al., 2007). Another future direction would be an analytical approach due to the simplicity ofthe model.

Knowles, J. D. and Watson, R. A. (2002). On the utility of redundant encodings in mutation-based evolutionary search. In
Merelo, J., Admidis, P., Beyer, H.-G., Fernandes-Villacanas,
J.-L., and Schwefel, H.-P., editors, Proceedings of Parallel Problem Solving from Nature - PPSN VII, Seventh International Conference, pages 88–98, Granada, Spain. LNCS
2439.

Acknowledgements
This work was supported by Grants-in-Aid for Scientific Research 22700241.

References

Meyers, L., Ancel, F., and Lachmann, M. (2005). Evolution ofgenetic potential. Computational Biology, 1(3):236–243.
Miller, J. (2009). Cartesian genetic programming. In Proceedingsof the 11th Annual Conference on Genetic and Evolutionary
Computation Conference, Tutorial, pages 3489–3512.
Newman, M. and Engelhardt, R. (1998). Effect of neutral selection on the evolution of molecular species. In Proc. R. Soc.
London B., pages 256:1333–1338.

Barnett, L. (1997). Tangled webs: Evolutionary dynamics on
fitness landscapes with neutrality. Master’s thesis, Schoolof Cognitive and Computing Sciences, Sussex University,
Brighton, UK.

Ohkura, K. and Ueda, K. (1999). Adaptation in dynamic environment by using GA with neutral mutations. International
Journal of Smart Engineering System Design, 2:17–31.

Branke, J. (2001). Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers.

Rothlauf, F. and Goldberg, D. E. (2003). Redundant representations in evolutionary computation. Evolutionary Computation, 11(4):381–415.

Ebner, M., Langguth, P., Albert, J., Shackleton, M., and Shipman,
R. (2001). On neutral networks and evolvability. In Proceedings of the 2001 IEEE Congress on Evolutionary Computation: CEC2001, pages 1–8, Piscataway, New Jersey. IEEE
Press.
Goldberg, D. (1989). Genetic Algorithms in Search, Optimizationand Machine Learning. Addison-Wesley.
Harvey, I. (1997). Artificial evolution for real problems. In Gomi,
T., editor, Evolutionary Robotics: From Intelligent Robots to
Artificial Life (ER’97). AAI Books, Tokyo.
Harvey, I. and Thompson, A. (1996). Through the labyrinth evolution finds a way: A silicon ridge. In Proceedings of thefirst International Conference on Evolvable Systems: From
Biology to Hardware, pages 406–422.
Katada, Y. and Ohkura, K. (2006). Estimating the degree of neutrality in fitness landscapes by the nei’s standard genetic distance – an application to evolutionary robotics –. In Proceedings of the 2006 IEEE Congress on Evolutionary Computation (CEC2006), pages 1590–1597.
Katada, Y. and Ohkura, K. (2009). Analysis on topologies of fitness landscapes with both neutrality and ruggedness basedon neutral networks. In Proceedings of the 2009 Genetic andEvolutionary Computation Conference (GECCO2009), pages
1855–1856.
Katada, Y., Ohkura, K., and Ueda, K. (2004). An approach to evolutionary robotics using the genetic algorithm with variable
mutation rate strategy. In Proceedings of The 8th Parallel
Problem Solving from Nature (PPSN VIII), pages 952–961.
Kauffman, S. A. (1995). At Home in the Universe: The Search forLaws of Self-organization and Complexity. Oxford University
Press.

Smith, T., Husbands, P., Layzell, P., and O’Shea, M. (2002). Fitness landscapes and evolvability. Evolutionary Computation,10(1):1–34.
Smith, T., Husbands, P., and O’Shea, M. (2001). Neutral networks in an evolutionary robotics search space. In Proceedings of the 2001 IEEE Congress on Evolutionary Computation: CEC2001, pages 136–145, Piscataway, New Jersey.
IEEE Press.
Thompson, A. (1996). An evolved circuit, intrinsic in silicon,
entwined with physics. In Proceedings of the first International Conference on Evolvable Systems:From Biology to
Hardware, pages 390–405.
van Nimwegen, E., Crutchfield, J. P., and Mitchell, M. (1999). Statistical dynamics of the royal road genetic algorithm. Theoretical Computer Science, 229(1):41–102.
Vanneschi, L. (2009). Fitness landscapes and problem fardness
in genetic programming. In Proceedings of the 11th Annual
Conference on Genetic and Evolutionary Computation Conference, Tutorial, pages 3657–3684.
Vassilev, V. K., Miller, J. F., and Fogarty, T. C. (2000). Information
characteristics and the structure of landscapes. Evolutionary
Computation, 8(1):31–60.
Yang, S., Ong, Y.-S., and Jin, Y., editors (2007). Evolutionary Computation in Dynamic and Uncertain Environments.
Springer.
Yu, T. (2007). Program evolvability under environmental variations
and neutrality. In Proc. ECAL 2007, pages 835–844. LNAI
4648.
Yu, T. and Miller, J. F. (2006). Through the interaction of neutral and adaptive mutations, evolutionary search finds a way.
Artificial Life, 12(4):525–551.