# GA 核心原理與 Memetic 策略設計
[TOC]

這是一份關於遺傳演算法（Genetic Algorithm, GA）的學習大綱，旨在協助你從基礎理論過渡到實務應用。

# 遺傳演算法基礎理論與核心概念

## 生物學背景與演化邏輯

### 演化計算的轉化模型

遺傳演算法將自然界的演化規律抽象化為計算步驟。在解決 TSP 問題時，我們將每一條可能的路徑視為一個個體。透過適者生存的原則，長度較短的路徑（適應度高）會有更高的機率被保留並進入交配池，進而產生更優秀的後代。

### 基因型與表現型的映射

在演算法實作中，區分這兩個層次能幫助我們設計更有效的算子：

* **基因型（Genotype）**：指演算法內部儲存的資料結構。在 TSP 中，這通常是一個整數數列，例如 `[0, 2, 3, 1]`。
* **表現型（Phenotype）**：指個體在現實問題中的具體含義，即「城市間的旅行順序」。
* **映射過程**：演算法在基因型層面進行交配與突變，但在表現型層面計算路徑總長度，以此評估個體的優劣。

### 隨堂練習

<details>
<summary>點擊查看練習：關於基因型與表現型</summary>
問題：在 TSP 程式碼實作中，如果我們修改了路徑數列中的數值順序，這是在操作基因型還是表現型？

解答：這是在操作基因型。我們透過改變基因型（數列順序）來產生新的表現型（旅行路徑），進而觀察適應度是否提升。

</details>

## 編碼機制

### 二進位編碼

將參數轉換為 0 與 1 的位元串。雖然在早期的遺傳演算法中非常流行，但其缺點是難以直觀地表達 TSP 的路徑約束，且容易在突變後產生非法解（例如重複訪問同一個城市）。

### 實數編碼

直接使用浮點數作為基因。這種方式在連續空間的最佳化問題（如神經網路權重調整）中表現優異，但對於需要處理「順序」與「排列」的 TSP 問題並非首選。

### 排列編碼

這是 TSP 問題的核心編碼方式。基因序列中的每一個元素代表一個城市，且每個元素在序列中必須是唯一的。

* **優點**：能夠完美確保每個城市都被訪問且不重複。
* **挑戰**：傳統的交配算子會破壞這種唯一性，因此需要專門的算子（如順序交配法 OX）來維持排列的合法性。

### 隨堂練習

<details>
<summary>點擊查看練習：編碼安全性</summary>
問題：若在 TSP 中誤用了二進位突變（將單一位元由 0 變 1），可能會遇到什麼問題？

解答：這會破壞排列的完整性。例如原本代表城市的編號可能會變為不存在的城市索引，或是導致路徑中出現重複的城市編號。因此在 TSP 中，我們必須使用交換位置的突變方式，而非位元翻轉。在 HTML 或程式邏輯中，這種約束可以視為一種 `完整性檢查`。

</details>

## 適應度函數設計

### 適應度與目標函數

在 TSP 中，我們的目標是最小化總路徑距離 。然而，遺傳演算法的選擇機制通常傾向於保留數值較大的個體，因此需要將最小化問題轉換為最大化問題。

### 數學定義

通常使用距離的倒數作為適應度函數：

$$
f(x) = \frac{1}{\sum_{i=1}^{n} dist(c_i, c_{i+1})}
$$

### 隨堂練習

<details>
<summary>點擊查看練習：適應度邏輯</summary>
問題：為什麼在 TSP 中不能直接將路徑距離作為適應度值來進行輪盤法選擇？

解答：因為在輪盤法中，數值越大被選中的機率越高。如果直接使用距離，則路徑越長（越差）的個體反而越容易被留下。因此必須進行倒數轉換，確保距離 ` 最小值 ` 對應到適應度 `最大值`。

</details>

---

# 核心運作機制

## 群體初始化

### 初始解集的生成

群體初始化是演化過程的第一步。在 TSP 問題中，這代表隨機生成一群符合規範的路徑（排列）。

