Analysis on Topologies of Fitness Landscapes with BothNeutrality and Ruggedness Based on Neutral Networks
Yoshiaki Katada

Kazuhiro Ohkura

Setsunan University
Faculty of Engineering
Neyagawa, Osaka 572-8508, JAPANHiroshima University
Graduate School of Engineering
Higashi-Hiroshima, Hiroshima 739-8527, JAPAN

katada@ele.setsunan.ac.jp

kohkura@hiroshima-u.ac.jp

ABSTRACT
Fitness landscapes which include neutrality have been conceptualized as containing neutral networks. Since the introduction of this concept, EC researchers have expected thata population can move along neutral networks without getting trapped on local optima. On the other hand, it has
been demonstrated in tunably neutral NK landscapes thatneutrality does not aﬀect the ruggedness, although it does
reduce the number of local optima. These show that theeﬀects of neutrality are still contentious issues. This paper investigates the eﬀects of neutrality and ruggedness on
topologies of ﬁtness landscapes. A neutral network of a ﬁtness landscape is described in a mathematical form based on
Harvey’s original deﬁnition with minor modiﬁcations. Ourresults demonstrate that landscapes with a higher degreeof neutrality have the larger sizes of neutral networks. Forlandscapes with the lowest degree of ruggedness, all networks lead to the networks of the highest ﬁtness via anynetworks. For landscapes with a higher degree of ruggedness, there are few contact points between the networks ofhigh ﬁtness and the ones of the highest ﬁtness, which seemto be isolated, deceptive or rugged.
Categories and Subject Descriptors: I.2.8 [ARTIFICIAL INTELLIGENCE]: Problem Solving, Control Methods, and Search–Heuristic methods
General Terms: Theory
Keywords: ﬁtness landscape, ruggedness, neutrality, analysis

1.

INTRODUCTION

Selective neutrality is caused by highly redundant mappings from genotype to phenotype or from phenotype to ﬁtness. Fitness landscapes which include neutrality have been
conceptualized as containing neutral networks [2]. Harvey [2]ﬁrst introduced the concept of neutral networks into the GA
community. His deﬁnition is as follows: “A neutral networkof a ﬁtness landscape is deﬁned as a set of connected pointsof 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 ﬁtness.” This concept iscentral to the majority of research in this ﬁeld.
Copyright is held by the author/owner(s).
GECCO’09, July 8–12, 2009, Montréal Québec, Canada.
ACM 978-1-60558-325-9/09/07.

EC researchers have expected that a population on a ﬁtness landscape with neutrality can move along neutral networks without getting trapped on local optima even though
the landscape also includes ruggedness. One question ariseson this: does neutrality diminish local optima? It has been
demonstrated in a tunably neutral NK landscape[1, 3] that
increasing neutrality does not aﬀect the ruggedness, although
it does reduce the number of local optima [1, 3, 4]. Thismeans that the eﬀects of both ruggedness and neutrality
on landscapes are still contentious issues and these must be
taken into account when genetic operators are designed.
This paper investigates the eﬀects of neutrality and ruggedness on topologies of ﬁtness landscapes in test problems.
The paper is organized as follows. The next section describes
a neutral network of a ﬁtness landscape in a mathematical form based on Harvey’s original deﬁnition with minor
modiﬁcations. Section 3 analyzes topologies in and between
neutral networks for a tunably neutral NK landscape anddiscusses the relationship between topologies of ﬁtness landscapes and GA diﬃculties. Conclusions are given in the lastsection.

2. A FORMAL DEFINITION OF A NEUTRALNETWORKThe expression, “single (neutral) mutations”, in Harvey’s
original deﬁnition of a neutral network mentioned in the previous section is ambiguous. Because the amount of a single
mutation is not deﬁned, the genetic distance between a parent and the (neutral) mutant has various values dependingon the mutation operator applied to the parent. Therefore,a neutral network is not uniquely determined by the original
deﬁnition.
Thus, we consider the minimum genetic distance between
them. When we use binary representations, the minimum
genetic distance is described by min H(xg , y g ), where H(·, ·)is the Hamming distance between a parent and the oﬀspring,xg and y g ∈ Φg , Φg is the set of genotypes. We assume one
point mutation applied to parents then min H(xg , y g ) = 1.
We describe a neutral network caused by redundant mappings from genotype to phenotype in a mathematical form
based on the above consideration.
At ﬁrst, two individuals, xg and z g , are connected, xg ∼gg
gz g , if there exists {xgi }n= xgn ,i=0 ⊂ Φg , s.t. x = x0 , zggggfg (xi ) = fg (x ), H(xi , xi+1 ) = 1, where fg is the mappingfrom genotype to phenotype and assumed to be surjective
and not injective. Thus, a neutral network of a genotype z gis Φg (z g ) = {xg ∈ Φg |xg ∼ z g }.

