# 隨城市規模 n 的動態參數調優與策略選型

[TOC]

針對旅行推銷員問題 ($TSP$) 的組合爆炸特性，遺傳演算法 ($GA$) 的效率取決於參數與算子隨問題規模 $n$ 的動態調整。

---

## 群體規模與初始化策略 (Population & Initialization)

### 群體規模的設定
群體規模 $P$ 決定了每一代對搜尋空間進行「抽樣」的覆蓋率。
* **建議關係**：$$P(n) \approx \alpha \cdot n \quad (\alpha \in [2, 4])$$
* **為什麼**：當 $n$ 增加，搜尋空間按階乘成長，必須增加族群數量以維持基因多樣性。若 $P$ 太小會導致演算法在早期就因基因趨同而陷入局部解；若 $P$ 太大則會導致運算時間過長。實務上，配合多執行緒運算，通常將上限設在 $500 \sim 1000$。

### 初始化隨機性的保證
初始化的品質決定了演化起點的廣度。
* **策略**：使用隨機置換 (Random Permutation)。
* **實作技術**：在 C++ 中應拋棄傳統 `rand()`，改用 `std::mt19937` (Mersenne Twister) 生成器配合 `std::shuffle`。
* **為什麼**：高品質的偽隨機數能確保初始個體在 $n!$ 的解空間中呈均勻分佈，避免初始基因庫出現偏差，這對後續的全球搜尋 (Global Search) 至關重要。

---

## 選擇算子與演化壓力 (Selection & Pressure)

### 錦標賽選擇法與精英保留策略
建議採用 **錦標賽選擇法 (Tournament Selection)** 並強制執行 **精英保留 (Elitism)**。

* **錦標賽規模 (Tournament Size $k$)**
* **實作決策**：在本專案的 Memetic 架構下，我們將 $k$ 固定為較小的常數 (如 $k=3$)。
* **深度理由**：由於我們引入了強大的 **2-Opt 局部搜尋**，個體在每一代都會被強烈地「拉向」局部最優。如果此時 GA 再施加過大的選擇壓力（$k$ 太大），基因多樣性會迅速喪失，導致過早收斂。透過「弱選擇壓 (Small $k$) + 強局部搜尋 (2-Opt)」的組合，我們能同時兼顧全域探索的廣度與局部收斂的深度。
* **為什麼不選輪盤法**：輪盤法會受適應度絕對數值的縮放影響（例如兩個解只差 $0.001$，機率幾乎一樣），導致選擇壓力消失。錦標賽法只看「排名」，能穩定維持演化動力。
* **精英保留 (Elitism)**
* **策略**：每一代強制保留前 $1\% \sim 5\%$ 的最優個體不經過交叉與突變，直接進入下一代。
* **為什麼**：GA 本質上是隨機搜尋，精英保留能確保已找到的最佳路徑「永不丟失」，保證適應度曲線單調不減。

---

## 基因算子與搜尋效率 (Crossover & Mutation)

### 最佳基因交換策略：順序交叉 (Order Crossover, OX)

對於 $TSP$ 這種置換排列（Permutation）問題，傳統的單點或多點交叉會破壞路徑的合法性（導致城市重複或遺漏）。**OX 交叉** 是公認最有效的策略，它能完美保留親代的「相對順序」特徵。

#### 1. 演算法執行邏輯（含具體範例）

假設城市編號為 $1 \sim 9$，我們隨機選定兩個切點（索引 3 到 6）：

* **親代 A (P1)**: `[1 2 3 | 4 5 6 7 | 8 9]`
* **親代 B (P2)**: `[9 8 7 | 6 5 4 3 | 2 1]`

**Step 1: 片段繼承 (Segment Inheritance)**
將 P1 切點間的基因直接複製給子代，其餘位置暫空：
* **子代 (Child)**: `[? ? ? | 4 5 6 7 | ? ?]`

**Step 2: 建立環狀填補序列 (Circular Filling)**
這是 OX 的精華。我們從 P2 的 **第二個切點之後** (即索引 7) 開始，繞一圈列出 P2 的城市順序：
1. P2 原始順序（從索引 7 開始）：`2 -> 1 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3`
2. **過濾**：去掉子代已擁有的城市 (`4, 5, 6, 7`)
3. **填補序列**：`2 -> 1 -> 9 -> 8 -> 3`

**Step 3: 環狀填滿子代**
同樣從子代的 **第二個切點之後** (索引 7) 開始，按填補序列依序塞入：
* 位置 7: `2`
* 位置 8: `1`
* 位置 0: `9` (繞回最前面)
* 位置 1: `8`
* 位置 2: `3`

**最終子代結果**: `[9 8 3 | 4 5 6 7 | 2 1]`

#### 2. 為什麼 OX 最好？
* **合法性保證**：子代自動成為一個合法的排列（Permutation），無需額外的「修復（Repair）」機制。
* **結構保護**：$TSP$ 的核心在於「城市的相對順序」。OX 能保留親代優良的路徑片段（Sub-tours），比一般交叉更能捕捉空間幾何特徵。
* **保護環狀鄰接關係 (Circular Adjacency)**：
* **為什麼不從索引 0 開始填？** 由於 $TSP$ 是閉合迴路，陣列首尾在物理意義上是相連的。從切點後方開始「環狀填補」，能確保親代 B 中原本位於首尾的連續片段不被隨意切斷，最大限度守住親代留下的鄰接特徵（Edge Preservation）。
* **效能優化 ($O(n)$)**：在 C++ 實作中，我們使用 **布林查表 (Boolean Lookup Table)** 或 `std::vector<bool>` 記錄已使用的城市 ID，將重複檢查的時間降至 $O(1)$。

