## 4 Results
### LCS Results  
Consider two sets of experiments with the LCS problem, one with random graphs and the other with strongly regular graphs. In the random graph case, we have 50 instances, each consisting of a pair of randomly generated isomorphic graphs. We use pairs of isomorphic graphs so that each problem instance has a known optimal solution. That is, the largest common subgraph is simply the graph itself. Each graph has 50 vertexes and edge density 0.5, which means that the probability of each possible edge is 0.5. Thus, each graph has 50 vertexes, and the expected number of edges is \(0.5\times 50\times 49/2=612.5\). The second graph for each instance is formed by relabeling the vertexes randomly. We use generalized Petersen graph \(G(25,2)\) for the strongly regular case. Generalized Petersen graph [76]\(G(n,k)\) has \(2n\) vertexes \(V=\{u_{0},u_{1},\ldots,u_{n-1},v_{0},v_{1},\ldots,v_{n-1}\}\), and \(3n\) edges \(E=\{(u_{i},v_{i})\mid 0\leq i<n\}\bigcup\{(u_{i},u_{i+1\mod n})\mid 0\leq i<n\} \bigcup\{(v_{i},v_{i+k\mod n})\mid 0\leq i<n\}\). The original Petersen graph (Figure 1) is \(G(5,2)\). Figure 4 shows a generalized Petersen graph \(G(25,2)\) that has 50 vertexes and 75 edges. We again average over 50 runs, but in this case, each instance consists of graph \(G(25,2)\) and a second graph isomorphic to it that is formed by randomly relabeling the vertexes. LCS is a maximization problem; however, for consistency we transform it to a minimization problem. Since each instance is a pair of isomorphic graphs, the LCS has \(|E|\) edges, where \(E\) is the edge set. Thus, redefine LCS to minimize the cost of permutation \(p\): \(C(p)=|E|-|E^{\prime}|\), where \(E^{\prime}\) is the edge set of the subgraph implied by vertex mapping \(p\). The results are in Figure 5 (random graphs) and Figure 6 (strongly regular graphs). For SA and random graphs (Figure 5b), scramble, insertion, and reversal all perform very poorly compared with the others. Cycle\((5)\) and Cycle\((0.75)\) are inferior to the other cycle mutation cases for the longest runs at statistically significant levels. Within an EA for random graphs (Figure 5a), the behavior is similar to that of the QAP. Swap exhibits a premature convergence effect, while cycle mutation finds increasingly lower cost solutions. Cycle\((3)\) also prematurely converges at \(10^{6}\) evaluations, while cycle mutation configured with a larger neighborhood continues to improve solution cost beyond that point. Cycle\((0.25)\) is best at statistically significant levels for the \(10^{7}\) evaluation runs. Figure 3: Results on the QAP for (**a**) \((1+1)\)-EA, and (**b**) SA. These results are consistent with the fitness landscape analysis. First, FDC suggested that swap, Cycle(3), and Cycle(5) were best suited to the problem, followed by Cycle(4) and insertion. The FDC analysis was likely misled with respect to insertion mutation due to the small size of the instance used in the FDC analysis, which is likely why we find insertion performing poorly on the larger instance. This is consistent with the search landscape calculus analysis which suggests that swap and cycle mutation are both well suited to the problem, and that the other operators, including insertion, are not. The Cycle(0.25) is most effective within longer runs of the EA due to the combination of small average change (average cycle length of 2.33) and very large neighborhood size. Within SA, cycle mutation is neither better nor worse than swap, converging at the same rate. Observe that the strongly regular graph results (Figure 6) are similar to those of random graphs, but are more pronounced. For example, in an EA (Figure 6a), swap and Cycle(3) prematurely converge, while Cycle(4) and Cycle(5) exhibit superior convergence effect,  
Figure 4: The generalized Petersen graph, \(G(25,2)\), a strongly regular graph. Figure 5: Results on the LCS problem with random graphs for (**a**) \((1+1)\)-EA, and (**b**) SA.