## 3 Methods
### Fitness Landscape Analysis
#### 3.3.2 Fitness Distance Correlation  
We now compute FDC for small instances of the TSP, LCS, and QAP. To compute FDC for a problem instance, you need all optimal solutions to that instance. This necessitates utilizing an instance small enough to feasibly and reliably determine all optimal solutions. The FDC calculations in this section use a permutation length \(n=10\) for this reason, which means a 10-city TSP, an LCS with graphs of 10 vertexes, and a QAP with 10 by 10 cost and distance matrices. The EA experiments later in the paper use larger problem instances to experimentally compare the performance of the different mutation operators. We use a TSP instance with 10 cities arranged equidistantly around a circle of radius 10, and Euclidean distance for the edge costs. In this way, the optimal solutions are known a priori. There are 20 optimal permutations, all representing the same TSP tour following the cities around the circle, including ten possible starting cities and two travel directions. We generate a QAP instance such that a random permutation \(p\) of length 10 is the known optimal solution. Let \(A=[(1,90),(2,89),\ldots,(90,1)]\). Shuffle this array of ordered pairs. The 90 non-diagonal elements of the 10 by 10 cost matrix \(C\) are populated row by row using the first element of the tuples in \(A\). Let \((u,v)\) be one of these tuples. If \(C[i][j]\) is set to \(u\), then \(D[p(i)][p(j)]\) in the distance matrix \(D\) is set to \(v\). We generate an LCS instance consisting of a pair of isomorphic graphs. In this way, we know that the LCS is either of those graphs or any of the other automorphisms of the graph. We use a strongly regular graph in the analysis. Strongly regular graphs are especially challenging for algorithms for the LCS and other related problems. Specifically, we use the Petersen graph [74], shown in Figure 1, which has 120 automorphisms, and thus 120 optimal vertex mappings. Such instances are hard because many vertexes of a strongly regular graph look the same locally to a solver, which can be simultaneously attracted toward different distinct solutions in a space plagued by complex local optima. Although guidance on interpreting FDC varies, an \(r\leq-0.15\) is commonly considered an easier fitness landscape since it implies that fitness increases as distance to an optimal solution decreases, while \(r\geq 0.15\) is likely a deceptive landscape since fitness increases as you move away from optimal solutions, and \(-0.15<r<0.15\) is considered difficult since there is very little correlation between fitness and distance to an optimal solution [28]. For each combination of problem and mutation operator, we compute FDC exactly, calculating Pearson correlation over all \(n!=3,628,800\) permutations of length \(n=10\). Table 3 summarizes the results. Without loss of generality, for TSP and QAP we compute FDC from the cost function (to minimize) rather than a fitness function (to maximize), flipping the sign of the FDC with positive FDC, implying more straightforward problem solving. Since LCS is a maximization problem, the sign of the FDC is interpreted normally. Figure 1: The Petersen graph, a strongly regular graph. For the TSP, there is very strong FDC for reversal mutation, and lesser but still strong FDC for insertion mutation. The FDC analysis predicts that these will perform better than the others. Swap has the next-highest FDC. Although not as high, all cases of \(\text{Cycle}(kmax)\) exhibit \(r>0.15\). Given the correlation strength of reversal and insertion landscapes, we expect them to dominate the others, but swap and \(\text{Cycle}(kmax)\) may also perform well. The strength of the correlations are not nearly as high for the QAP, and only three of the mutation operators have an \(r\geq 0.15\), including swap mutation and \(\text{Cycle}(kmax)\) with a \(kmax\) of either 3 or 4. This may be a problem where cycle mutation is better suited.