This week's book giveaway is in the Cloud/Virtualization forum.
We're giving away four copies of Learning OpenStack Networking: Build a solid foundation in virtual networking technologies for OpenStack-based clouds and have James Denton on-line!
See this thread for details.
Win a copy of Learning OpenStack Networking: Build a solid foundation in virtual networking technologies for OpenStack-based clouds this week in the Cloud/Virtualization forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Solving Travelling Salesman Problem using Genetic Algorithm  RSS feed

 
Ranch Hand
Posts: 104
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can somebody tell me how to solve Travelling Salesman Problem using Genetic Algorithm?I want a step by step approach.
P.S. I tried to google it but did not find a step by step solution to the problem
 
Bartender
Posts: 11445
18
Android Eclipse IDE Google Web Toolkit Java Mac Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fire him. Problem solved
 
Rancher
Posts: 42975
76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can dissolve any salesman in some kind of genetically engineered liquid. Problem solved.
 
Java Cowboy
Sheriff
Posts: 16084
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In case you're wondering why you get funny responses: you posted this in the Meaningless Drivel forum, which is the forum where we come to relax and have fun after all the hard work.
 
Maneesh Godbole
Bartender
Posts: 11445
18
Android Eclipse IDE Google Web Toolkit Java Mac Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Sheriff
Posts: 23706
50
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Travelling salesmen are always a problem. Who knows what mischief they are getting into in all those places they visit? It's much better to bring them in-house and hand them a telephone.
 
Ranch Hand
Posts: 162
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Since Al Gore invented the internet in the 1990's, traveling salesmen are obsolete. They have been replaced by those annoying pop-up ads.
 
Rancher
Posts: 436
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I recommend Carbonite. Would have been nice five days ago.
 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is clear the posters above do not understand genetic algorithms.
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 think.
 
Maneesh Godbole
Bartender
Posts: 11445
18
Android Eclipse IDE Google Web Toolkit Java Mac Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@David,
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
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It also fails in the case of Zombie invasion, but I think that you are right that there are several boundary or corner cases that need to be identified.
 
Rancher
Posts: 4686
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Puttin g Zombie invasion to the side for a moment, Genetic Algorithms and other heuristics are way to provide a reasonable solution to an NP problem without any guarantee that this solution is anywhere near the best solution. The 'larger number of random solutions' was meant as a simple way to seed the initial genetic fitness so that they can be used and refined later.
 
Ranch Hand
Posts: 464
Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Travelling Sales people will have a lot of problems personal and professional. Why are you attempting to solve it?
 
Pat Farrell
Rancher
Posts: 4686
7
Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!