P.S. I tried to google it but did not find a step by step solution to the problem
Ulf Dittmer wrote:You can dissolve any salesman in some kind of genetically engineered liquid. Problem solved.
How about liquid oxygen? Liquid won't let him live and oxygen won't let him die*
*plagiarised from an old Hindi movie
1) Hire a large number of travelling salesmen (make them all the same gender to ease the complexity of assigning uniforms)
2) Give them the same set of towns to visit (while returning to the original town)
3) allow the salesmen with the shortest routes to reproduce. Sterilise or kill the rest
4) goto 2
I've worked on TSP using simulated annealing heuristics, but not genetic algorithms.
If I was going to do it, I'd do something like this:
1) represent each town link for possible inclusion in the result. each link has a genetic strength
2) start generating a large number of random TSP solutions.
3) for each random TSP solution, increase the genetic strength of links that appear in the best solutions, decrease the genetic strength of links that appear in the worst solution
4) start generating new TSP solutions from the currently available genes (I'm not 100% on this step). pick two random links eg A-B, C-D. if replacing with A-C B-D (provided it is still valid, otherwise use A-D B-C) provides a better TSP solution, decrease the A-B and C-D strength and increase A-C B-D
5) eventually you should be able to provide a SortedSet of genes and build reasonably good TSP solutions using the best matches that are able to produce valid TSP solutions eg A-B B-C C-A may be the best genes but they cannot be used in a single valid TSP solution if there is also a node 'D'
I am sorry to be the bearer of bad news, but your genetic algorithm is not correct. It will fail for all test cases involving mutations.
David O'Meara wrote:2) start generating a large number of random TSP solutions.
Not to get to meaningful here in MD, but many folks do not understand a key part of discussing NP problems: Its not that obtaining the solution is non-polynomial, but rather its checking that a given solution is correct is non-polynomial.
So @David's random number of TSP solutions is a fine, acceptable approach, the key part of whether or not an algorithm is NP is if you can check that one of the random solutions is correct. Of course, being able to check it in polynomial time means you can check it in less than O(N^P) for some power P, where N is the "large number" that David provides. The P can be pretty big, thousands or even millions.
S Venkatesh wrote:Travelling Sales people will have a lot of problems personal and professional.
They also have a bad reputation. See "The Music Man" and all the farmer's daughter jokes.