[科普中國]-隨機爬山法

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

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

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

隨機重新開始爬山算法是基于最陡爬山算法，其實就是加一個達到全局最優(yōu)解的條件，如果滿足該條件，就結(jié)束運算，反之則無限次重復(fù)運算最陡爬山算法。1

評價爬山算法屬于局部搜索算法的一份子，因此是一種解決最優(yōu)化問題的啟發(fā)式算法。

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

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

嘗試交換函數(shù)對于每一個狀態(tài)，需要有一個評價函數(shù)對其進行估值評價。在此，我選用沖突數(shù)作為評價指標(biāo)，存在沖突數(shù)越多的狀態(tài)，其評價就越差。顯然，最優(yōu)解的評價結(jié)果為0，即不存在沖突。

對傳入的狀態(tài)進行交換嘗試，如果交換后的狀態(tài)評價結(jié)果小于當(dāng)前傳入狀態(tài)，就進行交換，將新狀態(tài)返回；否則，不交換，直接返回原先的狀態(tài)。
對于模擬退火算法，這里就需要加上一個temperature變量，當(dāng)鄰居狀態(tài)不是更優(yōu)，但是溫度夠高，達到了振蕩指標(biāo)時，也可以進行狀態(tài)轉(zhuǎn)換。同時，temperature值是在不斷減小的。2

本詞條內(nèi)容貢獻者為:

李斌 - 副教授 - 西南大學(xué)