目录

1 引言

2  模退火算法理论

3 模拟退火原理

4 模拟退火法数学模型 

6 模拟退火算法流程 

7 案例1

7.1 案例

7.2 Python实现 

7.3 结果 

8 案例2 

8.1 案例

8.2 Python实现 

8.3 结果 

---

1 引言

      模拟退火算法(Simulated Annealing，SA)的思想最早由 Metropolis等人于1953年提出;Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题。模拟退火算法是一种基于Monte Carlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其目的在于为具有NP (Non-deterministic Polynomial)复杂性的问题提供有效的近似求解算法，它克服了其他优化过程容易陷入局部极小的缺陷和对初值的依赖性。模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展。它不同于局部搜索算法之处是以一定的概率选择邻域中目标值大的劣质解。从理论上说，它是一种全局最优算法。模拟退火算法以优化问题的求解与物理系统退火过程的相似性为基础，它利用Metropolis算法并适当地控制温度的下降过程来实现模拟退火，从而达到求解全局优化问题的目的。模拟退火算法是一种能应用到求最小值问题的优化过程。在此过程中，每一步更新过程的长度都与相应的参数成正比，这些参数扮演着温度的角色。与金属退火原理相类似，在开始阶段为了更快地最小化，温度被升得很高，然后才慢慢降温以求稳定。

      目前，模拟退火算法迎来了兴盛时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是它的应用研究显得格外活跃，已在工程中得到了广泛应用，诸如生产调度、控制工程、机器学习、神经网络、模式识别、图像处理、离散/连续变量的结构优化问题等领域。它能有效地求解常规优化方法难以解决的组合优化问题和复杂函数优化问题，适用范围极广。模拟退火算法具有十分强大的全局搜索性能，这是因为比起普通的优化搜方法，它采用了许多独特的方法和技术:在模拟退火算法中，基本不用搜索空间的知识或者其他的辅助信息，而只是定义邻域结构，在其邻域结构内选取相邻解，再利用目标函数进行评估:模拟退火算法不是采用确定性规则，而是采用概率的变迁来指导它的搜索方向，它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着更优化解的区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实际上有着明确的搜索方向。 

2  模退火算法理论

模拟退火算法以优化问题求解过程与物理退火过程之间的相似性为基础，优化的目标函数相当于金属的内能，优化问题的自变量组合状态空间相当于金属的内能状态空间，问题的求解过程就是找一个组合状态，使目标函数值最小。利用Metopolis算法并适当地控制温度的下降过程实现模拟退火,从而达到求解全局优化问题的目的。

3 模拟退火原理

模拟退火算法来源于固体退火原理，将固体加温至充分高,再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大;而徐徐冷却时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。模拟退火算法与金属退火过程的相似关系如表所示。根据Metropolis准则，粒子在温度T时趋于平衡的概率为-，其中E为温度T时的内能，AE为其改变量。用固体退火模拟组合优化问题，将内能E模拟为目标函数值，温度T演化成控制参数，即得到解组合优化问题的模拟退火算法:由初始解X和控制参数初值T开始，对当前解重复“产生新解一计算目标函数差一接受或舍弃”的迭代,并逐步减小T值，算法终止时的当前解即为所得近似最优解，这是基于MonteCarlo迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表控制，包括控制参数的初值T及其衰减因子K、每个T值时的迭代次数L和停止条件。 

              

4 模拟退火法数学模型 

模拟退火的主要思想是:在搜索区间随机游走(即随机选择点)，再利用Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度是Metropolis算法中的一个重要控制参数，可以认为这个参数的大小控制了随机过程向局部或全局最优解移动的快慢。

Metropolis是一种有效的重点抽样法，其算法为:系统从一个能量状态变化到另一个状态时，相应的能量从E1变化到E2，其概率为：

                                      

如果E2<E1，系统接受此状态否则，以一个随机的概率接受或丢弃此状态。状态2被接受的概率为:

这样经过一定次数的迭代，系统会逐渐趋于一个稳定的分布状态。

