# C++ Parallel GA 實作藍圖與研發紀錄

[TOC]

本文件紀錄了 `Parallel-GA-TSP` 專案的架構演進與研發歷程。內容包含初期的 **「快速原型開發策略 (MVP Strategy)」** 以及後期為了提升尋優精準度與系統穩健性所規劃的 **「TSPLIB 深度驗證計畫」**，展現了從工程快攻到嚴謹科學驗證的完整思維流程。

---

## 1. 專案架構設計 (System Architecture)

採用模組化設計以確保演算法邏輯、多執行緒調度與資料解析之間的低耦合性。

### 目錄結構

/Parallel-GA-TSP
├── include/
│   ├── Core/           # 演算法核心 (GASolver, ParallelEvaluator)
│   ├── Parser/         # 資料解析 (TSPLIBParser)
│   └── Types.h         # 全域型別與配置
├── src/                # 實作邏輯 (.cpp)
├── examples/           # 示範程式 (main.cpp)
├── tests/              # 單元測試與效能標竿測試
├── data/               # TSPLIB 標準測試資料集 (.tsp)
└── CMakeLists.txt      # 現代化建構腳本 (支援 Presets)

### 模組職責分配

| 模組名稱 | 核心職責 | 技術要點 |
| --- | --- | --- |
| **Types** | 定義 `City`, `Individual`, `GAConfig` | 封裝 -dependent 參數管理邏輯 |
| **GASolver** | 演化循環控制 (選、交、突、局部搜尋) | 實作 的 Order Crossover (OX) |
| **ParallelEvaluator** | 任務導向的多執行緒計算引擎 | 處理 密集運算的平行化 |
| **Utils** | 靜態工具組 (隨機數、距離矩陣) | 查表優化與 `std::mt19937` 管理 |
| **TSPLIBParser** | 標準格式檔案解析 | 自動化 NODE_COORD_SECTION 數據提取 |

---

## 2. 階段一：快速原型實作 (MVP Prototype Phase)

在專案初期，為了快速驗證並行 GA 在 TSP 問題上的可行性，我們採取了「快攻開發策略」。

### 關鍵決策紀錄

* **參數管理 (Hardcoded vs. JSON)**：
* **策略**：優先使用 `struct GAConfig` 硬編碼配置。
* **理由**：為了降低編譯環境配置風險與時效性，捨棄外部 JSON 庫，改以「一處修改、全域生效」的配置結構達成同樣靈活性。

* **測試驅動 (Example vs. GTest)**：
* **策略**：優先撰寫 `examples/main.cpp` 與自研標竿測試。
* **理由**：直觀展示收斂曲線，比配置完整的測試框架更符合初期快速迭代的需求。

### 開發時程追蹤 (Blitz Timeline)

* **基礎建設 (45 min)**：定義資料結構與 CMake 環境。
* **數學工具 (45 min)**：預計算距離矩陣，將適應度計算轉為查表。
* **核心算子 (120 min)**：實作 OX 交叉、錦標賽選擇與突變邏輯。
* **並行工程 (60 min)**：使用 `std::async` 分配計算任務。

---

## 3. 階段二：R&D 驗證與效能調優 (R&D & Validation)

在完成 MVP 後，我們引入了國際標準測項進行深度驗證，將專案從「可用」提升至「精準」。

### TSPLIB 深度驗證計畫

為了證明演算法的尋優能力，我們導入了以下測項：

* **Small (eil51, berlin52)**：驗證基礎收斂至最優解的能力。
* **Medium (st70, rat99)**：驗證混合架構 (GA + 2-Opt) 處理複雜路徑的能力。
* **Large (ch150)**：針對 150 城市規模進行平行運算的壓力測試。

### 統計魯棒性指標 (Robustness Metrics)

我們不只追求一次性的 Best，更注重演算法的穩定性：

* **平均誤差 (Gap %)**：比較實測解與 TSPLIB 官方最優解的差距。
* **變異係數 (CV %)**：執行 30 次獨立實驗計算 ，確保系統輸出的穩定性。

---

## 4. 工程規範與實作準則 (Coding Standards)

為了確保程式碼的可維護性，本專案遵循以下準則：

* **命名風格**：Class/Struct 使用 `PascalCase`；Member Variables 使用 `m_` 前綴。
* **數學語意**：命名體現數學意義。例如路徑命名為 `permutation` 而非 `list`，距離命名為 `euclideanDistance`。
* **平行化安全**：適應度計算採用唯讀 (Read-only) 存取距離矩陣，實現 **Lock-free Parallelism**。

---

## 💡 研發心得與未來展望

透過這個專案，我深刻體會到啟發式演算法在處理 問題時的彈性。未來的優化方向將朝向：

1. **動態突變率 (Adaptive Mutation)**：隨收斂停滯程度自動調高突變率。
2. **硬體加速**：探索使用 CUDA 進行 GPU 端的族群評估。

---