「最優化算法」解讀最優化算法之模擬退火

2018

06

21

模擬退火算法

模擬退火算法 ( simulated anneal , SA) 求解最優化問題常用的算法，今天應用 SA 解決一元多次函數最小值的例子解釋 SA 算法。

1 算法思想

1. 初始化：初始溫度T，初始解狀態S，是算法迭代的起點；
2. 產生新解S′
3. 計算增量ΔT = C(S′,S)，其中C為評價函數：
4. 若ΔT < 0，則接受 S′ 作為新的當前解，
5. 否則以概率 exp(-ΔT/kT) 接受 S′ 作為新的當前解
6. 如果滿足終止條件則輸出當前解作為最優解，結束程序，終止條件通常取為連續若干個新解都沒有被接受時終止算法。

上述關鍵點：以一定概率exp(-ΔT/kT) 接受一個不好的解，這是SA區別於爬山算法的地方。

2 SA 算法應用

應用 模擬退火SA 算法求解以下函數的最小值：

y = np.sin(5np.pi(x-0.05)) + np.cos(np.pi*(x-0.04)), 0

先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)))

閱讀更多 人工智能channel 的文章

關鍵字: 算法 最優化 終止