解读最优化算法之模拟退火
模拟退火算法
模拟退火算法 ( simulated anneal , SA) 求解最优化问题常用的算法，今天应用 SA 解决一元多次函数最小值的例子解释 SA 算法。
1 算法思想
- 初始化：初始温度T，初始解状态S，是算法迭代的起点；
- 产生新解S′
- 计算增量ΔT = C(S′,S)，其中C为评价函数： 若ΔT < 0，则接受 S′ 作为新的当前解， 否则以概率 exp(-ΔT/kT) 接受 S′ 作为新的当前解
- 如果满足终止条件则输出当前解作为最优解，结束程序，终止条件通常取为连续若干个新解都没有被接受时终止算法。
上述关键点：以一定概率exp(-ΔT/kT) 接受一个不好的解，这是SA区别于爬山算法的地方。
2 SA 算法应用
应用 模拟退火SA 算法求解以下函数的最小值：
y = np.sin(5np.pi(x-0.05)) + np.cos(np.pi*(x-0.04)), 0<x<1
先plot 下函数：
这是有意选取的一个多峰值函数，观察SA算法是否陷入局部极小；爬山算法是怎么陷入局部极小的，SA又是怎么跳出局部极小的。
3 SA 算法代码
代码详细解释 sa函数的参数 y 代表 一元多次函数，后面3个为算法的调节参数，break_cond是连续多少次没有搜索到好解时的跳出条件, k 控制选择概率，step是迭代时步的控制参数。T,T_max 是解空间的取值范围，i 是迭代次数，best是初始最优解，设为在 T处，break_i是控制跳出的次数，每当取到最优解则置为0. 评价函数选用min(s,s').
以下两行是展示搜索过程的代码，不是算法的代码。
save_list.append([T, y(T)])
print('step = %d, T = %f, y = %f' % (i, T, y(T)))
1def sa(y, break_cond = 30,k=10,step=0.005):
2 T, T_max = 1e-3, 1.0
3 k = 10
4 i = 0
5 best = y(T)
6 break_i = 0
7 while T_max > T:
8 T += step
9 de = y(T) - y(T-step)
10 if de < 0:
11 best = min(best, y(T))
12 break_i = 0
13 else:
14 if np.exp(-de / (k*T)) > np.random.random
15
16(1): # 以一定概率接受不好的解
17 best = min(best, y(T))
18 break_i = 0
19 break_i += 1
20 if break_i > break_cond: # 如果连续找不到
21
22好解
23 break
24 i += 1
25 save_list.append([T, y(T)])
26 print('step = %d, T = %f, y = %f' % (i, T, y
27
28(T)))
29
30 return best4 SA 搜索模拟
为了更清楚的展示SA搜索的过程，制作搜素动画。
1import matplotlib.pyplot as plt
2import numpy as np
3import matplotlib.animation as animation
4
5def f(x):
6 y = np.sin(5*np.pi*(x-0.05)) + np.cos(np.pi*(x-0.04))
7 return y
8
9save_list = []
10
11
12def sa(y, break_cond = 30):
13 T, T_max = 1e-3, 1.0
14 k = 10
15 i = 0
16 best = y(T)
17 break_i = 0
18 while T_max > T:
19 T += 0.005
20 de = y(T) - y(T-0.01)
21 if de < 0:
22 best = min(best, y(T))
23 break_i = 0
24 else:
25 if np.exp(-de / (k*T)) > np.random.random(1): # 以一定概率接受不好的解
26 best = min(best, y(T))
27 break_i = 0
28 break_i += 1
29 if break_i > break_cond: # 如果连续找不到好解
30 break
31 i += 1
32 save_list.append([T, y(T)])
33 print('step = %d, T = %f, y = %f' % (i, T, y(T)))
34
35 return best
36
37# 模拟退火， 打印结果
38print (sa(f))
39
40fig = plt.figure()
41wind = fig.add_subplot(111)
42x = np.linspace(0, 1, 200)
43wind.plot(x, f(x))
44
45def update(data):
46 wind.scatter(data[0], data[1])
47 return
48
49ani = animation.FuncAnimation(fig, update, save_list, interval= 200)
50plt.show()通过动画可以看出，应用SA算法，搜索时可以成功跳出局部极小点，并且成功找到最小值大约为 -1.6.
5 爬山算法搜索模拟
这主要得益于SA以一定概率接收不好的解，如果标注这部分，可以认为为爬山算法。再看下，爬山算法的搜索过程，陷入局部最小，搜索提前终止，所能找到的最小值为-0.5.
6 总结
因此，同等条件下，SA算法更有可能不会陷入局部最小值，进而找到全局最值。