ICT 219 Intelligent Systems

Laboratory 10

The program we will study today solves the traveling salesman problem, as described in Topic 11, using a genetic algorithm.

First, install the executable code on your machine by downloading the zip file TSPApp_exe.zip from the ICT219 website. Unzip the file to a convenient directory and run the file TSPApp.exe. A window will appear with File, GA and Help menus at the top,

some controls down the right hand side of the screen and a 2-dimensional map with a circle of 100 cities indicated as red dots.

The system is in the default configuration; if you press the Start button at the right, you will see the default parameters at the right operating with the GA to find an optimal path in blue within a few generations (for a circle, simply a circumference around the circle). Explored paths are indicated in white during processing.Displayed from left to right at the bottom of the screen is the number of points (cities), then the best path length and the generation in which it was found, then the current generation, and finally a clock. An optimal path will quickly be found, but the algorithm will continue to run until you press the Stop button.

It's important to understand the adjustable parameter fields down the right hand side of the window. Begin your experiments by setting these to reasonable values (described below), then try systematically varying them from there.

  • Co-evolution: a number of parallel populations (separate threads) from 1 till 16.

We want to keep things simple at this stage, so set this to 1 (a single population).

  • Population: a size of population (N), between 10 and 1000, depending on your experiment.100 is a reasonably computable figure for our purposes.
  • Elite: An elite GA always maintains the best e members in the population. Can range from 0 to N. Initially, set to 10.
  • Migration: a size of migrated genes, from 0 to N. A refinement to improve performance, but an extra complication at present. Set to 0 and ignore it.
  • Heuristics: a size of best genes improved via heuristics method in every epoch.

Another complicated refinement, set to 0 and ignore.

  • Crossover: probability of crossover, as a percentage. Choose about 70% for good results.
  • Mutation: probability of a mutation. Should usually be kept low, about 1%.
  • Selection combo: selection method (roulette rank, roulette cost and tournament)
  • Remove Twins checkbox: set using a natural selection algorithm. It eliminates identical genes which helps avoid premature convergence. Leave ticked.

You can set up a tour of 30 cities like the one described in this week's lecture by selecting File | New | Random from the drop down menu at the top of the window. Enter 30 points in the New Map box. You will see a map with 30 randomly distributed points. With the parameters set to the above recommendations, try a few runs by pressing the Start and Stop buttons and recording the optimal path length and number of generations the GA took to converge. Try different selection methods on the same settings. Then try it with a larger number of cities, say 200. Always record your settings and the results you obtained in your lab notebook, so that you can compare results.

Questions

1. With the parameters set as above and a map of 100 random cities, make 20 runs and record the number of generations it took to converge on an optimal solution. What is the maximum, minimum and average of these data? How do you account for such a wide range of run lengths in solving the same problem with the same settings?

2. Dramatically increase the mutation rate by setting it to 30%, and perform another run. What happens? Explain this in terms of your knowledge of the mutation operator.

3. Generate random city sets of 500, 600, 700, 800, 900 and 1000 points, and record the time to calculate a single generation (you might do this by having another person count off seconds while you monitor the generation counter). Plot this with set size on the horizontal axis and time on the vertical axis. Make plots for each of the three selection methods: roulette rank, roulette cost and tournament. Is there any difference in performance?

4. Princeton University's Traveling Salesman Problem Webpage shows, among other amazing things, an optimal path for a tour of 666 of the world's most interesting spots (see

Using the computer in front of you, would it be feasible to do this with 6,666 interesting spots? With your best methods, try to estimate the best, worse and average times you might expect to converge on a solution.