---

### 交配率與突變率的設定：開發與探索的平衡

這兩者決定了演算法在「局部開發 (Exploitation)」與「全域探索 (Exploration)」之間的平衡。

* **交配率 (Crossover Rate, $p_c$)**
* **建議範圍**：$0.7 \sim 0.9$。
* **物理意義**：演化的主推動力。高交配率確保優秀的基因特徵能透過重組快速擴散。
* **啟發式實驗**：交配並不保證子代一定優於親代，它本質上是一種「有方向的隨機嘗試」。透過高交配率產生大量樣本，再利用**選擇壓力**過濾掉失敗的實驗，從而累積優良的路徑片段。

* **突變率 (Mutation Rate, $p_m$)**
* **黃金法則**：$$p_m(n) \approx \frac{1}{n}$$
* **數學意義**：這是基於 **期望值 (Expected Value)** 的設定。目的是讓每個染色體在每一代中「期望發生一次變動」。
* **風險控制**：
* **若 $p_m$ 太高**：演算法會退化為「隨機搜尋（Random Search）」，破壞已經收斂的優良結構。
* **若 $p_m$ 太低**：族群多樣性喪失，容易陷入「局部最佳解（Local Optimum）」。
## 停止標準與效能平衡 (Stopping Criteria)

### 停止標準的定義
建議採用雙重判斷：**最大迭代代數** 與 **停滯容忍度 (Stagnation Limit)**。

* **建議代數**：$$G(n) \approx 100 \cdot n$$
* **停滯判斷**：連續 $20n$ 代沒有更新最優解則終止。
* **為什麼**：當 $n$ 增加時，收斂所需的代數會隨之拉長。單純固定代數無法應對不同規模的問題，引入停滯判斷能有效節省在演化後期「無效迭代」的運算資源。

---

## 參數調整建議表 (針對不同城市規模 $n$)

| 城市規模 $n$ | 群體規模 $P$ | 突變率 $p_m$ | 錦標賽規模 $k$ | 停滯代數上限 |
| :--- | :--- | :--- | :--- | :--- |
| **小 ($n=20$)** | 100 | 0.05 | 3 | 100 |
| **中 ($n=50$)** | 200 | 0.02 | 3 | 500 |
| **大 ($n=100$)** | 500 | 0.01 | 10 | 3 |

### 複雜度與並行化需求
整體的計算時間複雜度為 $$O(G \cdot P \cdot n)$$。由於 $G, P$ 皆與 $n$ 呈正相關，總成本約為 $O(n^3)$。這解釋了為什麼針對大規模問題，使用 **C++ 多執行緒** 同時計算多個個體的適應度是實務上的必然選擇。

## 問題建模與距離矩陣 (Problem Modeling & Distance Matrix)

在實作 $TSP$ 時，距離的計算效率是決定演化速度的關鍵。透過合理的數學建模，可以大幅降低重複運算的成本。

### 對稱性 $TSP$ ($Symmetric \ TSP$) 建模
在標準的歐幾里得空間中，城市間距離具備對稱性，即從城市 $i$ 到 $j$ 的距離等於從 $j$ 到 $i$ 的距離：
$$d_{ij} = d_{ji}$$
這意味著距離矩陣 $D$ 是一個實對稱矩陣 ($D = D^T$)，且對角線元素（城市到自身的距離）恆為 $0$：
$$d_{ii} = 0$$

### 距離矩陣的預計算 (Pre-computation)
為了將適應度計算的複雜度從 $O(n^2)$ 降低至 $O(n)$，系統會在初始化階段建立一個 $n \times n$ 的扁平化一維陣列 (Flat Array) 以提升緩存友善性 (Cache Friendliness)。
* **計算公式**：
$$d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$
* **存取邏輯**：
在 C++ 中透過索引偏移進行 $O(1)$ 查表：
$$\text{index} = i \times n + j$$

---

## 演算法有效性驗證 (Validation Methodology)

由於遺傳演算法屬於啟發式搜尋，無法保證絕對最優解。為了證明系統的效能與可靠度，採用以下三種驗證機制。

### 基準測試 (Benchmarking via TSPLIB)
使用國際標準測試集（如 `berlin52` 或 `eil51`）來驗證演算法的精準度。
* **指標**：比較系統產出解與已知全域最優解 (Global Optimum) 的差距幅度：
$$\text{Gap} = \frac{\text{Result} - \text{Best}}{\text{Best}} \times 100\%$$
* **價值**：量化演算法在特定規模下的收斂品質。

### 統計魯棒性測試 (Statistical Robustness)
針對同一問題進行 $N \geq 30$ 次獨立實驗。除了平均值與標準差，我們特別引入 **變異係數 (CV, Coefficient of Variation)**：
* **公式**：$$CV = \frac{\sigma}{\mu} \times 100\%$$
* **工程意義**：反映演算法的「穩定輸出能力」。在本專案中，我們將目標設定為 $CV \leq 2\%$，這代表無論隨機種子如何變化，演算法都能穩定收斂至相近的解品質，這對工業排程系統至關重要。
### 基進演算法對照 (Baseline Comparison)
將 $GA$ 產出結果與 **隨機搜尋 (Random Search)** 及 **貪婪演算法 (Greedy / Nearest Neighbor)** 進行效能對比。
* **評估標準**：
1. 收斂速度：達到特定適應度所需的迭代次數。
2. 最終解品質：$GA$ 應在合理時間內顯著優於貪婪演算法。