《计算机基础》课程教学资源（参考论文）Motif Difficulty（MD）：A Predictive Measure of Problem Difficulty for Evolutionary Algorithms using Network Motifs

Motif Difficulty (MD):A Predictive Measure of Problem Difficulty for Evolutionary Algorithms using Network Motifs Jing Liu jing.liu@adfa.edu.au School of Engineering and Information Technology,The University of New South Wales at the Australian Defence Force Academy,Canberra,ACT 2600,Australia Hussein A.Abbass h.abbass@adfa.edu.au School of Engineering and Information Technology,The University of New South Wales at the Australian Defence Force Academy,Canberra,ACT 2600,Australia David G.Green david.green@monash.edu Clayton School of Information Technology,Monash University,Clayton 3800, Australia Weicai Zhong w.zhong@adfa.edu.au School of Engineering and Information Technology,The University of New South Wales at the Australian Defence Force Academy,Canberra,ACT 2600,Australia Abstract One of the major challenges in the field of Evolutionary Algorithms(EAs)is to char- acterise which kinds of problems are easy and which are not.Researchers have been attracted to predict the behaviour of EAs in different domains.Based on fitness land- scape networks(FLNs)built by operators satisfying specific requirements,we define a new predictive measure,namely Motif Difficulty (MD),for comparison-based EAs. Since exhaustive computation on whole networks becomes quickly impractical,we propose a sampling technique for calculating the approximate MD.Extensive experi- ments on binary search spaces are conducted to show both advantages and limitations of MD.Multidimensional knapsack problems(MKPs)are also used to validate the performance of approximate MD on FLNs with different topologies.The effect of two representations,namely binary and permutation,on the difficulty of MKPs is analysed. Keytinryalort,roblem difficully,predictive measure,fies landscape, complex network,network motif. 1 Introduction Intrinsically,evolutionary algorithms (EAs)(Forgel,1999;Back et al.,1997;Goldberg, 1989)are still stochastic algorithms.Thus,one of the major challenges in this field is to characterise which kinds of problems are easy for a given algorithm to solve and which are not.In this direction,researchers have been attracted to predict the behaviour of EAs in different domains and have proposed predictive measures to quantify problem difficulty.The major tool used in available predictive measures is fitness landscapes (FLs).The concept of a FL was introduced in theoretical genetics (Wright,1932)as a way to visualise evolutionary dynamics.FLs were connected to EAs via a neigh- bourhood structure based on operators used in EAs,which highlights the association C200X by the Massachusetts Institute of Technology Evolutionary Computationx(x):xxx-xxx

Motif Difficulty (MD): A Predictive Measure of Problem Difficulty for Evolutionary Algorithms using Network Motifs Jing Liu jing.liu@adfa.edu.au School of Engineering and Information Technology, The University of New South Wales at the Australian Defence Force Academy, Canberra, ACT 2600, Australia Hussein A. Abbass h.abbass@adfa.edu.au School of Engineering and Information Technology, The University of New South Wales at the Australian Defence Force Academy, Canberra, ACT 2600, Australia David G. Green david.green@monash.edu Clayton School of Information Technology, Monash University, Clayton 3800, Australia Weicai Zhong w.zhong@adfa.edu.au School of Engineering and Information Technology, The University of New South Wales at the Australian Defence Force Academy, Canberra, ACT 2600, Australia Abstract One of the major challenges in the field of Evolutionary Algorithms (EAs) is to char￾acterise which kinds of problems are easy and which are not. Researchers have been attracted to predict the behaviour of EAs in different domains. Based on fitness land￾scape networks (FLNs) built by operators satisfying specific requirements, we define a new predictive measure, namely Motif Difficulty (MD), for comparison-based EAs. Since exhaustive computation on whole networks becomes quickly impractical, we propose a sampling technique for calculating the approximate MD. Extensive experi￾ments on binary search spaces are conducted to show both advantages and limitations of MD. Multidimensional knapsack problems (MKPs) are also used to validate the performance of approximate MD on FLNs with different topologies. The effect of two representations, namely binary and permutation, on the difficulty of MKPs is analysed. Keywords Evolutionary algorithm, problem difficulty, predictive measure, fitness landscape, complex network, network motif. 1 Introduction Intrinsically, evolutionary algorithms (EAs) (Forgel, 1999; Ba¨ck et al., 1997; Goldberg, 1989) are still stochastic algorithms. Thus, one of the major challenges in this field is to characterise which kinds of problems are easy for a given algorithm to solve and which are not. In this direction, researchers have been attracted to predict the behaviour of EAs in different domains and have proposed predictive measures to quantify problem difficulty. The major tool used in available predictive measures is fitness landscapes (FLs). The concept of a FL was introduced in theoretical genetics (Wright, 1932) as a way to visualise evolutionary dynamics. FLs were connected to EAs via a neigh￾bourhood structure based on operators used in EAs, which highlights the association °c 200X by the Massachusetts Institute of Technology Evolutionary Computation x(x): xxx-xxx