重点抽样时，新状态下如果向下，则接受(局部最优);若向上(全局搜索)，则以一定概率接受。模拟退火算法从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时组合优化问题的相对最优解。然后减小控制参数T的值，重复执行Metropolis算法，就可以在控制参数T趋于零时，最终求得组合优化问题的整体最优解。控制参数的值必须缓慢衰减。

温度是Metropolis算法的一个重要控制参数，模拟退火可视为递减控制参数T时Metroplis算法的迭代。开始时T值大，可以接受较差的恶化解;随着T的减小，只能接受较好的恶化解最后在T趋于0时，就不再接受任何恶化解了。

在无限高温时，系统立即均匀分布，接受所有提出的变换。T的衰减越小，T到达终点的时间越长;但可使马尔可夫(Markov)链减小，以使到达准平衡分布的时间变短。

6 模拟退火算法流程 

                                

7 案例1

7.1 案例

 计算函数的最小值，其中个体x的维数n= 10。 这是一个简单的平方和函数，只有一个极小点x=(0, 0, …0)， 理论最小值f(0，0, .，. 0)=0

7.2 Python实现 

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
import matplotlib; matplotlib.use('TkAgg')
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
mpl.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题#=================初始化参数===============
D=10                           #变量维数
Xs=20                          #上限
Xx=-20                         #下限
#====冷却表参数====
L = 200                       #马可夫链长度 #在温度为t情况下的迭代次数
K = 0.998                     #衰减参数
S = 0.01                      #步长因子
T=100                         #初始温度
YZ = 1e-7                     #容差
P = 0                         #Metropolis过程中总接受点
#====随机选点初值设定====
PreX = np.random.uniform(size=(D,1))*(Xs-Xx)+Xx
PreBestX = PreX    #t-1代的全局最优X
PreX =  np.random.uniform(size=(D,1))*(Xs-Xx)+Xx
BestX = PreX      #t时刻的全局最优X#==============目标函数=============
def func1(x):return np.sum([i**2 for i in x])#====每迭代一次退火一次(降温), 直到满足迭代条件为止===
deta=np.abs(func1(BestX)-func1(PreBestX))   #前后能量差trace=[]    #记录
while (deta > YZ) and (T>0.1):    #如果能量差大于允许能量差 或者温度大于阈值T = K * T   #降温print(T)#===在当前温度T下迭代次数====for i in range(L):##====在此点附近随机选下一点=====NextX = PreX + S * (np.random.uniform(size=(D, 1)) * (Xs - Xx) + Xx)#===边界条件处理for ii in range(D):    #遍历每一个维度while NextX[ii]>Xs or NextX[ii]<Xx:NextX[ii]=PreX[ii] + S* (np.random.random() *(Xs-Xx)+Xx)#===是否全局最优解 ===if (func1(BestX) > func1(NextX)):#保留上一个最优解PreBestX = BestX#此为新的最优解BestX = NextX#====Metropolis过程====if (func1(PreX) - func1(NextX) > 0):  #后一个比前一个好#接受新解PreX = NextXP = P + 1else:changer = -1 * (func1(NextX) - func1(PreX)) / Tp1 = np.exp(changer)#接受较差的解if p1 > np.random.random():PreX = NextXP = P + 1trace.append(func1(BestX))deta = np.abs(func1(BestX)- func1(PreBestX)) #修改前后能量差print('最小值点\n',BestX)
print('最小值\n',func1(BestX))
plt.plot(trace,label='迭代曲线')
plt.xlabel('迭代次数')
plt.ylabel('目标函数值')
plt.show()

7.3 结果 

最小值点[[ 0.01025158][ 0.05412669][ 0.01478472][ 0.11712758][-0.0201138 ][ 0.10935337][-0.01210524][-0.06925395][ 0.06425366][ 0.06373066]]
最小值0.042467753287183725Process finished with exit code 0

8 案例2 

8.1 案例

