---
# System prepended metadata

title: 第四章 Local Search Algorithms and Optimization Problems
tags: [人工智慧]

---

# 第四章 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. 重複以上過程，直到滿足終止條件。

#### 優點

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

#### 缺點

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