A detail question when applying genetic algorithm to traveling salesman

Posted by burrough on Stack Overflow See other posts from Stack Overflow or by burrough
Published on 2010-03-30T00:37:28Z Indexed on 2010/03/30 0:43 UTC
Read the original article Hit count: 612

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.

© Stack Overflow or respective owner

Related posts about genetic-algorithms

Related posts about traveling-salesman