一. 爬山算法 ( Hill Climbing )

爬山算法是一種簡單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個最優(yōu)解作為當(dāng)前解，直到達到一個局部最優(yōu)解。爬山算法實現(xiàn)很簡單，其主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。假設(shè)C點為當(dāng)前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優(yōu)的解。

二. 模擬退火(SA,Simulated Annealing)思想

在實際日常中，人們會經(jīng)常遇到如下問題：在某個給定的定義域X內(nèi)，求函數(shù)f(x)對應(yīng)的最優(yōu)值。此處以最小值問題舉例（最大值問題可以等價轉(zhuǎn)化成最小值問題），形式化為： 

如果X是離散有限取值，那么可以通過窮取法獲得問題的最優(yōu)解；如果X連續(xù)，但f(x)是凸的，那可以通過梯度下降等方法獲得最優(yōu)解；如果X連續(xù)且f(x)非凸，雖說根據(jù)已有的近似求解法能夠找到問題解，可解是否是最優(yōu)的還有待考量，很多時候若初始值選擇的不好，非常容易陷入局部最優(yōu)值。 

隨著日常業(yè)務(wù)場景的復(fù)雜化，第三種問題經(jīng)常遇見。如何有效地避免局部最優(yōu)的困擾？模擬退火算法應(yīng)運而生。其實模擬退火也算是啟發(fā)式算法的一種，具體學(xué)習(xí)的是冶金學(xué)中金屬加熱-冷卻的過程。由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所發(fā)明的，V.?ern在1985年也獨立發(fā)明此演算法。

不過模擬退火算法到底是如何模擬金屬退火的原理？主要是將熱力學(xué)的理論套用到統(tǒng)計學(xué)上，將搜尋空間內(nèi)每一點想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。演算法先以搜尋空間內(nèi)一個任意點作起始：每一步先選擇一個“鄰居”，然后再計算從現(xiàn)有位置到達“鄰居”的概率。若概率大于給定的閾值，則跳轉(zhuǎn)到“鄰居”；若概率較小，則停留在原位置不動。

一、模擬退火算法基本思想

模擬退火其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。在迭代更新可行解時，以一定的概率來接受一個比當(dāng)前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。以下圖為例，假定初始解為左邊藍色點A，模擬退火算法會快速搜索到局部最優(yōu)解B，但在搜索到局部最優(yōu)解后，不是就此結(jié)束，而是會以一定的概率接受到右邊的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達全局最優(yōu)點D，于是就跳出了局部最小值。 

根據(jù)熱力學(xué)的原理，在溫度為T時，出現(xiàn)能量差為dE的降溫的概率為p(dE)，表示為: 

其中k是波爾茲曼常數(shù)，值為k=1.3806488(13)×10?23，exp表示自然指數(shù)，且dE<0。因此dE/kT<0，所以p(dE)函數(shù)的取值范圍是(0,1)。滿足概率密度函數(shù)的定義。其實這條公式更直觀意思就是：溫度越高，出現(xiàn)一次能量差為p(dE)的降溫的概率就越大；溫度越低，則出現(xiàn)降溫的概率就越小。

在實際問題中，這里的“一定的概率”的計算參考了金屬冶煉的退火過程。假定當(dāng)前可行解為x，迭代更新后的解為x_new，那么對應(yīng)的“能量差”定義為： 

其對應(yīng)的“一定概率”為： 

注：在實際問題中，可以設(shè)定k=1。因為kT可以等價于一個參數(shù)T。如設(shè)定k=2、T=1000，等于直接設(shè)定T=2000的效果。

二、模擬退火算法描述

初始化：初始溫度T（充分大），溫度下限Tmin（充分?。跏冀鉅顟B(tài)x(是算法迭代的起點)，每個T值的迭代次數(shù)L； 對l=1,2,...,L做第3至第6步； 產(chǎn)生新解x_new: (x_new=x+Δx)； 利計算增量Δf=f(x_new)?f(x)，其中f(x)為優(yōu)化目標(biāo)； 若Δf<0(若尋找最大值，Δf>0)則接受x_new作為新的當(dāng)前解，否則以概率exp(?Δf/(kT))接受x_new作為新的當(dāng)前解； 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。(終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。)； T逐漸減少，且T>Tmin，然后轉(zhuǎn)第2步。

