Traveling Salesman
Author
I''d like to attempt the traveling salesman problem using a genetic algorithm. I''m quite new at the subject (but very interested) and I''m not sure how to attack this problem. So the program starts up and randomizes the location of X cities. The cities will be stored into an array, so the Nth element cooresponds to a city. Piece of cake
Okay - so I was thinking making a chromosome structure simply a vector of the cities traveled to. the first element is the starting point then calculate the distance to each point finally resting back at the beginning. Now the problem with this comes with crossing over. Say you had a chromosome ABCDE (where abc.. are cities) and you cross it over with another chromosome DACBE - you might get something like DACDE. Notice D is duplicated. So how do you calculate the fitness of a chromosome that doesnt solve the problem correct? do you just forget it and assign it an extremely low fitness? And if so will the program ever solve the problem or at least come up with a decent approximation?
Thanks
I remember an old site, the Genetic Playground, which has one implmentation of the Traveling Salesman using Java.
I think the problem that your coming up against is the whole nature as to why the travelling salesman problem is computationally difficult. Problems occur such that the best solution to part of the network may not (and in many cases, is unlikely to) form part of the solution for the whole network. Hence assigning a fitness to it is perhaps a big question in this form of netwoork problem. It is in this diversability that the problem of sales men who travel arrise.
Not to burst your bubble but I don''t think that a genetic algorithm will be any more computationally effective than a heuristic approach.
(Having said that I don''t know for sure and it would be certainly be cool if you could get it working so don''t give up)
Not to burst your bubble but I don''t think that a genetic algorithm will be any more computationally effective than a heuristic approach.
(Having said that I don''t know for sure and it would be certainly be cool if you could get it working so don''t give up)
quote:Original post by Anonymous Poster
I think the problem that your coming up against is the whole nature as to why the travelling salesman problem is computationally difficult. Problems occur such that the best solution to part of the network may not (and in many cases, is unlikely to) form part of the solution for the whole network. Hence assigning a fitness to it is perhaps a big question in this form of netwoork problem. It is in this diversability that the problem of sales men who travel arrise.
You couldn''t be more off-base. The problem that he is ''coming up against'' is not why the TSP is hard. It is hard because every case _must_ be checked to _know_ a solution is the best.
quote:Original post by Anonymous Poster
Not to burst your bubble but I don''t think that a genetic algorithm will be any more computationally effective than a heuristic approach.
Not to burst _your_ bubble but a genetic algotithm could be a very good at finding near optimal (and sometimes even optimal) solutions to the TSP. In fact, this problem has really been done to death in optimization groups simply because it is such a good example of problems genetic algorithms and other optimization methods attempt to deal with.
quote:Original post by Anonymous Poster
(Having said that I don''t know for sure and it would be certainly be cool if you could get it working so don''t give up)
You don''t know at all.
In regards you the original question: I woudn''t worry to much about repeat entries in the chromosone. It isn''t unusual for a chromosne schema to have possible invalid forms. Just assign a really low fitness score (ie 0) and they will not be in the next generation. Or you could even just kill them off right away and keep breading (and mutating) till you get a decent offspring.
During mutation, however, you should select a mutation method that doesn''t create invalid offspring. This is simply because every ''city'' must be included and one mutation would create duplicates every time - not good.
Hope this helps.
- mongrelprogrammer
There are a few different types of crossover technique that have been devised to solve the kind of problem you are experiencing with the TSP. Some examples include, partially matched crossover (PMX), order crossover (OX), and cycle crossover (CX).
You should be able to find plenty of information about these techniques by doing a quick search, but if you do need any more help...just ask.
Hope this helps
You should be able to find plenty of information about these techniques by doing a quick search, but if you do need any more help...just ask.
Hope this helps
It isn''t unusual for a chromosne schema to have possible invalid forms
With regards to the TSP then it is unusual. You should use a crossover(and mutation) operator that only gives valid offspring (as Mr Nonsense suggests). In addition to those already suggested you can also search for...
Alternating-Position Crossover
Maximal-Preservation Crossover
Position-Based Crossover
Edge-Recombination Crossover
Subtour-Chunks Crossover
Intersection Crossover
Mutation operators are just as varied but are much simpler to implement and understand. See the posts made by Kent Paul Dolan on the comp.ai.genetic NG for further ideas.
ai-junkie.com
With regards to the TSP then it is unusual. You should use a crossover(and mutation) operator that only gives valid offspring (as Mr Nonsense suggests). In addition to those already suggested you can also search for...
Alternating-Position Crossover
Maximal-Preservation Crossover
Position-Based Crossover
Edge-Recombination Crossover
Subtour-Chunks Crossover
Intersection Crossover
Mutation operators are just as varied but are much simpler to implement and understand. See the posts made by Kent Paul Dolan on the comp.ai.genetic NG for further ideas.
ai-junkie.com
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
