Fitness Landscape Analysis Using Network Motifs
A new predictive difficulty measure for evolutionary algorithms (EAs) using network motifs, namely Motif Difficulty (MD), is proposed in this research. A new kind of motifs, namely Distance Motifs, is designed and is divided into three classes based on the contribution to the search process of EAs. These classes of motifs are named as Guide Motifs, Deceptive Motifs, and Neutral Motifs. Finally, MD is designed by synthesizing the effect of these 3 classes of motifs. Additionally, since exhaustive computation on the whole networks gets quickly impractical, a sampling technique especially for computing approximate MD is proposed. We [Liu, Zhong, Green & Abbass] analyse the effect of two representations, namely binary and permutation, on the difficulty of multidimensional knapsack problems. The results also confirm previous measures; that is, permutation representation with a first-fit heuristic is better than binary representation.