Traveling Salesman Problem

10 points.

In this project we apply genetic algorithms to the notorious Traveling Salesman Problem (TSP).

TSP has been studied ad nauseam outside the context of GAs, and many better solutions to TSP exist. In this project, we pretend that the world has just discovered the TSP, and knowing little about it, we apply the GA, which is a good technique for finding solutions to problems that are not well understood.

  1. First, you'll need to decide how to encode the TSP into a genome. Think about it, and if you need help, see me.

  2. Next step is to write the fitness function. This should be relatively easy - find the total distance the salesman needs to travel. Your fitness function may also need to "punish" invalid solutions, especially if individuals in the population don't meet the solution criteria (i.e. they don't go to every city.)

  3. "Tweak" parameters to try to get better solutions. Increasing the population size may give better results, but take longer to compute. Increasing the mutation rate may help too, up to a point.

Extra Credit - Devise a new crossover function that improves the results of the GA. (8 points.)

Best Credit - Awarded to the student who finds the best route for the given TSP problem. (The route must be found using GAs. Other techniques are not allowed!) (10 points.)

Files for the project are available here.