Overview

The Traveling Salesman Problem is a classic problem in optimization: find the least-cost round trip route amongst N cities, visiting each city exactly once. For example, in the below figure, starting at city 1, what is the shortest route that will visit all cities and bring us back to city 1?

This series of assignments involves (1) solving the TSP using various machine learning techniques such as genetic algorithms, simulated annealing, SOM etc (2a) using classic prediction algorithms (knn etc) to predict the DOW and (2b) use optimization methods from the first part (e.g., GAs) to optimize the prediction of the DOW

The objectives of the series of assignments are multifold:
  • To use the TSP as a test bed for various ML approaches (e.g., genetic algorithms, simulated annealing, Kohonen Self Organizing Maps etc).
  • To briefly study various real world applications of the TSP (e.g., logistics; genome sequencing; manufacturing: IC testing, PCB drilling; aiming telescopes; and x-ray crystallography)
  • To tie in problems from machine learning to general Computer Science (e.g., revisiting the concepts of NP completeness).
  • To provide a historical perspective of a problem with a rich history, significant practical applications, and and numerous technological approaches.)
  • To use the algorithm(s) developed for solving the TSP to solve a different optimization problem (predicting the DOW).

Conceptually the requirements of this assignment are simple. The assignment as given in my class required familiarity with Python programming. Additionally students need to be familiar with basic prediction methods (kNN, neural nets etc) and basic optimization techniques (genetic algorithms etc).

A variation of using a genetic algorithm to solve the TSP has been used in my introductory (Java based) programming class. The learning objectives of that assignment are different from the present. In that version of the assignment students are given a significant amount of code to read and extend:
File name Given Code

 My Solution

LOC SLOC LOC SLOC
City.java 27 12 38 27
GenerateCities.java 57 34 57 34
Map.java 59 39 44 29
SplitInterval.java 62 36 62 36
TSP.java 126 77 126 77
Tour.java 180 120 204 155
Util.java 29 12 33 20
UtilTest.java 0 0 37 26
Total 540 330 639 426

LOC: Lines of code (source + comments + blank lines)
SLOC: Source Lines of Code

More details of the introductory version of this assignment is available from the Nifty Assignments Page

Acknowledgment: Parts 2a and 2b are modeled after a similar assignment used by Professor Zbigniew Michalewicz.

This exercise can be given in a couple of different variations (1) in a short form as described in the SIGCSE nifty assignment or (2) in a longer form as described in the above pdf file TSP.pdf. You will need the free Adobe Acrobat Reader to view this file.
The course syllabus is available here.