8.2 Python实现 

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
import matplotlib; matplotlib.use('TkAgg')
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
mpl.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题#=================初始化参数============
D=2                           #变量维数 ,对应x,y
Xs=1                          #搜索区间上限
Xx=-1                         #搜索区间下限
#==冷却表参数==
L = 300                       #马可夫链长度 #在温度为t情况下的迭代次数
K = 0.98                     #衰减参数
S = 0.01                      #步长因子
T=100                         #初始温度
YZ = 1e-8                     #容差(运行t-1,，t时刻的误差）
P = 0                         #Metropolis过程中总接受点
eloss=0.1                     #允许的惩罚项误差
#====随机选点 初值设定====
PreX = np.zeros(shape=(D,1))
PreX[0]=np.random.uniform(1,2,1)#X范围【1,2】
PreX[1]=np.random.uniform(-1,0,1)#y范围【-1,0】
PreBestX = PreX#t-1代的全局最优XPreX = np.zeros(shape=(D,1))
PreX[0]=np.random.uniform(1,2,1)#X范围【1,2】
PreX[1]=np.random.uniform(-1,0,1)#y范围【-1,0】
BestX = PreX#t时刻的全局最优X#==============目标函数=============
def func1(X):A = 10pi = np.pix = X[0]y = X[1]return 2 * A + x ** 2 - A * np.cos(2 * pi * x) + y ** 2 - A * np.cos(2 * pi * y)
#==========惩罚项===========
def calc_e(X):"""计算个体的目惩罚项，X 的维度是 size * 2 """ee = 0"""计算第一个约束的惩罚项"""e1 = X[0] + X[1] - 6ee += max(0, e1)"""计算第二个约束的惩罚项"""e2 = 3 * X[0] - 2 * X[1] - 5ee += max(0, e2)return ee#====每迭代一次退火一次(降温), 直到满足迭代条件为止===
deta=np.abs(func1(BestX)-func1(PreBestX))#前后能量差trace=[]#记录
while (deta > YZ) and (T>0.1):#如果能量差大于允许能量差 或者温度大于阈值T = K * T#降温print(T)# =在当前温度T下迭代次数=for i in range(L):  ## =在此点附近随机选下一点==NextX = PreX + S * (np.random.uniform(size=(D, 1)) * (Xs - Xx) + Xx)# ===边界条件处理while NextX[0] > 2 or NextX[0] < 1:#x属于【1,2】NextX[0] =PreX[0] + S* (np.random.uniform() * (Xs - Xx) + Xx)while NextX[1] > 0 or NextX[0] < -1:  # y属于【-1,0】NextX[1] = PreX[1] + S* (np.random.uniform() * (Xs - Xx) + Xx)# ===是否全局最优解 ===if (func1(BestX) > func1(NextX)) and (calc_e(BestX)<eloss) and (calc_e(NextX)<eloss):#两者都没有违反约束，下一代适应度更好时选下一代# 保留上一个最优解PreBestX = BestX# 此为新的最优解BestX = NextXelif (calc_e(BestX)>eloss) and (calc_e(NextX)>eloss) and (func1(BestX) > func1(NextX)):#两者都违反约束，下一代适应度更好时（选下一代）# 保留上一个最优解PreBestX = BestX# 此为新的最优解BestX = NextXelif (calc_e(BestX)>eloss) and (calc_e(NextX)<eloss) :#上一代惩罚项不满足约束，下一代惩罚项满足约束（选下一代）# 保留上一个最优解PreBestX = BestX# 此为新的最优解BestX = NextX# ====Metropolis过程  当代温度T 前后个体判断===if (func1(PreX) - func1(NextX) > 0) and (calc_e(PreX)<eloss) and(calc_e(NextX)<eloss) :  # 两个惩罚项都满足约束，后一个的适应度更小（选后一个）# 接受新解PreX = NextXP = P + 1elif  (calc_e(PreX)>eloss) and(calc_e(NextX)>eloss) and (func1(PreX) - func1(NextX) > 0) :#两个惩罚项都不满足时，后一个适应度比前一个小（选后一个）# 接受新解PreX = NextXP = P + 1elif (calc_e(PreX)>eloss) and(calc_e(NextX)<eloss) :#前一个惩罚项不满足，后一个满足（选后一个）# 接受新解PreX = NextXP = P + 1else:changer = -1 * (func1(NextX) - func1(PreX)) / Tp1 = np.exp(changer)# 接受较差的解if p1 > np.random.random():PreX = NextXP = P + 1trace.append(func1(BestX))deta = np.abs(func1(BestX) - func1(PreBestX))  # 修改前后能量差print('最优值X\n',BestX)
print('最优目标函数值\n',func1(BestX))
print('最优值对应的惩罚项',calc_e(BestX))
plt.plot(trace,label='迭代曲线')
plt.xlabel('迭代次数')
plt.ylabel('目标函数值')
plt.show()

