Task

The aim is to find a set of genetic algorithm (GA) parameters that consistently produces good results for solving a travelling salesman problem (TSP) with 200 cities. Each student’s city map is different and is given in a table in the assignment description on Canvas. Note that the files are not in the TSPLIB format; only the x and y coordinates of each city are given.

Suggested Procedure

(1)  Design a GA with an arbitrary initial design. Use it to solve the given TSP. Run it 10 times. The results may not be very good but it can serve as a baseline for comparison. Save these results.

(2)  Use  the  first  50  cities  and  use  a  population  size  of  50  while  keeping  other  GA parameters the same as in (1). Obtain the results of 10 runs.

(3) Try changing one or more parameters (probabilities of crossover and mutation, for example) and repeat (2).

(4)  Base on the results from (2) and (3), decide on a suitable set of parameters for 50 cities. Use this setting for later experiments.

(5)  Experiment with different parent selection mechanisms and compare the results of 10 runs each.

Which selection policy works better? Keep this policy for later experiments.

(6)  Do the same comparison with different crossover and mutation mechanisms.

(7)  Using this new set of parameters and  mechanisms (with the  population scaled up relative to the problem size), obtain the results of 10 runs for the original approx. 200- city TSP.

How do these results compare with what you have obtained in (1)?

Submission Requirements

Write a report as a Jupyter notebook with relevant code cells that you have used to generate the results. This report should have:

(1) Your initial design of your GA.

(2) The experiments and results of your initial design with the TSP problem you are given.

(3) The experiments and results when refining your initial design. Show only those with significant improvements (no more than 4). Provide analyses of each set of results and discuss what contributed to the improvements.