J.Liu,H.A.Abbass,D.G.Green,and W.Zhong between search spaces and fitness spaces.With the property of neighbourhood struc- ture in mind and at some level of granularity,each FL can form a network.In such a network,each node corresponds to a point in the search space,and each edge con- nects one node to one of its neighbours.The fitness value can be viewed as the weight of each node.Therefore,different problems correspond to different networks,and the process of EAs solving problems is equivalent to navigating through these networks. From this viewpoint,problem difficulty can be predicted by analysing the features of FL networks(FLNs).Although it is well-known that FLs are related to networks,no predictive measure has been proposed based on the features of FLNs. A number of global features of complex networks,such as the small-world prop- erty,the clustering property,and the scale free property have been studied thoroughly. In addition to these global features,"network motifs"(Milo et al.,2002)were proposed to uncover the structural design principles and resulted in a deeper understanding of complex networks.Motifs are connected sub-graphs occurring in complex networks at numbers that are significantly higher than those in random networks.It has been shown that network motifs exist widely in various complex networks,and different complex networks have different types of motifs.Thus,network motifs are in fact an intrinsic property of complex networks,and can be used to differentiate different net- works.For example,Ghoneim et al.(2008)used network motifs to discriminate two- player strategy games.For EAs,FLNs corresponding to various problems are expected to be different in some intrinsic properties.Therefore,we propose a predictive diffi- culty measure for EAs,namely Motif Difficulty (MD),by extracting motif properties from directed FLNs.We define MD by synthesising the effect of different classes of distance motifs on the searching process.Our experimental results show that MD can quantify the difficulty of different problems into the range of-1.0(easiest)to 1.0(most difficult),and performs especially well on some counterexamples for other measures. This paper is organised as follows.Section 2 discusses related work.Preliminaries on fitness landscapes and network motifs are given in Section 3.Section 4 presents the definition of motifs in FLNs,and Section 5 presents a qualification of problem difficulty based on the motifs defined in Section 4.Experiments on exact and approximate MD are given in Sections 6 and 7,respectively.Finally,Section 8 summarises the work in this paper,and discusses both advantages and disadvantages of MD. 2 Related Work In general,the study of factors affecting the performance of EAs can be divided into two classes(Borenstein and Poli,2005a).The first class focuses on the properties of a particular algorithm,while the second class focuses on the problem itself,and partic- ularly on FLs.In the first class,the BB hypothesis(Goldberg,1989),which is famous in the Genetic Algorithm(GA)community,states that a GA tries to combine low order and highly fit schemata.Following the BB hypothesis,the notion of deception has been defined (Goldberg,1989;Forrest and Mitchell,1993).Epistasis variance (Davidor,1991) and epistasis correlation(Naudts,1998)try to assess the GA-hardness of problems from the perspective of theoretical genetics. In the second class,methods focus on using statistical properties of FLs to char- acterise problem difficulty.The first study in this class proposed isolation(needle-in- a-haystack)(Forrest and Mitchell,1993)and multimodality (Davidor,1991).The other popular method is Fitness Distance Correlation (Jones and Forrest,1995),which mea- sures the hardness of a landscape according to the correlation between the distance from the optimum and the fitness value of the solution.However,none of the available 2 Evolutionary Computation Volume x,Number x

