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.

Answer 3

if the chromosone does not represent a valid solution then it is completly unfit to solve the problem. So depending on how you order fitness. ie if a lower number represents more fitness (possibly a good idea when fitness represents total cost) then you'd assign it a max value and break any further fitness calculation on that chromosone when you get to a gene sequence that is invalid.

(or vice versa, assign it a fitness of zero if a higher fitness means a chromosone is more fit for the job)

however as others have pointed out it could be better to ensure that invalid chromosones dont occur. However if that is itself an overly compex process then allowing them and ensuring that broken chromosones are unlikely to make it into successive generations could be an acceptable approach.