posted 7 years ago

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.

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.

posted 7 years ago

- 1

@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.

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.

posted 7 years ago

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 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.

posted 7 years ago

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.

It is sorta covered in the JavaRanch Style Guide. |