J. Liu, H. A. Abbass, D. G. Green, and W. Zhong between search spaces and fitness spaces. With the property of neighbourhood struc￾ture in mind and at some level of granularity, each FL can form a network. In such a network, each node corresponds to a point in the search space, and each edge con￾nects one node to one of its neighbours. The fitness value can be viewed as the weight of each node. Therefore, different problems correspond to different networks, and the process of EAs solving problems is equivalent to navigating through these networks. From this viewpoint, problem difficulty can be predicted by analysing the features of FL networks (FLNs). Although it is well-known that FLs are related to networks, no predictive measure has been proposed based on the features of FLNs. A number of global features of complex networks, such as the small-world prop￾erty, the clustering property, and the scale free property have been studied thoroughly. In addition to these global features, “network motifs” (Milo et al., 2002) were proposed to uncover the structural design principles and resulted in a deeper understanding of complex networks. Motifs are connected sub-graphs occurring in complex networks at numbers that are significantly higher than those in random networks. It has been shown that network motifs exist widely in various complex networks, and different complex networks have different types of motifs. Thus, network motifs are in fact an intrinsic property of complex networks, and can be used to differentiate different net￾works. For example, Ghoneim et al. (2008) used network motifs to discriminate two￾player strategy games. For EAs, FLNs corresponding to various problems are expected to be different in some intrinsic properties. Therefore, we propose a predictive diffi- culty measure for EAs, namely Motif Difficulty (MD), by extracting motif properties from directed FLNs. We define MD by synthesising the effect of different classes of distance motifs on the searching process. Our experimental results show that MD can quantify the difficulty of different problems into the range of −1.0 (easiest) to 1.0 (most difficult), and performs especially well on some counterexamples for other measures. This paper is organised as follows. Section 2 discusses related work. Preliminaries on fitness landscapes and network motifs are given in Section 3. Section 4 presents the definition of motifs in FLNs, and Section 5 presents a qualification of problem difficulty based on the motifs defined in Section 4. Experiments on exact and approximate MD are given in Sections 6 and 7, respectively. Finally, Section 8 summarises the work in this paper, and discusses both advantages and disadvantages of MD. 2 Related Work In general, the study of factors affecting the performance of EAs can be divided into two classes (Borenstein and Poli, 2005a). The first class focuses on the properties of a particular algorithm, while the second class focuses on the problem itself, and partic￾ularly on FLs. In the first class, the BB hypothesis (Goldberg, 1989), which is famous in the Genetic Algorithm (GA) community, states that a GA tries to combine low order and highly fit schemata. Following the BB hypothesis, the notion of deception has been defined (Goldberg, 1989; Forrest and Mitchell, 1993). Epistasis variance (Davidor, 1991) and epistasis correlation (Naudts, 1998) try to assess the GA-hardness of problems from the perspective of theoretical genetics. In the second class, methods focus on using statistical properties of FLs to char￾acterise problem difficulty. The first study in this class proposed isolation (needle-in￾a-haystack) (Forrest and Mitchell, 1993) and multimodality (Davidor, 1991). The other popular method is Fitness Distance Correlation (Jones and Forrest, 1995), which mea￾sures the hardness of a landscape according to the correlation between the distance from the optimum and the fitness value of the solution. However, none of the available 2 Evolutionary Computation Volume x, Number x

