Antagonism in Genetic Algorithms for the Traveling Salesman Prob. among Opposite Paths Along the Same Route

Question

I'm pretty sure my question must have been investigated, but I'm missing the jargon that will help me search the literature. I'm writing a genetic algorithm that solves a type of Traveling Salesman Problem (TSP). Like the standard TSP, my variant has no notion of orientation. In a standard TSP, since there is a requirement to form a circuit back to the starting city, for any optimal solution there should be 2 equally optimal routes, which are just the 2 opposite routes around that circuit.

In a genetic algorithm, I would imagine that sometimes good solutions for the same (or similar) route emerge, yet encoded in opposite directions in different genotypes. I would also imagine that most cross-overs between these opposite routes would tend to antagonize one another, by that I mean their offspring would be unfit because they are attempting to optimize the same/similar route only from opposite directions. The two genotypes would be climbing the same hill, just from opposite sides. It would seem that this problem would slow down the search.

Are my assumptions above correct? Do you know what jargon used to describe this issue, or any tricks that help get around it? In an ideal world you'd like two fit, yet nearly opposite, genotypes to be encoded or cross-over in such that they preserve the overall route structure irrespective of the orientation.

Answer 1

For a GA and TSP, I assume you are using permutation encoding of your chromosomes.

Now, assuming a single distinct path is optimal---which is usual the case; i.e., no degeneracy among optimal solutions---the reverse cyclic permutation will also be optimal. The same is true for the same path with different starting cities; for n cities, the same distinct paths can be found in 2*n different kind of permutation encodings in your chromosomes (2 for reverse cyclic, n for first entry=starting city, in chromosome).

In practice, however, this is not an issue. The number of non-optimal paths is so large that the possible effect of "antagonism" between reverse cyclic good paths will be, in practice, non-existant.

A very important issue, however, that you might already be well aware of, is the way crossover is performed. With permutation encoding, simple crossover will result in non-feasible paths, so the encoding must be performed taking into account that the resulting child chromosomes still describe valid TSP permutations.

To wrap up; you should worry about antagonism w.r.t. cyclic reverse paths, as this is not an issue in practice. Instead, focus on studying difference crossover methods.

See e.g. Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator.

---

Final note: coming from a background in classic optimization, initially, I had a hard time accepting the "in practice..." statements regarding stochastic optimization methods such as genetic algorithms or ant colony opimization, and so on. But I've learned to accept that for these methods, "in practice..." statements are generally the best we aim for, as these methods are, by construction, not deterministic.