2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your second paragraph is hard to follow, and it seems to force the reader to read the linked article to understand. Can you shortly explain how the representation works, and why you can't do something "usual" for mutation, e.g. a partial shuffle? (That is, take a candidate tour, pick some part of it, and shuffle it). $\endgroup$ – Juho May 5 '15 at 5:39
  • $\begingroup$ @Juho I assumed adjacency representation is common knowledge, sorry if I was wrong. Its definition is simple: j value in i-th index means that node j goes right after node i. It doesn't say where the path starts (unlike path representation), but as a matter of fact, it's not necessary. I arbitrarily decided it to be one, for the sake of conversions. That implies that not every sequence of non-repeating integers is a valid solution, e.g. aforementioned 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
  • $\begingroup$ @Juho No, my concern isn't having a fixed starting city. I want an operation transforming one permutation in adjacency representation into another one. The simplest idea is to begin with adjacency/path conversion, mutate the result and convert it back. I am considering this solution, however I'm hoping for something trickier. Something as easy as path-representation mutators (or slightly more complicated), yet guaranteeing correct solutions. $\endgroup$ – Szymon May 5 '15 at 9:48
  • $\begingroup$ It might not even be worth it to consider this in the first place. The adjacency representation might enable "interesting operations", but who knows how effective they are. From an engineering approach, there might not be a better solution to just implement everything, and test them on the data you care about. $\endgroup$ – Juho May 5 '15 at 10:07
0
$\begingroup$

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$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.