This assignment gives you the chance to use evolutionary computation to solve a problem of your choice. You may work on the traveling salesperson problem, try to solve one of the contests associated with the upcoming conference on the Congress of Evolutionary Computation, or pick some other problem that interests you. I encourage you to work with a partner on this project. You have two weeks to complete it.
You will turn in a 4-6 page paper describing your project. Your paper should include the following:
Your grade will not be based on whether your experiment succeeds or fails. Negative results are as important as positive results. Your grade will be based solely on the thoroughness and readability of your paper.
Once again, I encourage you to try using latex. Check out the sample paper in: /home/meeden/public/latex-example/
The traveling salesperson problem can be described as follows. Given a list of N cities and their locations, find a roundtrip of minimal total length that visits each city exactly once. You can assume that the distance between city i and city j is the same as the distance between city j and city i. In other words the problem is symmetric.
Here is a nice interactive demo of a GA solving a TSP created by Sushil Louis.
TSP is interesting because it is part of a class of problems defined to be NP-complete. No polynomial-time algorithm has yet been discovered for any NP-complete problem, and many computer scientists believe that no such algorithms exist. Evolutionary computation can be a useful tool for finding nearly optimal solutions to very hard problems of this kind.
TSP is a frequently studied problem, so many data sets are available online. One such repository is the site on National Traveling Salesman Problems which includes data for a number of countries. The smallest set is from Djibouti with 89 cities and the largest set is from China with 71,009 cities. I would suggest starting with a small set first, and if you have success with that, then try larger sets.
The most common representation of the TSP for a GA uses an integer encoding of a complete tour of the possible cities. For example, if there are 5 cites numbered 1-5, then one possible tour would be the list: [4, 1, 2, 3, 5] which represents the path from 4 to 1, 1 to 2, 2 to 3, 3 to 5, and 5 back to 4. The fitness for this tour would be the sum of the euclidean distances between each pair of cities.
A wide variety of domain specific mutation and crossover operators have been tried on TSP. The paper Genetic Algorithms for the Traveling Salesman Problem: A Review of Representations and Operators published in AI Review in 1999 provides a good overview. I have implemented the operators called position based crossover and displacement mutation described on pages 16 and 24 repsectively. If you choose to study the TSP you must implement at least one other crossover and mutation operator. You can use one of the other operators described in this paper or you can invent your own new operators. You should compare the performance of your operators to the operators I provided.
In order to implement TSP in Pyro, you need to extend the Gene class as well as the GA class. Here is an initial implementation that you can work from tsp.py. First try the very small data set test.tsp. Then go on to the data set from Djibouti dj89.tsp, or search for other data sets available online.
Be sure to discuss your idea with me early on, so that I can determine whether it is an appropriate problem.