數(shù)學(xué)建模--智能優(yōu)化算法--模擬退火理論
本文章作者為上帝果凍(e小白網(wǎng)站用戶名和b站up主名?)。e小白網(wǎng)址:www.e-xiaobai.com
0 前言
? ?本文重點討論模擬退火算法的簡單應(yīng)用，對理論僅進行一些簡單介紹，本文對算法的實現(xiàn)使用python語言。前面簡介偏理論，如果不感興趣可以直接跳轉(zhuǎn)到代碼和流程部分。
1 模擬退火算法簡介
? ?模擬退火算法（Simulated Annealing,SA）是一種全局搜索算法。其理論來自于物理退火過程，物理退火分為三個部分“升溫過程”，“降溫過程”和“等溫過程”.
1.1 升溫過程
? ?升溫過程，在物理過程中是將固體加熱到液體狀態(tài)，打破固體中可能的非均勻狀態(tài)，使得它降溫后可以建立起新的平衡。過渡到數(shù)學(xué)模型中，也就是打破當(dāng)前這個非最優(yōu)解的狀態(tài)，使得它在降溫過程中可以逐步趨向最優(yōu)解。
1.2 降溫過程
? ?降溫過程，是使得高溫液體逐步趨向低溫狀態(tài)從而達到新的有序狀態(tài)（目標(biāo)是希望新狀態(tài)的固體是均勻的），如果降溫過程太快會導(dǎo)致只能冷凝成非均勻狀態(tài)的亞穩(wěn)態(tài)。過渡到數(shù)學(xué)中就是降溫過程是希望非最優(yōu)解能夠最終降到最優(yōu)狀態(tài)，而降溫速度過快，會導(dǎo)致得出的解仍然是局部最優(yōu)解或者就是一個劣解。
1.3 等溫狀態(tài)
? ?該過程保證了在每個溫度下都能達到平衡。這個的數(shù)學(xué)概念和算法設(shè)計稍后再談。
? ?在模擬退火算法中需要引入組合優(yōu)化方法中的Metropolis準(zhǔn)則，這個準(zhǔn)則保證了算法具有全局搜索能力，即在一定的概率上接受一個比當(dāng)前解要差的解，從而提高尋找到更優(yōu)解的可能性。
1.4 Metropolis準(zhǔn)則(物理學(xué)描述)
? ?假設(shè)熱力學(xué)系統(tǒng)S有n個離散狀態(tài)，其中i狀態(tài)的能量為。假設(shè)在溫度下達到熱平衡，此時狀態(tài)i的概率為其中C為已知參數(shù)；exp()為一自然常數(shù)e為底的指數(shù)函數(shù)。根據(jù)公式可以知道在同一個溫度下，能量低的概率是大于能量高的概率的。
1.4 Metropolis準(zhǔn)則(數(shù)學(xué)描述)
? 在同一個參數(shù)T下，如果解X1對應(yīng)的適應(yīng)度函數(shù)值F(X1)<F(X0),X0為初始解，則接受X1作為新的解，否則以概率exp(-(F(X1)-F(X0))/T)來接受X1作為新的解。其中以概率接受的方法可以使用隨機數(shù)的方式實現(xiàn)。
2 模擬退火算法流程及簡單應(yīng)用
2.1 算法流程（不包含等溫過程）
STEP 1 ：設(shè)置適應(yīng)度函數(shù)，初始溫度，終止溫度，初始解
STEP 2 ：循環(huán)，在當(dāng)前溫度下根據(jù)初始解在一定的范圍內(nèi)隨機產(chǎn)生新的解，并根據(jù)Metropolis準(zhǔn)則判斷是否接受新的解。判斷是否終止循環(huán)，如果終止輸出解，否則進行降溫。
2.2 簡單應(yīng)用
求解f(x) = x^2 的最小值點。
import numpy as np
#定義適應(yīng)度函數(shù)
def fun(x):
? ? y = x**2
? ? return y
#設(shè)置初始變量
T = 100? ???# 初始溫度
a = 0.99? ? # 溫度變化率
t = 1? ?? ? # 終止溫度
x0 = np.random.uniform(-10,10,1) # 產(chǎn)生初始解
#執(zhí)行退火流程
while T>t:
? ? # 根據(jù)初始解在一定范圍內(nèi)產(chǎn)生新解
? ? x1 = x0 + np.random.uniform(-1,1)
? ? # 計算新解和初始解的差值
? ? df = fun(x1)-fun(x0)
? ? # 執(zhí)行Metropolis準(zhǔn)則
? ? if df<0:
? ?? ???x0 = x1
? ? elif np.random.rand()< np.exp(-df/T):
? ?? ???x0 = x1
? ? # 進行降溫
? ? T *= a
print(x0)
試驗結(jié)果為：?[0.15110473]，與真實結(jié)果0相比已經(jīng)十分精確了。
注：退火算法每次計算的結(jié)果不一定相同，也不一定都可以收斂到最優(yōu)解處。所以應(yīng)該多使用幾次較好。
由于篇幅問題，文章部分內(nèi)容省略。詳細內(nèi)容可在e小白網(wǎng)站(www.e-xiaobai.com)進行查看。
【版權(quán)聲明：本文為e小白網(wǎng)站www.e-xiaobai.com的原創(chuàng)作品，需經(jīng)e小白網(wǎng)站或作者本人同意許可后，方可轉(zhuǎn)發(fā)到其它網(wǎng)站平臺上，否則我們有保留追究法律責(zé)任的權(quán)利】