Motif Difficulty:A Problem Difficulty Measure measures fully achieved success.Isolation might be sufficient,but it is not a necessary condition for a landscape to be difficult to search.Multimodality is neither necessary nor sufficient for a landscape to be difficult to search(Kallel et al.,2001).FDC has achieved some success,but is still not able to predict the performance in some scenar- ios(Naudts and Kallel,2000;Jansen,2001). In addition to FLs,Borenstein and Poli(2005a)pointed out that a limitation of the original FL approach is that it does not provide a way to quantify the amount of infor- mation available in a landscape nor to asses its quality.Thus,they proposed Informa- tion Landscapes(ILs)based on tournament selection in GAs.Using ILs,they proposed a method to predict GA hardness and a theoretical model to study search algorithms (Borenstein and Poli,2005b,c).Based on the observation that FLs can actually form net- works,Ochoa et al.(2008)proposed a network characterisation of combinatorial FLs, and use the well-known family of NK landscapes as an example,and exhaustively ex- tract local optima networks on NK landscape instances.This work is the first attempt at using network analysis techniques in connection with the study of FLs and problem difficulty.However,they did not propose predictive measures. He et al.(2007)gave a rigorous definition of difficulty measures in black-box op- timisation,and proved that in general predictive difficulty measures that run in poly- nomial time do not exist unless certain complexity-theoretical assumptions are wrong. However,there are still some successful applications of using predictive difficulty mea- sures to guide the design of new algorithms.For example,Merz and Freisleben(2000) and Tavares et al.(2008)conducted a FL analysis for quadratic assignment problems and multidimensional knapsack problems(MKPs),respectively;Yang et al.(2006)pre- sented an attempt at characterising the search space difficulties in red teaming by using fitness landscapes. 3 Preliminaries 3.1 Fitness Landscapes Formally,a fitness landscape FL is defined by a tuple of three components: FL=(S,f,N) (1) where S is the search space.In this paper,we consider only a finite discrete search space for combinatorial optimisation problems.The fitness function f:S-R assigns a numeric value to each configuration in S,and we consider maximisation problems here.N is a neighbourhood structure defined over S as follows. s∈S,N(s)={y∈SlP(y∈operator(s)>O} (2) where P(e)denotes the occurrence probability of event e,and operator(s)denotes the set of configurations that can be obtained by performing operator on s,namely the set of neighbours of s.Since EAs are determined by various operators,the above neigh- bourhood structure defined over operators reflects the features of different EAs,and correspondingly,these features can be reflected in the resulted FLs. If we treat each configuration in the search space as a node,and link each node to all its neighbours,then each FL can be mapped into a network,namly a fitness land- scape network FLN,which is also defined by a tuple of three components: FLN =(V,E,f) (3) Evolutionary Computation Volume x,Number x 3

Motif Difficulty: A Problem Difficulty Measure measures fully achieved success. Isolation might be sufficient, but it is not a necessary condition for a landscape to be difficult to search. Multimodality is neither necessary nor sufficient for a landscape to be difficult to search (Kallel et al., 2001). FDC has achieved some success, but is still not able to predict the performance in some scenar￾ios (Naudts and Kallel, 2000; Jansen, 2001). In addition to FLs, Borenstein and Poli (2005a) pointed out that a limitation of the original FL approach is that it does not provide a way to quantify the amount of infor￾mation available in a landscape nor to asses its quality. Thus, they proposed Informa￾tion Landscapes (ILs) based on tournament selection in GAs. Using ILs, they proposed a method to predict GA hardness and a theoretical model to study search algorithms (Borenstein and Poli, 2005b,c). Based on the observation that FLs can actually form net￾works, Ochoa et al. (2008) proposed a network characterisation of combinatorial FLs, and use the well-known family of NK landscapes as an example, and exhaustively ex￾tract local optima networks on NK landscape instances. This work is the first attempt at using network analysis techniques in connection with the study of FLs and problem difficulty. However, they did not propose predictive measures. He et al. (2007) gave a rigorous definition of difficulty measures in black-box op￾timisation, and proved that in general predictive difficulty measures that run in poly￾nomial time do not exist unless certain complexity-theoretical assumptions are wrong. However, there are still some successful applications of using predictive difficulty mea￾sures to guide the design of new algorithms. For example, Merz and Freisleben (2000) and Tavares et al. (2008) conducted a FL analysis for quadratic assignment problems and multidimensional knapsack problems (MKPs), respectively; Yang et al. (2006) pre￾sented an attempt at characterising the search space difficulties in red teaming by using fitness landscapes. 3 Preliminaries 3.1 Fitness Landscapes Formally, a fitness landscape FL is defined by a tuple of three components: FL = (S, f, N) (1) where S is the search space. In this paper, we consider only a finite discrete search space for combinatorial optimisation problems. The fitness function f : S → R assigns a numeric value to each configuration in S, and we consider maximisation problems here. N is a neighbourhood structure defined over S as follows. ∀s ∈ S, N(s) = {y ∈ S|P(y ∈ operator(s)) > 0} (2) where P(e) denotes the occurrence probability of event e, and operator(s) denotes the set of configurations that can be obtained by performing operator on s, namely the set of neighbours of s. Since EAs are determined by various operators, the above neigh￾bourhood structure defined over operators reflects the features of different EAs, and correspondingly, these features can be reflected in the resulted FLs. If we treat each configuration in the search space as a node, and link each node to all its neighbours, then each FL can be mapped into a network, namly a fitness land￾scape network FLN, which is also defined by a tuple of three components: FLN = (V, E, f) (3) Evolutionary Computation Volume x, Number x 3

J.Liu,H.A.Abbass,D.G.Green,and W.Zhong >≥>2≥ >>>>≥房 Figure 1:All 13 types of three-node connected subgraphs(Milo et al 2002). where V is the finite set of nodes and each node corresponds to a configuration in S. f is the same as that in (1).E is a set of undirected edges and each edge connects one configuration to one of its neighbours;that is, E={x,y}lx,y∈SA(x∈N(y)Vy∈Nx)} (4) 3.2 Network Motifs Network motifs are patterns of inter-connections,which can be reflected by connected subgraphs(Milo et al.,2002).Milo et al.(2002)showed that there are 13 types of three- node connected subgraphs(Figure 1)for all directed networks.In a directed network, a pattern of inter-connections can be viewed as a network motif only when its number of occurrences in this network is significantly higher than that in the corresponding random network.More specifically,network motifs are those connected subgraphs for which the probability of appearing in a random network an equal or greater number of times than in the real network is lower than a cutoff value 0.01(Milo et al.,2002). To detect n-node network motifs in a network,the network was scanned for all of the possible n-node subgraphs,and the number of occurrences of each subgraph was recorded(Milo et al.,2002).Milo et al.(2002)showed that several networks(i.e., gene regulation,neurons,food webs,electronic circuits,and world wide web)exhibit different types of network motifs,and frequencies of different network motifs vary from one network to another.Motifs may thus define universal classes of networks, and are basic building blocks of most networks.Therefore,network motifs have been widely used in studying complex systems and in characterising features on the system level by analysing locally how the substructures are formed. 4 Motifs in Directed Fitness Landscape Networks In EAs,when an individual moves from one node to its neighbour under the effect of an operator,it is equivalent to exploring the local structures or subgraphs.Thus, subgraphs,which can be reflected by motifs,that an EA has visited during the whole evolutionary process have a close relationship with its performance.Since network motifs are just connected subgraphs,obviously,the number of possible motifs in undi- rected networks is much lower than that in directed networks.Moreover,the topology of FLNs built by the same operator is identical if the fitness value of each node is ig- nored.Thus,we first convert undirected FLNs to directed FLNs(DFLNs)by making use of fitness values so that more different types of network motifs can be extracted. Second,we propose another way to consider the 13 types of possible three-nodes mo- tifs presented in Figure 1,and define six types of basic motifs.Finally,based on these basic motifs,a new type of motifs,namely distance motifs,is designed by taking global optima as references. Evolutionary Computation Volume x,Number x

