[科普中國(guó)]-隨機(jī)爬山法

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

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

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

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

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

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

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

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

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

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

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