Traveler - Closest Neighbor and Genetic DEATHMATCH

Question

Over the past few days, I have noted several web sites that have demonstrated TS solution using genetic algorithms.

I am looking for your opinion which is better for this particular problem.

Heuristics versus genetic.

For the better, I mean that you get a shorter / lower cost path.

Explain why you feel, how you feel.

Examples and links to other sites are welcome.

Answer 1

Since none of the methods guarantees the optimal solution, your mileage will vary. With little luck, any technique can come out of another. Both methods have pros and cons.

Nearest neighbor: + fast, + simple, - usually not optimal

Genetic algorithm: - slower, - more complex, + trend of solutions to optimal over time

The big difference is that randomized algorithms such as simulated annealing and genetic algorithms can improve over time - the longer you run them, the greater the chance of an optimal solution (although there are no guarantees).

Since NN is fast, nothing prevents you from combining methods. Launch NN to find a better solution than a random, starting solution. Then feed this solution into your genetic algorithm and let it work as you see fit.

If you are interested in optimal solutions, check out Lin-Kernighan heuristics and Linear programming . Both were used to find optimal solutions for large tours, including this solution for 85,900 city tours and 24,978 tours in Sweden in Sweden .

Georgia Tech TSP is an excellent resource.