8.3 结果 

98.0
96.03999999999999
94.11919999999999
92.23681599999999
90.39207968
88.58423808639999
86.812553324672
85.07630225817856
83.37477621301498
81.70728068875468
80.07313507497959
78.47167237347999
76.90223892601038
75.36419414749018
73.85691026454037
72.37977205924956
70.93217661806457
69.51353308570329
68.12326242398922
66.76079717550944
65.42558123199925
64.11706960735926
62.83472821521207
61.57803365090783
60.34647297788967
59.13954351833188
57.95675264796524
56.79761759500593
55.66166524310581
54.54843193824369
53.45746329947881
52.38831403348923
51.34054775281945
50.313736797763056
49.3074620618078
48.32131282057164
47.35488656416021
46.407788832877
45.47963305621946
44.57004039509507
43.67863958719317
42.80506679544931
41.94896545954032
41.10998615034951
40.287786427342525
39.482030698795676
38.69239008481976
37.918542283123365
37.160171437460896
36.41696800871168
35.688628648537446
34.9748560755667
34.27535895405536
33.58985177497426
32.91805473947477
32.25969364468527
31.614499771791564
30.98220977635573
30.362565580828615
29.755314269212043
29.160207983827803
28.577003824151248
28.005463747668223
27.445354472714858
26.89644738326056
26.35851843559535
25.831348066883443
25.314721105545775
24.80842668343486
24.312258149766162
23.826012986770838
23.349492727035422
22.88250287249471
22.42485281504482
21.97635575874392
21.53682864356904
21.10609207069766
20.683970229283705
20.27029082469803
19.86488500820407
19.467587308039988
19.07823556187919
18.696670850641606
18.322737433628774
17.956282684956197
17.597157031257073
17.24521389063193
16.900309612819292
16.562303420562905
16.231057352151648
15.906436205108616
15.588307481006444
15.276541331386316
14.971010504758588
14.671590294663416
14.378158488770147
14.090595318994744
13.808783412614849
13.532607744362553
13.261955589475301
12.996716477685794
12.736782148132079
12.482046505169437
12.232405575066048
11.987757463564726
11.748002314293432
11.513042268007563
11.282781422647412
11.057125794194464
10.835983278310575
10.619263612744364
10.406878340489476
10.198740773679686
9.994765958206093
9.79487063904197
9.598973226261132
9.406993761735908
9.21885388650119
9.034476808771165
8.853787272595742
8.676711527143826
8.50317729660095
8.33311375066893
8.166451475655553
8.003122446142442
7.8430599972195925
7.686198797275201
7.532474821329696
7.381825324903103
7.23418881840504
7.089505042036939
6.9477149411962005
6.808760642372277
6.672585429524831
6.539133720934334
6.408351046515647
6.280184025585334
6.154580345073628
6.031488738172155
5.910858963408712
5.792641784140538
5.676788948457727
5.563253169488572
5.451988106098801
5.342948343976825
5.236089377097288
5.131367589555342
5.028740237764235
4.92816543300895
4.829602124348772
4.733010081861796
4.63834988022456
4.545582882620068
4.454671224967667
4.365577800468314
4.278266244458948
4.192700919569768
4.108846901178373
4.026669963154805
3.9461365638917085
3.8672138326138743
3.7898695559615967
3.714072164842365
3.6397907215455176
3.566994907114607
3.495655008972315
3.425741908792869
3.3572270706170113
3.290082529204671
3.224280878620578
3.159795261048166
3.0965993558272027
3.0346673687106587
2.9739740213364456
2.9144945409097165
2.856204650091522
2.7990805570896913
2.7430989459478976
2.6882369670289394
2.6344722276883608
2.5817827831345936
2.530147127471902
2.4795441849224638
2.4299533012240144
2.381354235199534
2.3337271504955432
2.2870526074856325
2.24131155533592
2.1964853242292017
2.1525556177446177
2.1095045053897254
2.0673144152819307
2.025968126976292
1.985448764436766
1.9457397891480306
1.9068249933650698
1.8686884934977683
1.831314723627813
1.7946884291552565
1.7587946605721514
1.7236187673607084
1.6891463920134941
1.6553634641732242
1.6222561948897598
1.5898110709919646
1.5580148495721253
1.5268545525806827
1.496317461529069
1.4663911122984876
1.4370632900525178
1.4083220242514674
1.3801555837664379
1.352552472091109
1.325501422649287
1.2989913941963012
1.273011566312375
1.2475513349861276
1.222600308286405
1.198148302120677
1.1741853360782633
1.150701629356698
1.127687596769564
1.1051338448341728
1.0830311679374893
1.0613705445787396
1.0401431336871647
1.0193402710134214
0.9989534655931529
0.9789743962812898
0.959394908355664
0.9402070101885507
0.9214028699847796
0.9029748125850839
0.8849153163333823
0.8672170100067146
0.8498726698065803
0.8328752164104487
0.8162177120822397
0.7998933578405949
0.783895490683783
0.7682175808701073
0.7528532292527051
0.7377961646676511
0.723040241374298
0.708579436546812
0.6944078478158757
0.6805196908595582
0.666909297042367
0.6535711111015197
0.6404996888794893
0.6276896951018994
0.6151359011998614
0.6028331831758642
0.5907765195123469
0.5789609891220999
0.5673817693396579
0.5560341339528647
0.5449134512738074
0.5340151822483312
0.5233348786033646
0.5128681810312973
0.5026108174106714
0.4925586010624579
0.4827074290412087
0.47305328046038453
0.46359221485117685
0.4543203705541533
0.44523396314307023
0.4363292838802088
0.4276026982026046
0.4190506442385525
0.41066963135378143
0.4024562387267058
0.39440711395217165
0.3865189716731282
0.37878859223966566
0.37121282039487236
0.3637885639869749
0.3565127927072354
0.3493825368530907
0.34239488611602886
0.3355469883937083
0.3288360486258341
0.3222593276533174
0.315814141100251
0.309497858278246
0.3033079011126811
0.29724174309042745
0.29129690822861887
0.2854709700640465
0.27976155066276553
0.2741663196495102
0.26868299325652
0.2633093333913896
0.2580431467235618
0.25288228378909056
0.24782463811330874
0.24286814535104256
0.2380107824440217
0.23325056679514128
0.22858555545923845
0.22401384435005367
0.21953356746305258
0.21514289611379153
0.2108400381915157
0.20662323742768537
0.20249077267913165
0.19844095722554903
0.19447213808103805
0.1905826953194173
0.18677104141302894
0.18303562058476835
0.17937490817307297
0.1757874100096115
0.17227166180941927
0.16882622857323087
0.16544970400176626
0.16214070992173094
0.15889789572329632
0.1557199378088304
0.15260553905265378
0.1495534282716007
0.14656235970616868
0.1436311125120453
0.1407584902618044
0.13794332045656832
0.13518445404743695
0.13248076496648822
0.12983114966715845
0.12723452667381527
0.12468983614033896
0.12219603941753218
0.11975211862918153
0.1173570762565979
0.11500993473146594
0.11270973603683662
0.11045554131609989
0.10824643048977789
0.10608150187998233
0.10395987184238269
0.10188067440553503
0.09984306091742433最优值X[[ 1.00003199][-0.99454067]]
最优目标函数值[1.99505787]
最优值对应的惩罚项 0Process finished with exit code 0