隨機(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é)