minx∈Xf(x).” role=”presentation”>minx∈Xf(x).minx∈Xf(x).

\min_{x \in X} f(x).

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

p(dE)=exp⁡(dEkT).” role=”presentation”>p(dE)=exp(dEkT).p(dE)=exp⁡(dEkT).

p(dE) = \exp(\frac{dE}{kT}).

Δf=f(x_new)−f(x).” role=”presentation”>Δf=f(x_new)−f(x).Δf=f(x_new)−f(x).

Δf = f(x\_new) − f(x).

p(Δf)={exp⁡(−ΔfkT)最小值优化问题exp⁡(ΔfkT)最大值优化问题” role=”presentation”>p(Δf)=⎧⎩⎨exp(−ΔfkT)exp(ΔfkT)最小值優化問題最大值優化問題p(Δf)={exp⁡(−ΔfkT)最小值優化問題exp⁡(ΔfkT)最大值優化問題

p(Δf) = \left\{ \begin{array}{ll}
\exp(-\frac{Δf}{kT}) & 最小值優化問題 \\
\exp(\frac{Δf}{kT}) & 最大值優化問題
\end{array} \right.

二、模擬退火演算法描述

1. 初始化：初始溫度T” role=”presentation” style=”position: relative;”>TTT（充分大），溫度下限Tmin” role=”presentation” style=”position: relative;”>TminTminT_{min}（充分小），初始解狀態x” role=”presentation” style=”position: relative;”>xxx(是演算法迭代的起點)，每個T” role=”presentation” style=”position: relative;”>TTT值的迭代次數L” role=”presentation” style=”position: relative;”>LLL；
2. 對l=1,2,…,L” role=”presentation” style=”position: relative;”>l=1,2,…,Ll=1,2,…,Ll= 1,2,…,L做第3至第6步；
3. 產生新解x_new” role=”presentation” style=”position: relative;”>x_newx_newx\_new: (x_new=x Δx” role=”presentation” style=”position: relative;”>x_new=x Δxx_new=x Δxx\_new = x Δx)；
4. 利計算增量Δf=f(x_new)−f(x)” role=”presentation” style=”position: relative;”>Δf=f(x_new)−f(x)Δf=f(x_new)−f(x)Δf = f(x\_new) − f(x)，其中f(x)” role=”presentation” style=”position: relative;”>f(x)f(x)f(x)為優化目標；
5. 若Δf&lt;0″ role=”presentation” style=”position: relative;”>Δf<0Δf<0Δf<0(若尋找最大值，Δf&gt;0″ role=”presentation” style=”position: relative;”>Δf>0Δf>0Δf>0)則接受x_new” role=”presentation” style=”position: relative;”>x_newx_newx\_new作為新的當前解，否則以概率exp⁡(−Δf/(kT))” role=”presentation” style=”position: relative;”>exp(−Δf/(kT))exp⁡(−Δf/(kT))\exp(-Δf/(kT ))接受x_new” role=”presentation” style=”position: relative;”>x_newx_newx\_new作為新的當前解；
6. 如果滿足終止條件則輸出當前解作為最優解，結束程式。(終止條件通常取為連續若干個新解都沒有被接受時終止演算法。)；
7. T” role=”presentation” style=”position: relative;”>TTT逐漸減少，且T&gt;Tmin” role=”presentation” style=”position: relative;”>T>TminT>TminT> T_{min}，然後轉第2步。

三、模擬退火演算法的優缺點

(1) 溫度T的初始值設定問題
溫度T” role=”presentation” style=”position: relative;”>TTT的初始值設定是影響模擬退火演算法全域性搜尋效能的重要因素之一、初始溫度高，則搜尋到全域性最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全域性搜尋效能可能受到影響。

(2) 退火速度問題，即每個T” role=”presentation” style=”position: relative;”>TTT值的迭代次數
模擬退火演算法的全域性搜尋效能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜尋是相當必要的，但這也需要計算時間。迴圈次數增加必定帶來計算開銷的增大。

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

T=α×T.α∈(0,1).” role=”presentation”>T=α×T.α∈(0,1).T=α×T.α∈(0,1).

T=\alpha \times T.\alpha \in (0,1).

四、模擬退火演算法Python實戰

minf(x)=(x−2)∗(x 3)∗(x 8)∗(x−9)” role=”presentation”>minf(x)=(x−2)∗(x 3)∗(x 8)∗(x−9)minf(x)=(x−2)∗(x 3)∗(x 8)∗(x−9)

\min f(x)=(x-2)*(x 3)*(x 8)*(x-9)

# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
def inputfun(x):
return (x-2)*(x 3)*(x 8)*(x-9)
initT = 1000 #初始溫度
minT = 1 #溫度下限
iterL = 1000 #每個T值的迭代次數
delta = 0.95 #溫度衰減係數
k = 1
initx = 10*(2*np.random.rand()-1)
nowt = initT
print "初始解：",initx
xx = np.linspace(-10,10,300)
yy = inputfun(xx)
plt.figure()
plt.plot(xx,yy)
plt.plot(initx,inputfun(initx),'o')
#模擬退火演算法尋找最小值過程
while nowt>minT:
for i in np.arange(1,iterL,1):
funVal = inputfun(initx)
xnew = initx (2*np.random.rand()-1)
if xnew>=-10 and xnew<=10:
funnew = inputfun(xnew)
res = funnew-funVal
if res<0:
initx = xnew
else:
p = np.exp(-(res)/(k*nowt))
if np.random.rand()<p:
initx = xnew
#            print initx-xnew
#    print initx
#    print nowt
nowt = nowt*delta
print "最優解：",initx
print "最優值：",inputfun(initx)
plt.plot(initx,inputfun(initx),'*r')
plt.show()

參考資料

1. http://wiki.mbalib.com/wiki/模擬退火演算法 模擬退火演算法