-
-
算法介紹
-
模擬退火算法（SA）是一種模擬物理退火過程而設(shè)計的優(yōu)化算法。
它的基本思想最早在1953年就被Metropolis提出，但直到1983年，Kirkpatrick等人才設(shè)計出真正意義上的模擬退火算法并進(jìn)行應(yīng)用。
模擬退火算法采用類似于物理退火的過程。先在一個高溫狀態(tài)下，然后逐漸退火，在每個溫度下慢慢冷卻，最終達(dá)到物理基態(tài)（相當(dāng)于算法找到最優(yōu)解）。
-
-
算法應(yīng)用
-
求解TSP問題、求最值、全局優(yōu)化、生產(chǎn)調(diào)度、控制工程、機器學(xué)習(xí)、信號處理等問題。
-
-
算法特性
-
模擬退火算法源于對固體退火過程的模擬，采用Metropolis準(zhǔn)則，并用一組稱為冷卻進(jìn)度表的參數(shù)控制算法的進(jìn)程，使得算法在多項式時間里可以給出一個近似最優(yōu)解。
模擬退火算法在某一初溫下，伴隨溫數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解。即在局部最優(yōu)解的空間內(nèi)能概率性地跳出并最終趨于全局最優(yōu)。（不在局限于局部最優(yōu)）
-
-
算法名詞解釋
-
退火：將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)，保持足夠的時間，然后以適宜的速度逐步降溫。使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到內(nèi)能最小的穩(wěn)定狀態(tài)。（加溫—等溫—冷卻）
-
-
-
退火過程：
-
-
1、在初始狀態(tài)，固體內(nèi)部的粒子存在非均勻狀態(tài)。
2、加熱到一定溫度，增強其粒子的熱運動，使粒子偏離其平衡位置，消除原來的非均勻狀態(tài)。
3、讓溫度慢慢降低，達(dá)到熱平衡狀態(tài)，粒子逐漸均勻有序，最終達(dá)到內(nèi)能最小的狀態(tài)。
-
-
算法步驟
-
1.設(shè)定當(dāng)前解（即為當(dāng)前的最優(yōu)解）：令T=
?，即開始退火的初始溫度，隨機生成一個初始解
?，并計算相應(yīng)的目標(biāo)函數(shù)值E(
?)。
2.產(chǎn)生新解與當(dāng)前解差值：根據(jù)當(dāng)前解
進(jìn)行擾動，產(chǎn)生一個新解?
,計算相應(yīng)的目標(biāo)函數(shù)值E(
?),得到????=??(
?)???(
?)。
3.判斷新解是否被接受：若????<??，則新解
?被接受；若????>??，則新解
?按概率
接受，?
為當(dāng)前溫度。
4.當(dāng)新解被確定接受時：新解
?被作為當(dāng)前解。
5.循環(huán)以上四個步驟：在溫度
?下，重復(fù)k次的擾動和接受過程，接著執(zhí)行下一步驟。
6.最后找到全局最優(yōu)解：判斷T是否已經(jīng)達(dá)到終止溫度?
，是，則終止算法；否，則轉(zhuǎn)到循環(huán)步驟繼續(xù)執(zhí)行。
-
-
-
冷卻進(jìn)度表
-
-
退火過程由一組初始參數(shù)，即冷卻進(jìn)度表控制。它的目的是盡量使系統(tǒng)達(dá)到平衡，以使算法在有限的時間內(nèi)逼近最優(yōu)解。
冷卻進(jìn)度表包括：
1.控制溫度參數(shù)的初值T0
2.控制溫度T的衰減函數(shù)(溫度的更新)
3.馬爾科夫鏈的的長度Lk（迭代次數(shù)）
4.控制參數(shù)T的終值(停止準(zhǔn)則)
| 組合優(yōu)化問題 |
金屬物體 |
| 解 |
粒子狀態(tài) |
| 最優(yōu)解 |
能量最低的狀態(tài) |
| 設(shè)定初溫 |
熔解過程 |
| Metropolis接受過程 |
等溫過程 |
| 控制參數(shù)的下降 |
冷卻 |
| 目標(biāo)函數(shù) |
能量 |
-
-
模擬退火算法的優(yōu)缺點
-
優(yōu)點：
高效地求解NP完全問題（如TSP問題，0-1背包問題等）。
相較于其他非線性與優(yōu)化算法，模擬退火算法編程工作量小且易于實現(xiàn)。
缺點：
使用不當(dāng)，可能會陷入局部最優(yōu)
參數(shù)難以控制，所得結(jié)果可能為接近最優(yōu)解但并非最優(yōu)解。
-
-
案例1：求解TSP問題
-
問題描述：現(xiàn)有34個城市，已知其坐標(biāo)；從其中某一城市作為起點出發(fā)，途徑其他的所有城市，然后回到起點，要求走過的距離最短。
?結(jié)果如下所示：
文章來源：http://www.zghlxwxcb.cn/news/detail-797944.html
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-797944.html
到了這里，關(guān)于數(shù)學(xué)建模之模擬退火法（SA）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
