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.
5 1 4 3 2
gives a loop before visiting all the nodes. This is the reason "usual" mutation don't work, and I'm looking for something special. $\endgroup$ – Szymon May 5 '15 at 6:56