J.Liu,H.A.Abbass,D.G.Green,and W.Zhong the number of basic motifs in the whole network.Since the number of nodes in the search space is 2",the number of all basic motifs is 2"()=2m-1n(n-1) (20) ◇ Proposition 2:Given a fitness landscape,FL ={S,f,N},where S is composed of binary strings with length n,f=NIAH,and the 1-bit flip operator is used to construct N.Then,the fraction of neutral motifs in the corresponding directed fitness landscape network is equal to or greater than 1-3 x 2-7. Proof.Given a distance motif Md,and the configurations corresponding to three nodes in Md are not the global optimum,then the fitness values of these three nodes are 0. Thus,Md belongs to Groupo,namely a neutral motif. That is to say,only motifs that include the node corresponding to the global opti- mum,labelled as n",can be a guide or deceptive motif.According to Lemma 1(2),the number of motifs that nbelongs to is 3n(.Thus,the number of neutral motifs is 2 no less than 3n(n-1 3 1-2n-1nn-d=1-2a (21) ▣ Proposition 3:Given a fitness landscape,FL ={S,f,N},where S is composed of binary strings with length n,f=TRAP,and the 1-bit flip operator is used to construct N;then,the fraction of deceptive motifs in the corresponding directed fitness landscape network is equal to or greater than 1-3 x 2-". Proof.Let a distance motif in the corresponding DFLN be Md {(m,n2,n3},Em,{di,d2,d3}},and the configurations corresponding to m,n2, n3 are not the global optimum,namely the string of all 0'.Let the configuration corresponding to ni,i=1,2,3,be (si,si2,...,sin),Then f)=∑s (22) In fact,this is equivalent to ONEMAX,and according to the proof for Proposition 1,we have that Md belongs to Groups,Group,or Groups. Case 1:Md belongs to Group3.According to(14),we obtained that the number of'1'in m is smaller than that of n2,and that of n2 is smaller than that of n3.Since the global optimum is the string of all '0',we have di<d2 d3;that is,Md is a core deceptive motif. Case 2:Md belongs to Group.According to(15),we obtained that the number of '1'in n2 is smaller than those of m and n3.Thus,we have d2 di and d2 d3;that is, Md is a deceptive motif. Case 3:Md belongs to Groups.According to(16),we obtained that both the num- ber of'1'in m and ns is larger than that of n2.Thus,we have d2>di and d2>d3;that is,Md is a deceptive motif. 10 Evolutionary Computation Volume x,Number xJ. Liu, H. A. Abbass, D. G. Green, and W. Zhong the number of basic motifs in the whole network. Since the number of nodes in the search space is 2 n, the number of all basic motifs is 2 n ( n 2 ) = 2n−1n(n − 1) (20) Proposition 2: Given a fitness landscape, FL = {S, f, N}, where S is composed of binary strings with length n, f=NIAH , and the 1-bit flip operator is used to construct N. Then, the fraction of neutral motifs in the corresponding directed fitness landscape network is equal to or greater than 1 − 3 × 2 −n. Proof. Given a distance motif Md , and the configurations corresponding to three nodes in Md are not the global optimum, then the fitness values of these three nodes are 0. Thus, Md belongs to Group0 , namely a neutral motif. That is to say, only motifs that include the node corresponding to the global opti￾mum, labelled as n ∗ , can be a guide or deceptive motif. According to Lemma 1(2), the number of motifs that n ∗ belongs to is 3n(n−1) 2 . Thus, the number of neutral motifs is no less than 1 − 3n(n−1) 2 2 n−1n(n − 1) = 1 − 3 2 n (21) Proposition 3: Given a fitness landscape, FL = {S, f, N}, where S is composed of binary strings with length n, f = TRAP, and the 1-bit flip operator is used to construct N; then, the fraction of deceptive motifs in the corresponding directed fitness landscape network is equal to or greater than 1 − 3 × 2 −n. Proof. Let a distance motif in the corresponding DFLN be Md = {{n1, n2, n3}, −→E Md , {d1, d2, d3}}, and the configurations corresponding to n1, n2, n3 are not the global optimum, namely the string of all ‘0’. Let the configuration corresponding to ni , i = 1, 2, 3, be (si1, si2, · · · , sin), Then f(ni) = Xn j=1 sij (22) In fact, this is equivalent to ONEMAX , and according to the proof for Proposition 1, we have that Md belongs to Group3 , Group4 , or Group5 . Case 1: Md belongs to Group3 . According to (14), we obtained that the number of ‘1’ in n1 is smaller than that of n2, and that of n2 is smaller than that of n3. Since the global optimum is the string of all ‘0’, we have d1 < d2 < d3; that is, Md is a core deceptive motif. Case 2: Md belongs to Group4 . According to (15), we obtained that the number of ‘1’ in n2 is smaller than those of n1 and n3. Thus, we have d2 < d1 and d2 < d3; that is, Md is a deceptive motif. Case 3: Md belongs to Group5 . According to (16), we obtained that both the num￾ber of ‘1’ in n1 and n3 is larger than that of n2. Thus, we have d2 > d1 and d2 > d3; that is, Md is a deceptive motif. 10 Evolutionary Computation Volume x, Number x