## 1 Introduction
The central aim of this paper is development of a mutation operator for permutations that (a) is characterized by small random perturbations on average, (b) has a large neighborhood size, and (c) is tunable. These properties enable focused search with improved handling of local optima. No such mutation operators currently exist for permutations. For bit-vectors, the standard bit-flip mutation satisfies all of these properties. For example, the bit-flip mutation rate \(M\) is usually set to a low value for a small average number of bits flipped, but can be tuned for problems where greater mutation is beneficial, and as long as \(M\) is non-zero, the neighborhood includes all other bit-vectors. Similarly, Gaussian mutation in an ES satisfies all of these properties, with a tunable parameter, the standard deviation of the Gaussian. All existing permutation mutation operators have a fixed neighborhood size, which in most cases is small, that depends only on permutation length. To achieve this aim, we present a new mutation operator called cycle mutation, which relies on the concept of a permutation cycle and is inspired by CX. Rather than operating on two parents as CX does, cycle mutation instead mutates a single member of the population. Thus, it is also applicable to non-population metaheuristics such as simulated annealing (SA) [25; 26; 27]. We develop two variations of cycle mutation, \(\text{Cycle}(kmax)\) and \(\text{Cycle}(\alpha)\), offering two ways of addressing locally optimal solutions. To formally demonstrate that cycle mutation achieves the target properties of large neighborhood but small average changes, we conduct a fitness landscape analysis of cycle mutation, and other permutation mutation operators for three NP-hard optimization problems [14], the TSP, the LCS, and the quadratic assignment problem (QAP). The fitness landscape analysis predicts that cycle mutation likely performs well for assignment and mapping problems, such as LCS and QAP, where absolute positions directly affect fitness, but that it may be less well-suited to relative ordering problems such as the TSP. We use fitness distance correlation (FDC) [28], which requires a measure of distance between solutions that corresponds to the operator under analysis. Appropriate measures of distance exist for the operators to which we compare. However, no existing permutation distance functions are suitable for the new cycle mutation. Therefore, we introduce three new permutation distance measures: cycle distance, \(k\)-cycle distance, and cycle edit distance. To validate the new cycle mutation, we experiment with the LCS, QAP, and TSP, comparing cycle mutation with commonly used permutation mutation operators within a \((1+1)\)-EA as well as within SA. The results support the predictions of the fitness landscape analysis, demonstrating the efficacy of cycle mutation for assignment problems such as LCS and QAP, while also showing that cycle mutation is inferior to alternatives for the TSP where relative element positions are more important than absolute locations. The experiments also show that the Cycle(\(\alpha\)) variation is especially effective at escaping local optima. A secondary aim of this research is to enable reproducibility [29], as well as to advance the state of practice. Therefore, we integrate our Java implementation of cycle mutation into the open source Chips-n-Salsa library [30], and cycle distance, \(k\)-cycle distance, and cycle edit distance into the open source JavaPermutationTools library [31]. Chips-n-Salsa is a library for stochastic and adaptive local search as well as EAs. JavaPermutationTools is a library for computation on permutations and sequences, with a focus on measures of distance.