## 1 Introduction  
In an evolutionary algorithm (EA), a problem is solved through the simulated evolution of a population that evolves over many generations. There are many types of EA that mostly differ in the types of problems they solve and in how solutions are represented. For example, a genetic algorithm (GA) [1], the original EA, usually represents a candidate solution to an optimization problem with a vector of bits. Evolution strategies (ESs) [2] focus specifically on real-valued function optimization, utilizing a vector of floating-point values to represent each candidate solution. Genetic programming [3] is an approach to automatic inductive programming, and evolves a population of programs, each of which is typically represented with a tree structure. This paper focuses on EAs that encode solutions with permutations, often referred to as a permutation-based GA [4; 5; 6; 7], while others prefer the more general term EA [8; 9] to avoid confusion with a binary-encoded GA. Solutions to some problems are more naturally represented with a permutation than with another representation. The classic example is the traveling salesperson problem (TSP), where a solution is a tour of the cities, and thus can be represented in a straightforward way as a permutation of indexes into a list of cities. One challenge with designing a permutation EA is deciding which genetic operators to use. This is less of an issue with the classic bit-vector GA or a real-valued ES because it is possible to mutate bits independently of the rest of a bit-vector in a GA, and real-valued alleles in an ES can likewise be mutated independently from the vector as a whole, such as with Gaussian mutation [10] or Cauchy mutation [11]. Within a permutation-based EA, mutation cannot change individual elements independent of the rest of the permutation. For example, in the permutation \([2,4,0,3,1]\) of the first five integers, we cannot mutate one value in isolation or it leads to an invalid permutation. Crossover cannot naively exchange parts of parents. For example, if one parent is as above, and the other is \([4,2,1,0,3]\), exchanging the second and third elements between the parents leads to two invalid permutations, \([2,2,1,3,1]\) and \([4,4,0,0,3]\). Thus, for permutations, mutation and crossover must consider the overall structure to ensure a valid encoding. As a consequence, many mutation and crossover operators exist for permutations. The suitability of each depends upon the characteristics of the permutation that most significantly impacts solution fitness for the problem at hand, such as absolute element positions, relative element positions, or element precedences [12; 13]. Only relative positions matter to fitness of a TSP solution. For example, if cities \(i\) and \(j\) are adjacent in the permutation, then the solution includes the edge \((i,j)\) regardless of where the pair of cities appears. The absolute element positions are most important for other problems, such as the largest common subgraph (LCS). The LCS is an NP-hard [14] optimization problem involving finding a one-to-one mapping between the vertex sets of a pair of graphs to maximize the number of edges of the common subgraph implied by the mapping. As a permutation problem, one holds the vertexes of one graph in a fixed order, and a permutation of the vertexes of the other graph represents a mapping. The absolute index of a vertex in the permutation therefore corresponds to the vertex it is mapped to in the other graph. Mutation for permutations is most often one of swap mutation, insertion mutation, reversal mutation, or scramble mutation [15]. There are many permutation crossover operators that focus on maintaining different characteristics of the parents, including order crossover [16], non-wrapping order crossover [17], uniform order-based crossover [18], partially matched crossover [19], uniform partially matched crossover [20], precedence preservative crossover [21], edge assembly crossover [22; 23], and cycle crossover (CX) [24].