Menu
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.
620
Genetic Algorithm which is a very good local search algorithm is employed to solve the TSP by generating a preset number of random tours and then improving the population until a stop condition is satisfied and the best chromosome which is a tour is returned as the solution.
Genetic algorithm is another approach to solve TSP because of its flexibility and robustness. Some distinctive applications of TSP comprise vehicle routing, computer wiring, cutting wallpaper and job sequencing etc. equal to number of nodes in the problem.
New hybrid cultural algorithm with local search (HCALS) is introduced to solve traveling salesman problem (TSP). The algorithm integrates the local search method into the cultural algorithm which uses social intelligence to guide and lead individuals in the population.
Genetic algorithms do not scale well with complexity. That is, where the number of elements which are exposed to mutation is large there is often an exponential increase in search space size. This makes it extremely difficult to use the technique on problems such as designing an engine, a house or a plane.
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.
50
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
