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

You are required to implement Simulated Annealing (SA)  and Genetic Algorithm (GA) to solve the 48 cities (US state capitals) from TSPLIB as listed hereLinks to an external site.. You can also download the file here: att48.tsp.gzDownload att48.tsp.gz

Requirements:

1. You can use any programming language to complete this assignment. However, if you want to use languages other than Matlab/Octave, you should make your program executable/runnable. For example, if you use Java, you need to compile it.

2. Implement the Simulated Annealing (SA) and  Genetic Algorithm (GA)  algorithms. For GA, you need to choose an appropriate encoding scheme.

3. Execute a maximum of 100 trial runs for each algorithm to tune the parameters (Hint: You probably need to do some literature search to find the appropriate parameter ranges). Record the parameters and the performance.

4. After obtaining suitable parameters, execute 30 independent runs with 10000 fitness (objective function) evaluations for each algorithm (Note: for SA, that's 10000 iterations, but for GAs, that depends on the population size and the number of maximum generations). Record the average distance and standard deviation from the results over the 30 runs for each algorithm, respectively.

5. Compare the results for these two algorithms statistically using a Wilcoxon signed-rank testLinks to an external site.. Please read this article if you do not know the statistical hypothesis test.

6. Write a report which should at least include

1. Brief introduction of the SA and GA algorithms. You need to justify your design decisions, e.g., the encoding scheme for GA, and explain these algorithms by using a flowchart and pseudo-code.

2. Discuss the parameters and how they impacted the performance of the algorithms.

3. You should also list all the average results and standard deviations obtained from the 30 runs of the two algorithms.

4. Discuss how you compare the results obtained by SA and GA statistically.

7. Submit your report separately as a PDF file and your source code (.m .py .c preferred over notebook files). If necessary, you may use .tar or .tgz or .targz (if possible, avoid rar). If you have already submitted a zip file with the report and code, please resubmit the report pdf and code separately.

Marking Scheme (total 25 points):

· Correct implementation of SA (6 marks)

· Correct implementation of GA (6 marks)

· Report: Satisfied requirements 6 and 7 of a well-presented, well-explained report, including critical reflection and discussion of results (13 marks)

Submission guideline:

You must submit your report as a single PDF file, and separately your source code (.m, .py, .c etc), and compiled binary executable (if applicable), see point 7 above).