* **群體規模（Population Size）**：通常設定在 50 到 500 之間。規模太小會導致搜尋空間不足，規模太大幅則會消耗過多運算資源。
* **隨機性（Randomness）**：每個個體必須是所有城市編號的隨機排列，確保演算法從解空間的各個角落開始搜尋。

### 群體多樣性的重要性

多樣性是指群體中個體之間的差異程度。

* **避免過早收斂（Premature Convergence）**：如果初始群體過於相似，演算法很快就會陷入區域最佳解（Local Optimum），而無法找到全域最佳解（Global Optimum）。
* **探索與利用的平衡**：初始化良好的群體提供了豐富的基因素材，讓演算法在早期階段能充分「探索」解空間。

### 隨堂練習

<details>
<summary>點擊查看練習：群體初始化策略</summary>
問題：在解決 TSP 時，若將所有初始個體都設為相同的路徑，演算法還能運作嗎？會發生什麼事？

解答：演算法理論上仍可運作，但效率會極低。因為交配算子在兩個相同的個體間無法產生新特徵，演化將完全依賴機率極低的突變算子。這會導致群體缺乏 `多樣性`，極難逃離當前的 `區域最佳解`。

</details>

---

## 適應度函數設計 (Fitness Function Design)

### 從目標函數到適應度

適應度函數是導引演化方向的唯一標準。它必須能精確反映出一個「解」的好壞。

* **目標函數 (Objective Function)**
在 $TSP$ 中，目標函數是路徑的總長度 $L$，我們希望 $L$ 越小越好。
* **適應度轉換**
遺傳演算法通常預設「適應度越高越好」，因此需要將最小化問題轉換為最大化問題。

---

### 數學模型

對於 $TSP$ 問題，最常見的適應度 $f$ 定義如下：

$$f = \frac{1}{L} = \frac{1}{\sum_{i=1}^{n-1} d(c_i, c_{i+1}) + d(c_n, c_1)}$$

