Mutation operator for genetic algorithms for solving traveling salesman problem

Question

I need help help for defining mutation operator for traveling salesman problem.

I'm currently using this now (pseudocode):

mutate ( strand ):
    for n in random_interval ( min_gene_index, max_gene_index ):
        i := random_interval ( min_gene_index, max_gene_index );
        j := random_interval ( min_gene_index, max_gene_index );
        swap ( strand[i], strand[j] );

So when swapping is executed two cities in the route is swapped. The goal is that it needs to be fast and effective. I don't want it to be a performance hit in the main loop. Can I improve my implementation or is there any other alternative that is better?

Answer 1

Many different mutation (and crossover) operators have been devised for the TSP and each give different results.

You could use domain specific information (heuristic mutation).

E.g. the 2-opt mutation is an often used algorithm.

It usually improves solutions compared to a crossover-only approach (in (2) the 2-opt mutation operator was tested even without crossover with good results).

      ..                   ..
     /  \                 /  \
    /    \               /    \
  (a)    (c)           (a)    (c)
     \  /               |      |
      \/         =>     |      |
      /\                |      |
     /  \               |      |
  (d)    (b)           (d)    (b)
    \    /               \    /
     \  /                 \  /
      ..                   ..

The operator randomly select two edges e.g. (a,b) and (c,d) from the tour and check if:

distance(a, b) + distance (c, d) > distance(a, d) + distance(c, b)

if this is the case the tour is changed by removing (a,b) and (c,d) and replacing them with the edges (a,d) and (c,b).

This is quite lightweight and simple to implement.

References

1. Parallel Genetic Algorithms Applied to the Traveling Salesman Problem
2. Schema analysis of the traveling salesman problem using genetic algorithms

Answer 2

Unless you're doing some really nonstandard version of the TSP, I don't think you need a loop here. With a GA using a binary encoding of real-valued parameters, occasionally you might need a loop like

for each gene:
    for each bit in the gene:
        do something

It's fairly rare even then, but occasionally you do want to observe parameter boundaries like that.

For TSP though, the canonical representation is just a permutation of integers representing the cities in the order they occur in the tour. If you want to make one swap (the smallest valid mutation), then you just do

def mutate(candidate):
    p1 = random_index()
    p2 = random_index()
    swap(candidate[p1], candidate[p2])

You can try doing the swap trick with bitwise operators, but I don't imagine it would make a noticeable difference. Otherwise, this is about as efficient as you can get.