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 xJ. 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