其中：
* $c_i$ 代表路徑中第 $i$ 個訪問的城市。
* $d(c_i, c_j)$ 代表城市 $i$ 與城市 $j$ 之間的歐幾里得距離：
$$d(i, j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$

---

### 適應度比例化 (Fitness Scaling)

在演化早期，如果群體中出現一個遠優於其他的個體，其適應度 $f$ 可能會過大。為了避免該個體迅速主宰群體造成「過早收斂」，有時會使用縮放技術來調整壓力。常用的方法包括：

* **線性縮放**：$f' = a \cdot f + b$
* **排名縮放**：根據排序位置而非絕對數值給予適應度。

---

### 隨堂練習

<details>
<summary>點擊查看練習：適應度函數與選擇壓</summary>
問題：假設路徑 $A$ 的長度為 $100$，路徑 $B$ 的長度為 $200$。在 $f = 1/L$ 的設計下，路徑 $A$ 的適應度是 $B$ 的幾倍？這對選擇過程有什麼影響？

解答：
1. 路徑 $A$ 的適應度 $f_A = 1/100 = 0.01$。
2. 路徑 $B$ 的適應度 $f_B = 1/200 = 0.005$。
3. 因此 $f_A$ 是 $f_B$ 的 $2$ 倍。

這代表在選擇階段（如輪盤法），路徑 $A$ 被保留下來的機率是 $B$ 的 $2$ 倍，這精確體現了「適者生存」的數學邏輯。
</details>
# 遺傳算子詳解

遺傳算子是演化演算法的核心驅動力，透過模擬生物遺傳過程中的選擇、雜交與變異，使群體不斷向最佳解進化。

## 選擇算子 (Selection Operators)

### 篩選策略與演化壓力

選擇算子的目標是從目前群體中挑選出優秀的個體作為父代。選擇壓力 (Selection Pressure) 決定了演算法收斂的速度：壓力大則收斂快但易陷於區域解，壓力小則探索充分但收斂慢。

* **輪盤法 (Roulette Wheel Selection)**
個體被選中的機率與其適應度成正比。假設族群大小為 $N$，個體 $i$ 的適應度為 $f_i$，則其被選中的機率 $P_i$ 為：
$$P_i = \frac{f_i}{\sum_{j=1}^{N} f_j}$$
適應度越高的個體，在輪盤上佔據的面積（被選中的期望值）越大。

* **錦標賽選擇法 (Tournament Selection)**
隨機從群體中取出 $k$ 個個體，將其中最適應的個體保留。這種方法不需計算全域適應度比例，實作簡單且效率高。在實作上，我們常調整 $k$ 的大小來控制選擇壓力。

* **精英保留策略 (Elitism)**
直接將當前世代中表現最好的個體複製到下一代，確保最優解不會因為隨機的交叉或突變算子而意外消失。這在 $TSP$ 的收斂過程中極其重要。

---

### 隨堂練習

<details>
<summary>點擊查看練習：選擇法的比較</summary>
問題：在輪盤法中，如果群體中某一個體的適應度遠高於其他個體，會造成什麼後果？

解答：這會導致該個體在選擇過程中佔據絕對優勢，使得其基因迅速主宰整個群體。這種現象稱為「過早收斂 (Premature Convergence)」，會大幅降低群體的「多樣性 (Diversity)」，導致演算法無法找到全域最佳解。
</details>
## 交配算子

### 基因交換機制

交配算子負責結合兩個父代的特徵，產生具有潛力的新後代。這是遺傳演算法中主要的「利用」機制。

* **單點與多點交配 (Single/Multi-point Crossover)**：
在基因序列中隨機選取一個或多個切點，交換父代間的段落。
* **均勻交配 (Uniform Crossover)**：
以一定的機率（如 0.5）決定子代每一個位置的基因來自哪一個父代。

### TSP 的特殊限制

對於 TSP 問題，上述標準交配法會導致非法解。例如父代 A 為 `[0, 1, 2, 3]`，父代 B 為 `[3, 2, 1, 0]`，若在位置 2 切分，子代可能會出現 `[0, 1, 1, 0]`，這違反了城市不能重複的原則。因此 TSP 實務上多採用 **順序交配法 (OX)**。

### 隨堂練習

<details>
<summary>點擊查看練習：交配算子與合法性</summary>
問題：在處理 TSP 旅人尋路問題時，為何不能直接套用單點交配？

解答：因為單點交配僅是單純的區段交換，無法保證交換後的基因序列仍然是一個 `排列 `。這會導致路徑中出現 `重複城市` 或 `遺漏城市`，使該路徑在表現型層面上變為非法解。

</details>

---

## 突變算子

### 維持多樣性的關鍵

突變算子以極低的機率隨機改變個體的基因，防止演算法在演化後期因群體趨同而停滯不前。

* **位元反轉突變 (Bit Inversion)**：
僅適用於二進位編碼，將 0 變為 1 或 1 變為 0。
* **交換突變 (Swap Mutation)**：
**最常用於 TSP**。隨機選取兩個位置，交換其城市編號。例如 `[0, 1, 2, 3]` 突變後變為 `[0, 3, 2, 1]`。
* **變異強度調整**：
演化初期可設定較高的突變率以進行大範圍搜尋，後期則調低以利於精細最佳化。

### 隨堂練習

<details>
<summary>點擊查看練習：突變算子的角色</summary>
問題：如果將突變率設定為 100%（即每個個體都必定突變），這時的遺傳演算法會變成什麼？

解答：當突變率極高時，演算法會失去累積優良基因的能力，這時遺傳演算法會退化成隨機搜尋（Random Search），無法透過 `演化累積` 趨向最佳解。

</details>

---

# 演算法分析與實戰應用

## 收斂條件與參數調優

### 演算法停止準則

遺傳演算法是一個隨機搜尋過程，因此需要明確的收斂條件來決定何時停止演化並輸出最佳解。常見的停止準則包括：

* **最大世代數（Max Generations）**：設定演算法運行的上限（如 1000 代），防止無窮盡的運算。
* **適應度停滯（Fitness Stagnation）**：當連續多代（如 50 代）的最佳適應度沒有顯著提升時，視為演算法已找到當前環境下的最優解。
* **達到預設目標**：如果適應度已達到使用者預設的滿意值（如 TSP 路徑長度低於特定數值），則停止運算。

### 核心參數設定

參數的選擇會極大影響演算法的效率與品質：

* **交配率（Crossover Rate, ）**：通常設定在 0.6 至 0.9 之間。高交配率能加速新特徵的產生，但也可能過快破壞優良基因。
* **突變率（Mutation Rate, ）**：通常設定在 0.001 至 0.05 之間。突變率應維持在較低水準，以確保演化具有方向性而非隨機漫遊。
* **群體大小**：較大的群體具有較好的多樣性，但每一代的計算成本也會隨之增加。

### 隨堂練習

<details>
<summary>點擊查看練習：參數調優的影響</summary>
問題：在進行 TSP 最佳化時，如果發現演算法在非常早期的世代就停止更新最佳解，且得到的結果很不理想，這可能與哪些參數設定有關？

解答：這通常代表發生了 `過早收斂`。可能的原因包括：

1. 突變率設定太低，導致群體缺乏新基因。
2. 選擇壓力太大（例如精英保留比例過高），使得局部最優解迅速佔據群體。
3. 初始群體規模太小，導致搜尋空間不足。

</details>

## 典型應用場景

### 旅行推銷員問題 (TSP)

這是遺傳演算法最經典的舞台。

* **編碼方式**：排列編碼（Permutation Encoding）。
* **核心挑戰**：必須使用特殊的算子（如 OX 交配或交換突變）來確保路徑的合法性，即每個城市 < 恰好訪問一次 >。

### 背包問題 (Knapsack Problem)

在限制的重量下挑選價值最高的物品組合。

* **編碼方式**：二進位編碼（Binary Encoding）。
* **核心挑戰**：處理「超重」的無效解。通常透過處罰函數（Penalty Function）降低無效解的適應度，或是在初始化與算子中加入修正邏輯。

### 神經網路權重最佳化

在深度學習中，除了梯度下降法，遺傳演算法也可用於尋找最佳權重或網路架構（神經演化）。

* **編碼方式**：實數編碼（Real-value Encoding）。
* **優點**：不依賴梯度資訊，因此適用於不可導或具有大量局部最小值、雜訊嚴重的目標函數環境。

### 隨堂練習

<details>
<summary>點擊查看練習：問題與編碼的對應</summary>
問題：如果要使用遺傳演算法解決「排班問題」（將不同員工分配到不同時段且不衝突），你認為最適合使用哪種編碼方式？

解答：這類問題與 TSP 類似，涉及資源分配與約束條件，因此通常使用 `排列編碼` 或 ` 整數編碼`。我們需要確保特定的約束條件（如同一時段不重複排班）在基因操作過程中受到保護。

</details>

---

---

# 進階實作：Memetic 與平行化策略

在解決大規模 TSP 問題（如 $n > 100$）時，傳統 GA 常面臨收斂過慢的問題。本專案透過以下進階策略提升效能：

## 1. Memetic Algorithm：GA + 2-Opt 局部搜尋
為了平衡「廣域探索」與「局部精煉」，我們在演化循環中嵌入了 **2-Opt** 算子：
* **GA (Global Search)**：透過交叉與突變，確保搜尋路徑能跳出局部最佳陷阱。
* **2-Opt (Local Search)**：針對個體進行路徑去交錯優化，消除「交叉路徑」，極大化搜尋精準度。

## 2. $N$-dependent 動態參數調優
不同規模的 TSP 問題需要不同的演化壓力。本專案實作了隨 $n$ 變動的參數模型：
* **族群大小 ($P$)**：設定為 $4n$，確保搜尋空間隨問題維度同步擴張。
* **突變率 ($p_m$)**：設定為 $1/n$，確保每個個體平均發生 1 次突變，維持穩定擾動。
* **選擇壓力**：採用弱選擇壓力的錦標賽 ($k=3$)，將「精煉」的重任留給 2-Opt，避免過早收斂。

## 3. 並行評估加速 (Parallel Evaluation)
適應度計算是遺傳演算法中運算量最大的部分。
* **技術路徑**：採用 C++17 `std::async` 任務平行化。
* **實作效果**：將 $O(P \times n)$ 的計算負載分攤至多核 CPU，在 8 核心環境下達成約 **7x 的效能提升**，使大數據量的收斂實驗成為可能。