## 3 Methods
### New Measures of Permutation Distance
#### 3.2.1 Cycle Distance  
As a first step toward a distance measure appropriate for use in analyzing fitness landscapes associated with the \(\text{Cycle}(\alpha)\) form of cycle mutation, we present cycle distance. \(\text{Cycle}(\alpha)\) mutates a permutation by inducing a cycle whose length is only limited by the permutation length itself. Therefore, cycle distance is the count of the number of non-singleton cycles. We can define the cycle distance between permutations \(p_{1}\) and \(p_{2}\) as  
\[\delta(p_{1},p_{2})=\text{CycleCount}(p_{1},p_{2})-\text{FixedPointCount}(p_{ 1},p_{2}), \tag{21}\]  
where CycleCount is the number of permutation cycles, and FixedPointCount is the number of singleton cycles or fixed points, which is a cycle of length one (i.e., a point where both permutations contain the same element). We compute cycle distance in \(O(n)\) time.  
Cycle distance is a semi-metric, since it satisfies all of the metric properties except for the triangle inequality. First, it obviously satisfies non-negativity since \(\delta(p_{1},p_{2})\) clearly cannot be negative since there cannot be a negative number of non-singleton permutation cycles. Second, it is obvious that \(\delta(p_{1},p_{2})=\delta(p_{2},p_{1})\), and is thus symmetric. Third, it satisfies the identity of indiscernibles as follows. When \(p_{1}=p_{2}=p\), we have  
\[\delta(p,p)=\text{CycleCount}(p,p)-\text{FixedPointCount}(p,p)=n-n=0, \tag{22}\]  
since the cycle count is \(n\) (i.e., \(n\) singleton cycles), and thus the number of fixed points is also \(n\). In the other direction, we have  
\[\delta(p_{1},p_{2})=0\implies\text{CycleCount}(p_{1},p_{2})=\text{FixedPoint Count}(p_{1},p_{2})\implies p_{1}=p_{2}, \tag{23}\]  
since the only way that every cycle is a fixed point is if \(p_{1}\) and \(p_{2}\) are identical.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Mutation Operator** & **Worst Case** & **Average Case** \\ \hline \(\text{Cycle}(kmax)\) & \(O(\min(n,kmax^{2}))\) & \(O(\min(n,kmax^{2}))\) \\ \(\text{Cycle}(\alpha)\) & \(O(n)\) & \(O(\min(n,\frac{(2-\alpha)}{k-\alpha})^{2})\) \\ Swap & \(O(1)\) & \(O(1)\) \\ Insertion & \(O(n)\) & \(O(n)\) \\ Reversal & \(O(n)\) & \(O(n)\) \\ Scramble & \(O(n)\) & \(O(n)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Asymptotic runtime of cycle mutation and common permutation mutation operators.  
To demonstrate the violation of the triangle inequality, consider the permutations:  
\[\begin{split} p_{1}&=[0,1,2,3,4,5,6,7,8,9]\\ p_{2}&=[1,0,3,2,5,4,7,6,9,8]\\ p_{3}&=[0,3,2,5,4,7,6,9,8,1].\end{split} \tag{24}\]  
Observe \(\delta(p_{1},p_{2})=5\) since every consecutive pair of elements in \(p_{1}\) is swapped in \(p_{2}\), creating five cycles of length two. All even-numbered elements are fixed points for \(p_{1}\) and \(p_{3}\), and all odd-numbered elements form a single cycle. That is, keep the even elements fixed and cycle the odd elements to the left within \(p_{1}\) to obtain \(p_{3}\). Thus, \(\delta(p_{1},p_{3})=1\). Finally, inspect \(p_{3}\) and \(p_{2}\) to note that if we cycle all of the elements of \(p_{3}\) one position to the right, we obtain \(p_{2}\). Therefore, \(\delta(p_{3},p_{2})=1\). Thus, since \(\delta(p_{1},p_{2})>\delta(p_{1},p_{3})+\delta(p_{3},p_{2})\), cycle distance does not satisfy the triangle inequality, and is only a semi-metric.  
The diameter of the space of permutations \(S_{n}\) of length \(n\) given a measure of distance \(\delta\) is the maximal distance between points in that space. Define the diameter \(D(n,\delta)\) as  
\[D(n,\delta)=\max_{p_{1},p_{2}\leq S_{n}}\{\delta(p_{1},p_{2})\}. \tag{25}\]  
Since each non-singleton cycle contributes one to cycle distance, independent of cycle length, the maximum case is when the number of non-singleton cycles is maximized. The smallest non-singleton cycle is length two. The maximum cycle distance therefore occurs when there are \([n/2]\) cycles of length two, leading to a diameter of  
\[D(n,\delta)=\Big{[}\frac{n}{2}\Big{]}. \tag{26}\]