Detailed question when applying the genetic algorithm for a traveling salesman

Question

I read various things about this and understood the principle and concepts, however, none of the documents does not mention detailed information on how to calculate the suitability of a chromosome (which is a route) with the participation of neighboring cities (in the chromosome) that are not directly connected by an edge (on the chart).

For example, given chromosome 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, in which each gene represents the city index on the graph / map, how we calculate its suitability (i.e., the total sum of the distances traveled), if, say, there is no straight edge / connection between cities 2 and 8. We monitor what then a greedy algorithm for developing a route between 2 and 8 and add the distance from this route to the total?

This problem seems quite common when applying GA to TSP. Anyone who has done this before sharing their experiences. Thank you

Answer 1

If your graph does not have a link between 2 and 8, then any chromosome with 2 | 8 or 8 | 2 in it is unacceptable for the classic traveling salesman problem. If you find a different route between 2 and 8, you are likely to violate the “visit every place once” requirement.

, , + INF, . , .

, , .

Answer 2

, TSP. question.

Answer 3

, . , . .. (, , ), , , .

( , , , )

however, as others have pointed out, it would be better to make sure that invalid chromosones do not arise. However, if this is an overly complex process in itself that allows them to guarantee that broken chromosones are unlikely to turn into successive generations, then this may be an acceptable approach.