Skip to main content

LH Evolutionary Computation - Assignment 1

Solving a Travelling Salesman Problem using SA and GA 使用 SA 和 GA 解決旅行商問題​

Aim 目的​

You are required to implement Simulated Annealing (SA) and Genetic Algorithm (GA) to solve the Odyssey of Ulysses 22 cities Travelling Salesman Problem (TSP) as listed here Download here. 您需要實施模擬退火 (SA) 和遺傳算法 (GA) 來解決尤利西斯奧德賽 22 個城市的旅行商問題 (TSP)，如此處所列下載 此處。

You can read the article The Optimized Odyssey and the original Simulated Annealing paper published in Science can be found here. 您可以在外部站點閱讀文章 The Optimized Odyssey。可以在 此處 找到發表在《科學》雜誌上的原始模擬退火論文。

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. 你可以使用任何編程語言來完成這個作業。但是，如果您想使用 Matlab/Octave 以外的語言，您應該使您的程序可執行/可運行。例如，如果你使用 Java，你需要編譯它。
  2. Implement the Simulated Annealing (SA) and Genetic Algorithm (GA) algorithms. For GA, you need to choose an appropriate encoding scheme. 實施模擬退火 (SA) 和遺傳算法 (GA) 算法。對於 GA，需要選擇合適的編碼方案。
  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. 對每個算法執行最多 100 次試運行以調整參數（提示：您可能需要進行一些文獻搜索以找到合適的參數範圍）。記錄參數和性能。
  4. After obtaining good parameters, execute 30 independent runs with 10000 fitness (objective function) evaluations for each algorithm (Note: for SA, that's 10000 interactions 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. 獲得良好的參數後，對每個算法執行 30 次獨立運行，進行 10000 次適應性（目標函數）評估（注意：對於 SA，這是 10000 次交互，但對於 GA，這取決於種群規模和最大世代數）。分別記錄每種算法 30 次運行結果的平均距離和標準偏差。
  5. Compare the results for these two algorithms statistically using a Wilcoxon signed-rank test. If you do not know the statistical hypothesis test, please read this article. 使用 Wilcoxon 符號秩檢驗 從統計學上比較這兩種算法的結果。如果您不知道統計假設檢驗，請閱讀本文。
  6. Write a report which should at least include the following sections: 寫一份報告，至少應該包括以下部分：
    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. 簡單介紹 SA 和 GA 算法。您需要證明您的設計決策的合理性，例如 GA 的編碼方案，並使用流程圖和偽代碼來解釋這些算法。
    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 您還應該列出從兩種算法的 30 次運行中獲得的所有平均結果和標準偏差
    4. Discuss how you compare the results obtained by SA and GA statistically. 討論如何從統計學上比較 SA 和 GA 獲得的結果。
  7. Submit your report as a single PDF file and your source code separately (.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 both report and code please resubmit the report pdf and code separately. 將您的報告作為單個 PDF 文件和您的源代碼分別提交（.m .py .c 優先於筆記本文件）。如有必要，您可以使用 .tar 或 .tgz 或 .targz（如果可能，請避免使用 rar）。如果您已經提交了包含報告和代碼的 zip 文件，請分別重新提交報告 pdf 和代碼。