Final Project: Solving the TSP with Genetic Algorithms

In this project, your task is to implement a genetic algorithm that solves the traveling salesman problem (TSP).

Here’s a recording of a lecture that explains the assignment and discusses genetic algorithms.

The Travelling Salesman Problem (TSP)

The traveling salesman problem (TSP) is a well-known computational problem that asks you to find the shortest tour through a set of cities (i.e. points on a 2-dimensional plane).

The goal is to find a permutation of the cities \(c_1, \ldots, c_n\) that minimizes the sum of all distances between adjacent cities in the permutation, including the distance between the first and last city. More mathematically, you want a permutation of \(c_1, \ldots, c_n\) that minimizes this expression:

\[\textrm{dist}(c_1,c_n) + \sum_{i=1}^{n-1} \textrm{dist}(c_i, c_{i+1})\]

dist is the standard Euclidean distance function. If city \(c_i\) is at location \((x_i,y_i)\) and city \(c_j\) is at location \((x_j,y_j)\), then the distance between them is:

\[\textrm{dist}(c_i,c_j) = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}\]

Genetic Algorithms

Genetic algorithms (GAs) are a kind of randomized search algorithm inspired by biological evolution.

Please read section 4.1.4 of the Norvig and Russell textbook to get an idea of how they work. They include a worked example in Figure 4.6/4.7, and pseudocode in Figure 4.8. In the AIMA-Python code, search.py has some code for genetic algorithms (e.g. search for genetic_search), but the comments suggest it might not work correctly (!).

Also, the textbook version of genetic algorithms assumes that individuals in the population are represented as bit strings, but for the TSP individuals are usually represented as permutation of cities. Thus, the crossover and mutation operators they discuss don’t apply directly to the TSP: they will result in invalid permutations.

So please do some research and find variations of crossover and mutation that work with the TSP. For instance, partially-mapped crossover (PMX) is popular, and you can find resources on the web that it explain it and alternatives (e.g. this paper by Ucoluk). For mutation, swapping the position of two randomly chosen cities might work.

Note that many details are left unspecified! For instance, the population size and mutation are choice. You should do some experimentation to find reasonable values for these.

What to Submit

On Canvas, please submit a zip filed named project.zip that contains the following.

Code

An implementation of genetic algorithms in Python 3. Include all the code needed to run and test your algorithms.

You are welcome to modify the AIMA-Python code if you like, or to use other Python code from the web. If you do choose to use code from the web, then you must make sure you are allowed to use it and submit it to us (check the license, or ask the author), and you must also say exactly where you found the code (so that we could go look at the original code if we like).

You could also implement your own genetic algorithm framework. It’s not that hard once you understand the basics, and you could optimize it specifically for the TSP.

To keep the playing field level, you are restricted to using Python 3 for this project. Do not use any non-Python 3 code. Yes, this may cause performance problems, but, as described below, the main goal of this project is to try out variations of genetic algorithms. Python is a good language for this kind of experimentation.

Written Report

Submit a written report (in a PDF or Word file) with the following:

  • A title page with your name and student number, and also basic course info, i.e. CMPT 310 Surrey Spring 2020.

  • A section that describes of your genetic algorithm framework. Tell us where you got it from (or if you made it yourself), what modifications you made to it, etc. Include an example of how to call it on the TSP so that the marker can run it.

  • A section describing all the ideas and features you tried.

    We want to see that you have experimented with as many different selection, crossover, and mutation techniques as you can. Experimenting with features of genetic algorithms is the heart of this project.

    You can try techniques beyond selection, crossover, and mutation. With a little bit of research, you can find lots of ideas for variations of genetic algorithms. There are also lots of heuristics and idea specific to the TSP that you could try to fitting into a genetic algorithm.

    Try some of your own ideas as well: treat this as a research project.

    Make a list of all the ideas you tried! Even if they didn’t work out well, we want to know about it. The more the better. Make sure to say where you found the ideas — cite all your sources.

    We want to see some effort at originality, so include some of your own ideas. Explain how they work in enough detail so that someone else could implement it if they wanted to.

  • A section on your Challenge Problem results.

    Include your best solution to the Challenge Problem, and tell us:

    • How long did it take find this solution?
    • What techniques you used to find your solution, e.g. what selection, crossover, and mutation operators did you use? Did you make any other changes?

    Also, please submit your best solution (a permutation of the numbers from 1 to 1000) to the Challenge Problem in a text file named best-solution1000_<sfu_username>.txt, and replace <sfu_username> with your SFU computer username (i.e. skip the @sfu.ca). For example, if your SFU email is bgates@sfu.ca, you would name your file best-solution1000_bgates.txt

    Put all the numbers on one line, with one space between each number.

Challenge Problem

The file cities1000.txt contains the names and locations of 1000 cities. The cities are named 1, 2, …, 1000, and their locations were randomly generated.

Every line of cities1000.txt consists of 3 space-separated integers like this:

<city_name> <x-coordinate> <y-coordinate>

<city_name> is an integer from 1 to 1000, and <x-coordinate> and <y-coordinate> specifies the location of <city_name>.

The challenge is to find a permutation of 1, 2, …, 1000 that minimizes the TSP tour length defined above. Part of your mark for this project will depend upon the score for your best permutation.

Your are competing against everyone else in the class. Do not share permutations with others: that could give them a significant advantage over you! Keep your best permutations secret. It might be okay to share the score for a permutation, but even that could give clever competitors and advantage.