Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP701 Nature Inspired Computing

Assignment 1 Part 1: Genetic Algorithm

(Worth 25% of the total marks for COMP701)

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’scity 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 andy 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)  Experiment by modifying one or more parameters (such as population size, probability of crossover and mutation) 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 parentselection 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 aJupyter 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.