A detail question when applying genetic algorithm to traveling salesman

Question

I read various stuff on this and understand the principle and concepts involved, however, none of paper mentions the details of how to calculate the fitness of a chromosome (which represents a route) involving adjacent cities (in the chromosome) that are not directly connected by an edge (in the graph).

For example, given a chromosome 1|3|2|8|4|5|6|7, in which each gene represents the index of a city on the graph/map, how do we calculate its fitness (i.e. the total sum of distances traveled) if, say, there is no direct edge/link between city 2 and 8. Do we follow some sort of greedy algorithm to work out a route between 2 and 8, and add the distance of this route to the total?

This problem seems pretty common when applying GA to TSP. Anyone who's done it before please share your experience. Thanks.

Answer 1

If there is no link between 2 and 8 on your graph, then any chromosome with 2|8 or 8|2 in it is invalid for the classical travelling salesman problem. If you find some other route between 2 and 8, you are probably going to violate the "visit each location once" requirement.

One really dodgy-but-pragmatic solution is to include edges between those nodes with incredibly high distances, or even +INF if your language supports it. That way, your standard minimizing fitness function will naturally prune them.

I think the original formulation of the problem includes edges between all nodes, so this is a non-issue.

Answer 2

This is the exact kind of problem, specialized Crossover and mutation methods have been applied for GA based solutions to TSP problems. See this question.