模拟退火算法

模拟退火算法的原理

模拟退火算法來源于固體退火原理，将固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體内部粒子随溫升變為無序狀，内能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡态，最後在常溫時達到基态，内能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e(-ΔE/(kT))，其中E為溫度T時的内能，ΔE為其改變量，k為Boltzmann常數。用固體退火模拟組合優化問題，将内能E模拟為目标函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模拟退火算法：由初始解i和控制參數初值t開始，對當前解重複“産生新解→計算目标函數差→接受或舍棄”的叠代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅叠代求解法的一種啟發式随機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的叠代次數L和停止條件S。

模拟退火算法的模型

1模拟退火算法可以分解為解空間、目标函數和初始解三部分。

2模拟退火的基本思想:

(1)初始化：初始溫度T(充分大)，初始解狀态S(是算法叠代的起點)，每個T值的叠代次數L。

(2)對k=1，……，L做第(3)至第6步：

(3)産生新解S′。

(4)計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數。

(5)若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解。

(6)如果滿足終止條件則輸出當前解作為最優解，結束程序。

終止條件通常取為連續若幹個新解都沒有被接受時終止算法。

(7)T逐漸減少，且T->0，然後轉第2步。

模拟退火算法的步驟

模拟退火算法新解的産生和接受可分為如下四個步驟：

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

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

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

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

模拟退火算法與初始值無關，算法求得的解與初始解狀态S(是算法叠代的起點)無關；模拟退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優解的全局優化算法；模拟退火算法具有并行性。

模拟退火算法僞代碼

步驟

1）随機給定初始狀态，設定合理的退火策略。（選擇各參數值、初始溫度T0、降溫規律等）。

2）令x‘=x+△x（△x為小的均勻分布的随機擾動），計算△E=E（x'）-E（x）。

3）若△E<0，則接受x'為新的狀态，否則以概率P=exp(-△E/(kT))接受x'，其中k為波爾茲曼常數。具體做法是産生0到1之間的随機數a，若P>a則接受x'，否則拒絕x'，系統仍停留在狀态x。

4）重複步驟2)、3）直到系統達到平衡狀态。

5）按第1）步中給定的規律降溫，在新的溫度下重新執行2）~4）步，直到T=0或者達到某一預定低溫。

由以上步驟可以看出，△E>0時任然有一定的概率（T越大概率越大）接受x'，因而可以跳出局部極小點。理論上說，溫度T的下降應該不快于：

T(t)=T0/(1+lnt),t=1,2,3,...其中T0為起始高溫，t為時間變量。常用的公式是T(t)=aT0(t-1)，其中0.85≦a≦0.98。