人工智慧/搜尋/迭代改進/爬山法

爬山法作為一種最佳化技術

爬山法是一種用於解決計算難題的最佳化技術。它最適合用於具有“狀態描述本身包含解決問題所需所有資訊”特性的問題（Russell & Norvig, 2003）。 該演算法在記憶體效率方面表現出色，因為它不維護搜尋樹：它只關注當前狀態和直接的未來狀態。

爬山法嘗試透過評估函式迭代改進當前狀態。“考慮所有[可能的]狀態，它們分佈在景觀表面上。景觀上任意點的海拔高度對應於該點狀態的評估函式值”（Russell & Norvig, 2003）。

與其他迭代改進演算法相比，爬山法始終嘗試進行改進當前狀態的更改。換句話說，只有當鄰近景觀中存在更高點時，爬山法才能前進。

迭代改進和爬山法

爬山法可能遇到的主要問題是區域性最大值問題。當演算法停止向最優解前進時就會出現這種情況；主要原因是鄰近狀態中缺乏立即改進。

可以透過多種方法避免區域性最大值問題：模擬退火透過允許一些步驟降低當前狀態的立即最優性來解決此問題。模擬退火等演算法“有時會做出使情況變得更糟的更改，至少是暫時性的”（Russell & Norvig, 2003）。 這使得能夠避免搜尋路徑中的死衚衕。

隨機重啟爬山法

解決區域性最大值問題的另一種方法涉及對問題空間進行反覆探索。“隨機重啟爬山法從隨機生成的初始狀態開始進行一系列爬山搜尋，並在每個搜尋停止或沒有明顯進展時執行”（Russell & Norvig, 2003）。 這使得能夠比較許多最佳化試驗，從而使找到最優解成為一個使用足夠迭代次數來處理資料的問題。

虛擬碼演算法

function HILL-CLIMBING(problem) returns a solution state
     inputs: problem, a problem
     static: current, a node
         next, a node
     current <— MAKE-NODE(INITIAL-STATE[problem])
     loop do
         next— a highest-valued successor of current
         if VALUE[next] < VALUE[current] then return current
         current *—next
     end

(Russell & Norvig, 2003)

計算複雜度

由於使用的評估只關注當前狀態，因此爬山法不會遇到計算空間問題。其計算複雜度的來源是探索問題空間所需的時間。

對於大多數問題空間，隨機重啟爬山法可以在多項式時間內找到最優解。但是，對於一些 NP 完全問題，區域性最大值的數量可能是導致指數級計算時間的因素。為了解決這些問題，一些研究人員已經研究使用機率論和區域性抽樣來指導爬山演算法的重啟。（Cohen, Greiner, & Schuurmans, 1994）。

應用

爬山法可以應用於任何當前狀態允許使用準確評估函式的問題。例如，旅行推銷員問題、八皇后問題、電路設計以及各種其他現實世界問題。爬山法已被用於歸納學習模型中。其中一個例子是 PALO，這是一個機率爬山系統，它模擬歸納學習和加速學習。該系統的一些應用已被納入“基於解釋的學習系統”和“效用分析”模型。（Cohen, Greiner, & Schuurmans, 1994）。

爬山法也被用於機器人技術中，以管理多機器人團隊。其中一個例子是 Parish 演算法，它允許在多機器人系統中進行可擴充套件且高效的協調。研究小組設計了“一個機器人團隊[它]必須協調其行動，以保證定位熟練的逃避者。”（Gerkey, Thrun, & Gordon, 2005）。

他們的演算法透過使用爬山法允許機器人選擇是單獨工作還是團隊合作。因此，執行 Parish 的機器人“根據區域性進度梯度集體爬山，但隨機進行橫向或向下移動，以幫助系統擺脫區域性最大值。”（Gerkey, Thrun, & Gordon, 2005）。