J. Liu, H. A. Abbass, D. G. Green, and W. Zhong Figure 1: All 13 types of three-node connected subgraphs (Milo et al., 2002). where V is the finite set of nodes and each node corresponds to a configuration in S. f is the same as that in (1). E is a set of undirected edges and each edge connects one configuration to one of its neighbours; that is, E = {{x, y}|x, y ∈ S ∧ (x ∈ N(y) ∨ y ∈ N(x))} (4) 3.2 Network Motifs Network motifs are patterns of inter-connections, which can be reflected by connected subgraphs (Milo et al., 2002). Milo et al. (2002) showed that there are 13 types of three￾node connected subgraphs (Figure 1) for all directed networks. In a directed network, a pattern of inter-connections can be viewed as a network motif only when its number of occurrences in this network is significantly higher than that in the corresponding random network. More specifically, network motifs are those connected subgraphs for which the probability of appearing in a random network an equal or greater number of times than in the real network is lower than a cutoff value 0.01 (Milo et al., 2002). To detect n-node network motifs in a network, the network was scanned for all of the possible n-node subgraphs, and the number of occurrences of each subgraph was recorded (Milo et al., 2002). Milo et al. (2002) showed that several networks (i.e., gene regulation, neurons, food webs, electronic circuits, and world wide web) exhibit different types of network motifs, and frequencies of different network motifs vary from one network to another. Motifs may thus define universal classes of networks, and are basic building blocks of most networks. Therefore, network motifs have been widely used in studying complex systems and in characterising features on the system level by analysing locally how the substructures are formed. 4 Motifs in Directed Fitness Landscape Networks In EAs, when an individual moves from one node to its neighbour under the effect of an operator, it is equivalent to exploring the local structures or subgraphs. Thus, subgraphs, which can be reflected by motifs, that an EA has visited during the whole evolutionary process have a close relationship with its performance. Since network motifs are just connected subgraphs, obviously, the number of possible motifs in undi￾rected networks is much lower than that in directed networks. Moreover, the topology of FLNs built by the same operator is identical if the fitness value of each node is ig￾nored. Thus, we first convert undirected FLNs to directed FLNs (DFLNs) by making use of fitness values so that more different types of network motifs can be extracted. Second, we propose another way to consider the 13 types of possible three-nodes mo￾tifs presented in Figure 1, and define six types of basic motifs. Finally, based on these basic motifs, a new type of motifs, namely distance motifs, is designed by taking global optima as references. 4 Evolutionary Computation Volume x, Number x

