# 第四章 Local Search Algorithms and Optimization Problems

## Local Search 演算法

局部搜尋（Local Search）是一種基於解空間的優化方法，主要用於解決組合優化問題。其核心思想是從一個初始解開始，通過在鄰域中尋找更好的解來逐步改進。

- 局部搜尋 = 使用一個目前狀態，並轉移到鄰近的狀態
- **不需要全局資訊**：僅依賴當前狀態的鄰域資訊。
- **適用於大規模問題**：能夠處理搜索空間非常大的問題。
- 使用非常少的記憶體
- 找到的解通常是可接受的
- **可能陷入局部最優**：需要額外的策略來跳出局部最優解。

### 爬山演算法（Hill Climbing）

爬山演算法是一種簡單的局部搜尋方法，通過不斷選擇鄰域中最好的解來尋找全局最優解。像是在爬山一樣，當前的狀態就像山上的位置，接著盡可能的向上爬，直到無法再上升為止。其主要步驟包括：

1. 從初始狀態開始。
2. 在鄰域中選擇一個比當前解更好的解。
3. 重複此過程，直到無法找到更好的解為止。

#### 優點

- 簡單易實現。
- 適合於連續改進的問題。

#### 缺點

- 容易陷入局部最佳解。
- 無法處理具有多個峰值的問題。

#### 改進方法

- **隨機重啟**：在多次運行中隨機選擇不同的初始狀態。
- **擴展鄰域**：在每次迭代中考慮更大的鄰域。（看得更遠）

### 模擬退火（Simulated Annealing）

模擬退火是一種基於物理退火過程的演算法，通過在早期允許接受較差解來避免陷入局部最佳解。其主要步驟包括：

1. 初始化溫度和初始狀態。
2. 隨機選擇鄰域中的一個狀態。
3. 根據接受概率函數決定是否接受該解。
- 初期接受較差解的機率較高，隨時間（溫度）降低。
4. 隨著迭代次數增加，逐漸降低溫度。

#### 優點

- 能夠跳出局部最佳解。
- 適合於解空間複雜的問題。

#### 缺點

- 參數調整（如初始溫度和降溫速率）較為困難。

### Local Beam Search

Local Beam Search 是一種改進的局部搜尋方法，通過保持多個狀態來探索狀態空間。其主要步驟包括：

#### 特色

- **多個候選狀態**
- 與爬山演算法只維護一個當前狀態不同，Beam Search 同時追蹤多個狀態。
- 這些狀態被稱為「光束」（beam）。
- **鄰域生成**：
- 每個候選解都會生成其鄰域解。
- 將所有鄰域狀態合併，從中選擇最好的幾個狀態作為下一次迭代的候選狀態。
- 光束的大小（beam width）是固定的，僅保留前幾個最佳解。
- **選擇策略**：
1. 初始化多個解。
2. 在每個解的鄰域中選擇最好的解。
3. 將所有選擇的解合併，並保留最好的幾個解。
- 通常根據目標函數的值選擇最好的狀態。
4. 重複以上過程，直到滿足終止條件。
5. 最後選擇最好的解作為結果。

### 遺傳演算法（Genetic Algorithms）

遺傳演算法模仿自然選擇的過程，通過選擇、交叉和突變操作來生成更好的解。其主要步驟包括：

1. 初始化種群。
2. 計算每個個體的適應度。
3. 根據適應度選擇父母進行交叉。
4. 對後代進行隨機突變。
5. 重複以上過程，直到滿足終止條件。

#### 優點

- 適合於非線性和多峰值問題。
- 能夠探索更大的解空間。

#### 缺點

- 計算成本較高。
- 需要設計適當的適應度函數。