Assignment Part 1: Genetic Algorithm
(Worth 15% of the total marks for COMP815)
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.
(4) Your final (best) design and the results.
(5) A conclusion.
The text in your notebook should clearly describe your process and results. It is important
that the code cells, if run in the same sequence, should allow me to reproduce exactly what
you have generated. Appropriate headings should be used to make your notebook readable
by the marker. Also, make sure that you are using the instance of TSP specific to yourself.
Zip (do not use rar or other archive formats) your Jupyter notebook with any data files that
are needed for your code to work in a single file. Submit this file to Canvas.