Motif Difficulty:A Problem Difficulty Measure 4.1 Directed Fitness Landscape Networks and Basic Motifs Definition 1:Define a fitness landscape network as FLN =(V,E,f),then the corre- sponding Directed Fitness Landscape Network is: 瓦N=(V,E) (5) where E={(x,y)lx,y}EAf(x)<f(y)}is a set of directed edges. Given two nodes x and y,y is the neighbour of x as long as the probability of converting x to y by operator is larger than 0,then the edge {x,y}exists in the corre- sponding network.In this way,a complete graph will be generated when using the mutation operator in which each bit will be flipped with probability 1/n for a binary string of length n(labelled as 1/n mutation in the following text),and the probabilities of transforming this string to different neighbours are not always the same.These incur some problems in detecting network motifs.First,if an operator leads to a complete graph,the topology of fitness landscapes for all problems is the same.Second,if the probabilities of transforming a string to different neighbours are not always the same, which is equivalent to the fact that edges have different weights,the edges in a motif may have different importance,and we cannot just count the number of each type of motifs.Therefore,in the following text,for the sake of simplicity,the operator used to build DFLNs must satisfy the conditions in (6)and (7).That is to say,the number of neighbours of each node must be much smaller than the number of nodes in the network,and the probabilities of converting one node to different neighbours must be identical.Edges in DFLNs use only the relative difference between the fitness val- ues of two nodes rather than the absolute fitness values.Thus,DFLNs are suitable for analysing comparison-based search algorithms,such as(1+1)EA(Droste et al.,2002). x∈V,N(xI《V (6) Vy,ZE N(x),P(operator(x)=y)=P(operator(x)=z) (7) The original network motifs are defined on the difference in frequency from ran- dom networks(Milo et al.,2002).However,random FLNs are built from a random fitness function.The difficulty of this random fitness function for EAs is also a part of study,so we cannot take it as a reference to detect network motifs in DFLNs.In fact,if we further check the 13 types of possible three-node motifs listed in Figure 1,we can find that motifs of types 1,2,3,4,7,and 8 are subsets of motifs of types of 5,6,9,10, 11,12,or 13.Therefore,in this study,for a three-node subgraph,we consider only the edges between two pairs of nodes,namely motifs of types 1,2,3,4,7,and 8 in Figure 1,which are named as Basic Motifs. Definition 2:Given a directed fitness landscape network FLN=(V,E),a Basic Motif,labelled as Mb,in FLN is a connected three-node subgraph, M={VMb={n1,2,3}CV,EMb={(h,2),(2,n1),(2,g),(n3,2)}nE}(⑧) To let Mo be a connected subgraph,EM should satisfy (1,2)∈EMV(2,m1)∈EMb)A(2,g)∈EMV(n3,2)∈EMb)(9) Evolutionary Computation Volume x,Number x

