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 3Motif 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