概率爬山法（Probabilistic Hill Climbing，PHC）是一種局部搜索算法，它結合了隨機性和貪婪搜索的特點，是對爬山算法（Hill Climbing Algorithm）的一種變體或擴展。與傳統的爬山法不同，PHC不是總是選擇最優的鄰居作為下一步的移動，而是以一定的概率選擇最優鄰居，同時以一定的概率接受非最優或甚至更差的鄰居。這種方法有助于算法跳出局部最優解，增加找到全局最優解的可能性。

一、爬山算法基礎

定義：爬山算法是一種局部搜索算法，常用于解決優化問題。它模擬了登山者尋找山峰的過程，通過逐步改進當前的解決方案，以期達到一個局部最優解。

核心思想：從當前解出發，通過與相鄰解的比較來尋找更優解。每次迭代中，算法會探索當前解的周圍區域，尋找能夠帶來改進的潛在解，并更新當前解為最優的候選解。

應用場景：爬山算法廣泛應用于數學建模、機器學習中的參數調優、運籌學中的路徑規劃、生物信息學中的蛋白質結構預測等領域。

前面說過的幾種爬山法變體在選擇下一步時的區別：

（1）爬山算法（Hill Climbing Algorithm，HCA）是在鄰域內搜索最優解作為下一步方向；

（2）隨機化爬山法（Stochastic Hill Climbing）是隨機選擇下一個移動的鄰近解作為下一步方向；

（3）首次爬山法（First-Choice Hill Climbing）是選擇第一個比當前解好的解作為下一步方向；

（4）最陡上升爬山法（Steepest-Ascent Hill Climbing）是鄰域內搜索使目標函數值增長最快的解作為下一步方向。

二、基本原理

概率爬山法的核心思想是在每一步都以一定的概率接受更優的鄰居，同時以一定的概率接受非最優的鄰居。這種隨機性可以幫助算法逃離局部最優解，探索更廣泛的搜索空間。

（1）隨機性引入：在爬山算法的搜索過程中，通過引入隨機因素來增加算法的多樣性，從而有可能跳出局部最優解。這類似于隨機重啟爬山算法（Stochastic Hill Climbing），在搜索過程中以一定的概率重新選擇起始點或接受較差的解。

（2）概率選擇：在比較當前解與鄰居解時，不是簡單地選擇最優解，而是根據一定的概率分布來選擇解。例如，可以設置一個溫度參數，根據當前解與鄰居解的差異和溫度參數來決定接受鄰居解的概率。這種方法類似于模擬退火算法（Simulated Annealing），它結合了概率機制和溫度下降策略來探索解空間。

三、算法步驟

（1）初始化：在搜索空間中隨機選擇一個初始狀態。

（2）選擇鄰居：從當前狀態選擇一組鄰居。

（3）評估鄰居：計算每個鄰居的狀態值（或目標函數值）。

（4）選擇下一步：以一定的概率p選擇最優鄰居作為下一步的移動，或者以1?p的概率隨機選擇一個鄰居（包括當前狀態）。

（5）更新狀態：將選擇的鄰居作為新的狀態。

（6）檢查停止條件：如果達到最大迭代次數或滿足其他停止條件，則停止算法；否則，返回步驟2。

圖1 概率爬山法流程圖

四、概率爬山法的數學公式

（1）初始化解：設初始解為，通常是在解空間內隨機選擇的。其中表示從解空間中均勻隨機選擇一個解。

（2）鄰域解生成：對于當前解，生成一個或多個鄰域解