TSP genetic algorithm: what mutation function for adjacency representation?

Question

When implementing TSP GA I decided for adjacency representation (i.e. $j$ value in $i$-th index means that node $j$ goes right after node $i$), as it enables interesting heuristical crossover operation (see Greffenstette, 1985). However this source, like many others, is silent about a sensible option of mutating solutions written in this way.

Traditional approaches (taken from path representation) usually result in incorrect solutions. For example, let's take permutation 5 4 1 3 2 (path rep. 1 5 2 4 3) and try swapping second and third position, namely giving 5 1 4 3 2. Path representation would start with 1 5 2 1 and oops, we're stuck. Another methods are similaringly disappointing.

So, is there an elegant and fast (emphasis on the latter) idea to mutate? Of course, I can switch between representations, but it might strongly impact performance (a switch is linear complexity, though I believe there's a chance of finding something with $O(1)$) and it's a worst-case scenario.

Answer 1

The core of your problem is this: you want a simple mutation operator that sends any $n$-cycle to another $n$-cycle.

Recall that every permutation on $n$ symbols can be decomposed into cycles. To count as a TSP tour, you need the permutation to be a single cycle, i.e., it to be a $n$-cycle. So given a TSP tour (a permutation that is a $n$-cycle), you want your mutation operator to give you another TSP tour (another $n$-cycle).

Here are multiple approaches you could take:

1. Don't represent the tour in your adjacency representation. Instead, represent it as a $n$-cycle: represent it as a list of the vertices visited, in the order they are visited. Then, you can swap any two elements in the list and get another tour (another $n$-cycle). For instance, you'd represent your example path as the list [1,5,2,4,3]. Swapping the second and third position gives you [1,2,5,4,3], which is another valid path.

2. Represent the path in adjacency representation. Do the same operation as above, but now apply it directly to the adjacency representation: emulate its effect on the adjacency representation. So, given 5 4 1 3 2, you decide you're going to swap the order that 5 and 2appear in. This can be done by replacing the5with a2, and replacing the2with the second element (4), and replacing the second element with2`.

3. Pick a suffix of the path, then splice that into the middle of the path. For instance, suppose you can decompose the path into $A \to \dots \to F \to G \to \dots \to P \to Q \to \dots Z \to A$. Then you could change this to $A \to \dots \to F \to Q \to \dots \to Z \to G \to \dots P \to A$ by splicing the $Q \to \dots \to Z$ part right after $F$. You can take any suffix and splice it in, at an earlier position, like this. This can be done via a not-too-complex transformation on the adjacency representation, by changing only three elements in the adjacency representation (in this example, you change the successor for $F,Z,P$).