Motif Difficulty: A Problem Difficulty Measure 4.1 Directed Fitness Landscape Networks and Basic Motifs Definition 1: Define a fitness landscape network as FLN = (V, E, f), then the corre￾sponding Directed Fitness Landscape Network is: −−→FLN = (V, −→E ) (5) where −→E = {(x, y)|{x, y} ∈ E ∧ f(x) ≤ f(y)} is a set of directed edges. Given two nodes x and y, y is the neighbour of x as long as the probability of converting x to y by operator is larger than 0, then the edge {x, y} exists in the corre￾sponding network. In this way, a complete graph will be generated when using the mutation operator in which each bit will be flipped with probability 1/n for a binary string of length n (labelled as 1/n mutation in the following text), and the probabilities of transforming this string to different neighbours are not always the same. These incur some problems in detecting network motifs. First, if an operator leads to a complete graph, the topology of fitness landscapes for all problems is the same. Second, if the probabilities of transforming a string to different neighbours are not always the same, which is equivalent to the fact that edges have different weights, the edges in a motif may have different importance, and we cannot just count the number of each type of motifs. Therefore, in the following text, for the sake of simplicity, the operator used to build DFLNs must satisfy the conditions in (6) and (7). That is to say, the number of neighbours of each node must be much smaller than the number of nodes in the network, and the probabilities of converting one node to different neighbours must be identical. Edges in DFLNs use only the relative difference between the fitness val￾ues of two nodes rather than the absolute fitness values. Thus, DFLNs are suitable for analysing comparison-based search algorithms, such as (1+1)EA (Droste et al., 2002). ∀x ∈ V, |N(x)| ¿ |V| (6) ∀y, z ∈ N(x), P(operator(x) = y) = P(operator(x) = z) (7) The original network motifs are defined on the difference in frequency from ran￾dom networks (Milo et al., 2002). However, random FLNs are built from a random fitness function. The difficulty of this random fitness function for EAs is also a part of study, so we cannot take it as a reference to detect network motifs in DFLNs. In fact, if we further check the 13 types of possible three-node motifs listed in Figure 1, we can find that motifs of types 1, 2, 3, 4, 7, and 8 are subsets of motifs of types of 5, 6, 9, 10, 11, 12, or 13. Therefore, in this study, for a three-node subgraph, we consider only the edges between two pairs of nodes, namely motifs of types 1, 2, 3, 4, 7, and 8 in Figure 1, which are named as Basic Motifs. Definition 2: Given a directed fitness landscape network −−→FLN = (V, −→E ), a Basic Motif, labelled as Mb , in −−→FLN is a connected three-node subgraph, Mb = {VMb = {n1, n2, n3} ⊂ V, −→E Mb = {(n1, n2), (n2, n1), (n2, n3), (n3, n2)} ∩ −→E } (8) To let Mb be a connected subgraph, −→E Mb should satisfy ((n1, n2) ∈ −→E Mb ∨ (n2, n1) ∈ −→E Mb ) ∧ ((n2, n3) ∈ −→E Mb ∨ (n3, n2) ∈ −→E Mb ) (9) Evolutionary Computation Volume x, Number x 5