Evolutionary algorithms solve problems by simulating the evolution of a
population of candidate solutions. We focus on evolving permutations for
ordering problems like the traveling salesperson problem (TSP), as well as
assignment problems like the quadratic assignment problem (QAP) and largest
common subgraph (LCS). We propose cycle mutation, a new mutation operator whose
inspiration is the well known cycle crossover operator, and the concept of a
permutation cycle. We use fitness landscape analysis to explore the problem
characteristics for which cycle mutation works best. As a prerequisite, we
develop new permutation distance measures: cycle distance, $k$-cycle distance,
and cycle edit distance. The fitness landscape analysis predicts that cycle
mutation is better suited for assignment and mapping problems than it is for
ordering problems. We experimentally validate these findings showing cycle
mutation's strengths on problems like QAP and LCS, and its limitations on
problems like the TSP, while also showing that it is less prone to local optima
than commonly used alternatives. We integrate cycle mutation into the
open-source Chips-n-Salsa library, and the new distance metrics into the
open-source JavaPermutationTools library.

研究演化算法在排列问题和映射问题上的应用，提出了一种新的变异算子 “cycle mutation”，并且利用新的排列距离度量方法进行问题特征分析和应用实验，结果表明 cycle mutation 适用于映射和分配问题，对于旅行商问题有一定局限性，并且相对于常用替代方案对局部最优解的稳健性更好。