三、模擬退火算法的優(yōu)缺點

模擬退火算法的應(yīng)用很廣泛，可以高效地求解NP完全問題，如貨郎擔(dān)問題(Travelling Salesman Problem，簡記為TSP)、最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)等等，但其參數(shù)難以控制，不能保證一次就收斂到最優(yōu)值，一般需要多次嘗試才能獲得（大部分情況下還是會陷入局部最優(yōu)值）。觀察模擬退火算法的過程，發(fā)現(xiàn)其主要存在如下三個參數(shù)問題：

　　(1) 溫度T的初始值設(shè)置問題 
　　溫度TT的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。

　　(2) 退火速度問題，即每個TT值的迭代次數(shù) 
　　模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。一般來說，同一溫度下的“充分”搜索是相當(dāng)必要的，但這也需要計算時間。循環(huán)次數(shù)增加必定帶來計算開銷的增大。

　　(3) 溫度管理問題 
　　溫度管理問題也是模擬退火算法難以處理的問題之一。實際應(yīng)用中，由于必須考慮計算復(fù)雜度的切實可行性等問題，常采用如下所示的降溫方式： 

T=α×T.α∈(0,1).

注：為了保證較大的搜索空間，α一般取接近于1的值，如0.95、0.9。

　　關(guān)于爬山算法與模擬退火，有一個有趣的比喻：

　　爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。

　　模擬退火：兔子喝醉了。它隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。

附上模擬退火算法偽代碼：

四. 使用模擬退火算法解決旅行商問題

　　旅行商問題 ( TSP , Traveling Salesman Problem ) ：有N個城市，要求從其中某個問題出發(fā)，唯一遍歷所有城市，再回到出發(fā)的城市，求最短的路線。

　　旅行商問題屬于所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時間復(fù)雜度是O(N!) 。

　　使用模擬退火算法可以比較快的求出TSP的一條近似最優(yōu)路徑。（使用遺傳算法也是可以的，我將在下一篇文章中介紹）模擬退火解決TSP的思路：

1. 產(chǎn)生一條新的遍歷路徑P(i+1)，計算路徑P(i+1)的長度L( P(i+1) )

2. 若L(P(i+1)) < L(P(i))，則接受P(i+1)為新的路徑，否則以模擬退火的那個概率接受P(i+1) ，然后降溫

3. 重復(fù)步驟1，2直到滿足退出條件

　　產(chǎn)生新的遍歷路徑的方法有很多，下面列舉其中3種：

1. 隨機選擇2個節(jié)點，交換路徑中的這2個節(jié)點的順序。

2. 隨機選擇2個節(jié)點，將路徑中這2個節(jié)點間的節(jié)點順序逆轉(zhuǎn)。

3. 隨機選擇3個節(jié)點m，n，k，然后將節(jié)點m與n間的節(jié)點移位到節(jié)點k后面。

五. 算法評價

        模擬退火算法是一種隨機算法，并不一定能找到全局的最優(yōu)解，可以比較快的找到問題的近似最優(yōu)解。 如果參數(shù)設(shè)置得當(dāng)，模擬退火算法搜索效率比窮舉法要高。

相關(guān)知識

[轉(zhuǎn)]爬山算法和模擬退火算法簡介
PEAK爬山模擬器
爬山模擬器下載
爬山模擬器3d下載
一種模擬爬山健身器的制作方法
爬山模擬器最新版下載安裝包
爬山模擬器免廣告游戲下載安裝
健身房模擬器爬山丘安卓版下載
2023年全球及中國環(huán)境模擬測試行業(yè)頭部企業(yè)市場占有率及排名調(diào)研報告
爬山注意事項 爬山的英文

網(wǎng)址: 爬山算法 ( Hill Climbing )/模擬退火(SA,Simulated Annealing) http://www.u1s5d6.cn/newsview1602942.html