# 第四章 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. 重複以上過程，直到滿足終止條件。 #### 優點 - 適合於非線性和多峰值問題。 - 能夠探索更大的解空間。 #### 缺點 - 計算成本較高。 - 需要設計適當的適應度函數。