# 遺傳演算法求解 TSP：實作結果與實驗紀錄

[TOC]

本文件彙整了 `Parallel-GA-TSP` 專案的最終測試結果。透過單元測試驗證模組正確性，並利用 TSPLIB 標準測項評估演算法在不同規模下的收斂品質與平行加速效能。

---

## 1. 模組正確性驗證 (Unit Testing)

在執行大規模運算前，透過獨立測試確保基礎組件之健壯性。

* **[test_utils] 數學工具測試**：
* 驗證隨機城市生成範圍。
* 確保距離矩陣之對稱性。
* **結果**：`SUCCESS`
* **[test_parser] 資料解析測試**：
* 針對 `berlin52.tsp` 進行完整性檢查。
* 驗證維度 (Dimension) 與首尾節點座標準確度。
* **結果**：`SUCCESS`
* **[test_ga] 演算法集成測試**：
* 驗證小型 4 城市案例。
* 確保演化循環能精確收斂至理論最優路徑。
* **結果**：`SUCCESS (Execution Time: 0.026s)`

---

## 2. 平行運算效能分析 (Parallel Performance)

針對運算密集型 (CPU Bound) 的適應度評估環節，對比單執行緒與多執行緒之效能。

* **測試環境**：MacBook Air M2 (8-Core CPU)
* **測試規模**：City Count = 2,000, Population Size = 5,000

| 模式 | 執行時間 (Seconds) | 加速倍率 (Speedup) |
| --- | --- | --- |
| 序列模式 (Serial) | 0.02616 s | 1.00x |
| **平行模式 (Parallel)** | **0.00368 s** | **7.09x** |

> **研發評論**：在 8 核心處理器上達成 **7.09 倍加速**，證明了基於 `std::async` 的任務平行化架構具有極低的排程開銷與優異的負載平衡能力。

---

## 3. TSPLIB 標竿測試數據 (Accuracy & Stability)

本測試針對每個測項進行 **10 次獨立實驗**，統計其最優值、平均值與穩定度。

### 綜合測試報告 (Summary Table)

| Instance | 城市規模 (n) | TSPLIB 最優解 | 實測最佳 (Best) | 誤差 (Gap %) | 穩定度 (CV %) | 平均耗時 (s) |
| --- | --- | --- | --- | --- | --- | --- |
| **berlin52** | 52 | 7542 | 7710.83 | **2.24%** | 2.76% | **3.79s** |
| **st70** | 70 | 675 | 694.47 | **2.88%** | 2.18% | **5.29s** |
| **ch150** | 150 | 6528 | 6801.80 | **4.19%** | 1.75% | **7.87s** |

### 實驗發現分析

1. **精準度穩定**：在所有測項中，誤差 (Gap) 均維持在 **5% 以內**。
2. **高魯棒性 (Robustness)**：變異係數 (CV) 均在 **2-3% 左右**，代表遺傳演算法在隨機種子變動下，仍能穩定收斂至相近的高品質解。
3. **收斂瓶頸**：在大型問題 `ch150` 中，雖然 Gap 仍屬優異，但執行時間隨之增加。這驗證了我們在設計階段提出的 ** n-dependent 參數調整** 的必要性。

---

## 4. 實作心得與結語

本專案成功展示了從「純數學理論」到「高效能 C++ 實作」的轉化過程。

* **核心價值**：
* 結合 **Memetic Algorithm (GA + 2-Opt)** 有效解決了傳統啟發式算法在後期收斂精準度不足的痛點。
* 平行化架構讓大規模問題的求解時間從分鐘級降至秒級。
* **韌體工程思維的應用**：
* 透過扁平化矩陣與絕對路徑注入等技術，優化了底層存取效率與系統穩健性。

透過此次研發，證明了在處理 問題時，**「演算法設計」與「硬體效能發揮」**同樣重要。這不僅是一次學術驗證，更是邁向專業研發工程師的重要里程碑。

---