1

The current algorithm used, is a genetic algorithm using, mutation and ordered crossover. We modified the original ordered crossover algorithm by removing the depot (end points) and then performing the crossover and adding them in after. The parent selection algorithm uses roulette selection with the

goodness = 1/time_to_travel_route.

Without the Crossover, the algorithm produces good results (using only mutations), but adding it in significantly worsens them. Here is a link to a post with a similar problem: Why does adding Crossover to my Genetic Algorithm gives me worse results?

Following the advice given in the post, the goodness was changed to

goodness = 1/(time_to_travel_route)^n with varying n

However, this still did not produce a favorable result.

Population Size: tried from 100 to 10,000 Stop Condition: tried from 10 generations to 1000 Fitness Algorithm: tried 1/(time_to_travel_route)^n with varying n from 1 to Big Numbers

Mutation Algorithm: The algorithm uses 2-opt. All offspring are mutated. The mutation algorithm tries different mutations until it finds a better solution. However, if it finds a worse solution, it might just return the worse population with probability p. This is done to add some randomness and escape local minimas. We varied p from 5 to 20 percent.

Community
  • 1
  • 1
algoBaller
  • 39
  • 3
  • 9
  • Why do you expect genetic algorithms will give you good results? – Douglas Zare Mar 27 '15 at 20:16
  • @DouglasZare I found multiple papers that suggest the use of genetic algorithms. Genetic algorithms tend to be the usual go to heuristic for TSP problems from what I found online. – algoBaller Mar 27 '15 at 20:19
  • Are you sure your crossover is actually happening correctly, and you're not corrupting your chromosome due to some bug? Have you tried various ways of doing the crossover (i.e. half from each parent, multiple parents, etc)? – Steve Mar 27 '15 at 20:22
  • @Steve we haven't tried different types of crossover algorithms because after doing research we found that ordered crossover algorithm is one of the best. We have tested the current output and are certain that it currently doing what its supposed to. – algoBaller Mar 27 '15 at 20:28
  • @algoBaller: I'm surprised to hear that. I would expect genetic algorithms to perform really badly. Do people who work on TSP problems think genetic algorithms work, or do people who work on genetic algorithms think the TSP is a good place to use genetic algorithms? Those are very different. – Douglas Zare Mar 27 '15 at 20:33
  • @DouglasZare From what I read in papers, genetic algorithms work really well for TSP problems because TSP problems are easily represented as strings (each item in the string is a location to visit). I also found a ton of online papers suggesting the use of genetic algorithms: https://scholar.google.ca/scholar?q=travelling+salesman+problem+genetic+algorithm&hl=en&as_sdt=0&as_vis=1&oi=scholart&sa=X&ei=j78VVZ3-BYmbNoXJg6AL&sqi=2&ved=0CBoQgQMwAA – algoBaller Mar 27 '15 at 20:39
  • @DouglasZare What would you suggest instead? – algoBaller Mar 27 '15 at 20:40
  • When I search for both together, I mainly get papers from people who work in genetic algorithms, not papers from people with good results on TSP problems. It appears that genetic algorithms are exciting to people and people keep trying them even when they don't produce results. If good results are important to you, though, look for what people actually do on large TSP problems, such as using good local heuristics or integer linear programming. See the Concorde TSP solver. On the other hand, if you actually get genetic algorithms to work well it will be exciting to many people. – Douglas Zare Mar 27 '15 at 20:52

0 Answers0