We extend this deﬁnition to redundant mappings fromphenotype to ﬁtness. Two individuals, xg and z g , are conggnected, xg ∼ z g , if there exists {xgi }ni=0 ⊂ Φg , s.t. x = x0 ,z g = xgn , (fp ◦fg )(xgi ) = (fp ◦fg )(xg ), H(xgi , xgi+1 ) = 1, where
fp is the mapping from phenotype to ﬁtness and assumed tobe surjective and not injective. Addition to this assumption,
there are 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 a genotype z g is describedin the both cases as follows: Φ∗g (z g ) = {xg ∈ Φg |xg ∼ z g }.

3.

THE ANALYSIS OF TOPOLOGIES IN A
TUNABLY NEUTRAL NK LANDSCAPE

3.1 Terraced NK LandscapeA terraced NK landscape (TNK) is the tunably neutral
NK landscape proposed by Newman and Engelhardt [3]. A
terraced NK landscape has three parameters: N , the lengthof the genotype; K, the number of epistatic linkages betweengenes; and F , a constant integer for tuning neutrality. The
neutrality of the landscape can be tuned by changing thevalue of F . The neutrality of the landscape is maximized
when F = 2, and is eﬀectively non-existent as F → ∞. The
ruggedness of the landscape increases with the increase of K
and is maximized when K = N −1. In this function, a ﬁtness
value is assigned to a genotype directly so no phenotype isdeﬁned. Thus, it is also assumed that fg is bijective, and fp
is investigated.

3.2 Simulation Conditions
Computer simulations were conducted by exhaustive enumeration of Φg . This enumeration and their clustering into
neutral networks are so time consuming that we conductedsimulations with the small genotype space. We conducted
10 independent runs for each problem under the landscapeparameters, N = 10, K = {0, 9} and F = {2, 8}. Here,|Φg | = 210 = 1024.

3.3 Simulation Results
Table 1-2 show the sizes of the neutral networks and thenumber of them for diﬀerent values of K and F . For K = 0,
all genotypes belong to an arbitrary neutral network. The
sizes of all networks are equal to 16 for F = 2 and 2 for
F = 8. This result suggests that for K = 0 the sizes of theneutral networks become larger with the decrease of F , thatis, with a higher degree of neutrality. For K = 9, the sizesof the neutral networks are not constant, some of which arelarger for F = 2 than for F = 8. That is, there are a small
number of large networks for F = 2 and a large number ofsmall ones for F = 8. Many genotypes do not belong to any
neutral networks and stand alone (20% for F = 2 and 66%
for F = 8).
The total number of neutral networks is so large that thewhole networks do not appear in this manuscript due tospace restrictions. Thus, topologies among these neutral
networks are only described. For K = 0, all networks havesome portals to the networks of higher ﬁtness. This meansthat individuals always reach the networks of the highest
ﬁtness whichever networks they pass through if we assume
that they move along neutral networks by one point mutation and then reach a portal to a neutral network of higher

Table 1: The sizes of the neutral networks and thenumber of them in the TNK for K = 0
size
16

F =2
number64size
2F =8
number512

Table 2: The sizes of the neutral networks and thenumber of them in the TNK for K = 9size
12
3
4
56
789F =2
number size
210
1139
1410151116622272
1212
2226
1-

number11111111-

size
12345611-

F =8number680
921915421-ﬁtness. For K = 9, the number of portals between networks
is very small. For F = 8, there is no portal among the networks of the highest several ﬁtness values. Moreover, there
are long distances between the networks where there is nocontact point. These can be considered that the networks
are isolated or “deceptive”. It would be diﬃcult for individuals to reach the networks of the highest ﬁtness.

4. CONCLUSIONS
Our results can be summarized as follows: (1) The sizesof the neutral networks become larger for landscapes witha higher degree of neutrality. (2) All networks have someportals to the networks of higher ﬁtness. Thus, individuals reach the networks of the highest ﬁtness through themfor landscapes with the lowest degree of ruggedness. (3)Most of networks of the high ﬁtness do not have many portals to networks of the highest ﬁtness for landscapes witha higher degree of ruggedness. This would be consideredthat the networks are isolated. Future work will investigate
whether these results are observed in real-world problems
which are expected to have landscapes with both neutrality
and ruggedness and to be with the small genotype space

5. REFERENCES[1] L. Barnett. Tangled webs: Evolutionary dynamics on ﬁtness
landscapes with neutrality. Master’s thesis, School of Cognitive
and Computing Sciences, Sussex University, Brighton, UK, 1997.
[2] I. Harvey and A. Thompson. Through the labyrinth evolutionﬁnds a way: A silicon ridge. In Proceedings of the first
International Conference on Evolvable Systems: From Biology
to Hardware, pages 406–422, 1996.
[3] M. Newman and R. Engelhardt. Eﬀect of neutral selection on
the evolution of molecular species. In Proc. R. Soc. London B.,
pages 256:1333–1338, 1998.
[4] T. Smith, P. Husbands, P. Layzell, and M. O’Shea. Fitness
landscapes and evolvability. Evolutionary Computation,10(1):1–34, 2002.