前言

這一篇文章較為詳細地介紹了模擬退火演算法，但是一沒有涉及程式碼，二沒有舉例，三沒有深入探討改進模型，四沒有聯絡其他演算法。

不過我比較佛，知錯不改，先這樣吧。

模擬退火演算法

模擬退火演算法來源於固體退火原理，是一種基於機率的演算法。模擬退火演算法是透過賦予搜尋過程一種時變且最終趨於零的機率突跳性，從而可有效避免陷入區域性極小並最終趨於全域性最優的序列結構的最佳化演算法。

1。物理退火過程

將固體加溫至充分高，再讓其徐徐冷卻（退火），加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。

2。演算法思想

物理中，

淬火

（快速降溫），會導致不是最低能態的非晶形；

退火

，可達到最低能量狀態。模仿自然界退火現象而得，利用了物理中固體物質的退火過程與一般最佳化問題的相似性。

模擬退火演算法從某一較高初溫出發，伴隨溫度引數的不斷下降，結合機率突跳特性在解空間中隨機尋找目標函式的全域性最優解，即在區域性最優解能機率性地跳出並最終趨於全域性最優。模擬退火演算法是一種通用的最佳化演算法，理論上演算法具有機率的全域性最佳化效能。

注：這裡應該瞭解什麼是區域性最優解和全域性最優解，還有普通貪心演算法，見

https：//

blog。csdn。net/effective

_coder/article/details/8736718

。

模擬退火演算法包含兩個部分即Metropolis演算法和退火過程。Metropolis演算法就是如何在區域性最優解的情況下讓其跳出來，是退火的基礎。1953年Metropolis提出重要性取樣方法，即以機率來接受新狀態，而不是使用完全確定的規則，稱為Metropolis準則，計算量較低。

3。Metropolis準則

在溫度為T時，接受能量從E（Xold）到E（Xnew）的機率為P：

4。模擬退火演算法的模型

Step1 設定初始溫度t = tmax, 任選初始解r = r0

Step2 內迴圈

Step2.1 從r的鄰域中隨機選一個解rt, 計算r和rt對應目標函

數值, 如rt對應目標函式值較小，則令r = rt; 否則若exp(-(E(rt)-E(r))/t)>random(0,1), 則令r=rt.

Step2.2 不滿足內迴圈停止條件（1. 目標函式均值穩定 2. 連續若干步的目標值變化較小 3. 固定的抽樣步數）時，重複Step2.1

Step3 外迴圈

Step3.1 降溫t = decrease(t)

Step3.2 如不滿足外迴圈停止條件，則轉Step2（1. 達到終止溫度 2. 達到迭代次數 3. 最優值連續若干步保持不變）；否則演算法結束

其中，模擬退火演算法新解的產生和接受的步驟：

第一步是由一個產生函式從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響（冷卻進度表（Cooling Schedule）包括控制引數的初值

t

及其衰減因子Δ

t

、每個

t

值時的迭代次數L和停止條件S）。

第二步是計算與新解所對應的目標函式差。因為目標函式差僅由變換部分產生，所以目標函式差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函式差的最快方法。

第三步是判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則： 若ΔT<0則接受S′作為新的當前解S，否則以機率exp（-ΔT/T）接受S′作為新的當前解S。

第四步是當新解被確定接受時，用新解代替當前解，這隻需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函式值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為捨棄時，則在原當前解的基礎上繼續下一輪試驗。

模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S（是演算法迭代的起點）無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以機率l 收斂於全域性最優解的全域性最佳化演算法；模擬退火演算法具有並行性。

5。流程圖

6。應用場景

在已知的某個定義域內求函式最優值的問題通常有以下三種情況，以求最小值問題為例（求最大值可以轉換為求最小值）：

· 如果是離散取值，則可以用窮舉法獲得問題最優解

· 如果取值連續，且函式是凸函式，則可以用梯度下降等方法獲得最優解

· 如果連續非凸，雖說根據已有的近似求解法能夠找到問題解，可解是否是最優的還有待考量，很多時候若初始值選擇的不好，非常容易陷入區域性最優值

模擬退火演算法就是為了應對第三種情況而提出的。

7.需注意的問題

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

(1) 溫度T的初始值設定問題

溫度

T

的初始值設定是影響模擬退火演算法全域性搜尋效能的重要因素之一、初始溫度高，則搜尋到全域性最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全域性搜尋效能可能受到影響。

(2) 退火速度問題，即每個

T

值的迭代次數

模擬退火演算法的全域性搜尋效能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜尋是相當必要的，但這也需要計算時間。迴圈次數增加必定帶來計算開銷的增大。

(3) 溫度管理問題

溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算複雜度的切實可行性等問題，常採用如下所示的降溫方式：

注：為了保證較大的搜尋空間，

α

一般取接近於1的值，如0。95、0。9。