局部搜索

在計算機科學中，局部搜索是解決最優化問題的一種元啟發式算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。局部搜索的優點是簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。

局部搜索廣泛應用於計算機科學（主要是人工智能）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

應用

對於某些計算起來非常複雜的最優化問題，比如各種NP完全問題，要找到最優解需要的時間隨問題規模呈指數增長，因此誕生了各種啟發式算法來退而求其次尋找次優解。局部搜索就是其中的一種方法。

局部搜索算法可以用來解決以下問題：

1. 最小頂點覆蓋問題：尋找圖中包含最少頂點的覆蓋。
2. 旅行商問題：尋找圖中經過所有頂點的最短迴路。
3. 布爾可滿足性問題：尋找滿足一組子句的變量賦值。

描述

局部搜索算法從一個候選解開始，反覆探索其鄰域，並移動到鄰域中的最後解。所以要使用局部搜索算法必須首先在搜索空間中定義鄰域。比如，在最小頂點覆蓋問題中，一個覆蓋的鄰域可以是只改變一個頂點能夠到達的另一種覆蓋；在布爾可滿足性問題中，一個變量賦值的鄰域可以是只改變一個變量的值能到達的所有賦值。對於同一個問題可以有很多種鄰域的定義。如果一個局部優化算法將鄰域定義為只改變 k 個成分能夠到達的解，那麼這個算法可以稱為 k-opt。

通常，每個候選解的鄰域包含多個解。所謂局部搜索，就是只根據鄰域中的信息來決定移動方向。如果選擇的是最大化目標函數的解，那麼這種局部搜索算法又可以叫做爬山算法。當鄰域中已經沒有比當前最優的解的時候，局部搜索就困在了局部最優解。

為了離開局部最優解，可以使用很多種方法，包括在不同的初始值重複整個算法，或者使用更複雜的策略如模擬退火。

局部搜索可以設計成在運行足夠長時間後終止，或者連續n步沒有改善時終止。所以局部搜索是一種任一時間算法：即便它運行中被強行中止，也能返回正確的解。

局部搜索是典型的近似算法，因為它找到的解不一定是最優的。即便沒有中斷算法執行，也可能因為陷入局部最優而無法找到更好的解。

對於某些問題，可以定義一個非常大的鄰域，甚至是指數級大小的鄰域，只要在鄰域中能夠高效地找到最優解。這樣的算法叫做大規模鄰域搜索。

參見

局部搜索屬於以下領域：

• 啟發式算法
  • 元啟發式算法
• 最優化
  • 隨機最優化

局部搜索包括以下話題：

• 爬山算法
• 模擬退火
• 禁忌搜索

參考資料

• Battiti, Roberto; Mauro Brunato; Franco Mascia. Reactive Search and Intelligent Optimization. Springer Verlag. 2008. ISBN 978-0-387-09623-0. （原始內容存檔於2012-03-16）. 
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems （頁面存檔備份，存於互聯網檔案館）, Siam Journal of Computing 33(3).