隨機爬山法

隨機爬山法是一種局部貪心的最優算法，該算法的主要思想是：每次拿相鄰點與當前點進行比對，取兩者中較優者，作為爬坡的下一步.

基本介紹

• 中文名：隨機爬山法
• 套用領域：數學分析，機器學習

簡介

依次尋找該點X的鄰近點中首次出現的比點X價值高的點，並將該點作為爬山的點(此處說的價值高，在該題中是指Z或f(x，y)值較大)。依次循環，直至該點的鄰近點中不再有比其大的點。我們成為該點就是山的頂點，又稱為最優點.。

最陡爬山算法是在首選爬山算法上的一種改良，它規定每次選取鄰近點價值最大的那個點作為爬上的點。

隨機重新開始爬山算法是基於最陡爬山算法，其實就是加一個達到全局最優解的條件，如果滿足該條件，就結束運算，反之則無限次重複運算最陡爬山算法。

評價

爬山算法屬於局部搜尋算法的一份子，因此是一種解決最最佳化問題的啟發式算法。

在實際運用中，爬山算法不會前瞻與當前狀態不直接相鄰的狀態，只會選擇比當前狀態價值更好的相鄰狀態，所以簡單來說，爬山算法是向價值增長方向持續移動的循環過程。

由於它的貪婪特性，使得在解決問題中容易陷入局部極大值(Local maxima，指一個比所有鄰居狀態價值要高但是比全局最大值要低的狀態)，我們能採取隨機重啟(Random restart)以及模擬退火(Simulated annealing)的方法來改進。

嘗試交換函式

對於每一個狀態，需要有一個評價函式對其進行估值評價。在此，我選用衝突數作為評價指標，存在衝突數越多的狀態，其評價就越差。顯然，最優解的評價結果為0，即不存在衝突。

對傳入的狀態進行交換嘗試，如果交換後的狀態評價結果小於當前傳入狀態，就進行交換，將新狀態返回；否則，不交換，直接返回原先的狀態。
對於模擬退火算法，這裡就需要加上一個temperature變數，當鄰居狀態不是更優，但是溫度夠高，達到了振盪指標時，也可以進行狀態轉換。同時，temperature值是在不斷減小的。