物料退火算法的專題介紹
摘要：物料退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，使用加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，使用退火爐常溫時達到基態(tài)，內(nèi)能減為最小。
物料退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，使用加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，使用退火爐常溫時達到基態(tài)，內(nèi)能減為最小。
根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中e為溫度T時
的內(nèi)能，ΔE為其改變量,k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(Cooling Schedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。
起源
模擬退火算法起源于物理退火。
物理退火過程：
⑴ 加溫過程
⑵ 等溫過程
⑶ 冷卻過程
模型建立
模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。
模擬退火的基本思想：
⑴ 初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點）， 每個T值的迭代次數(shù)L
⑵ 對k=1,……,L做第⑶至第6步：
⑶ 產(chǎn)生新解S′
⑷ 計算增量Δt′=C(S′）-C(S)，其中C(S)為評價函數(shù)
⑸ 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解.
⑹ 如果滿足終止條件則輸出當前解作為最優(yōu)解，結(jié)束程序。
終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。
⑺ T逐漸減少，且T->0,然后轉(zhuǎn)第2步。
算法步驟
模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：
第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當前新解的鄰域結(jié)構，因而對冷卻進度表的選取有一定的影響。
第二步是計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。
第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropolis接受準則： 若Δt′<0則接受S′作為新的當前解S,否則以概率exp(-Δt′/T)接受S′作為新的當前解S。
第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代�？稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。
注意事項
模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài)S（是算法迭代的起點）無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。
作為模擬退火算法應用，討論旅行商問題(Travelling Salesman Problem,簡記為TSP)：設有n個城市，用數(shù)碼1,…,n代表。城市i和城市j之間的距離為d(i,j) i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短.。
TSP的模擬退火算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有回路，是{1,……,n}的所有循環(huán)排列的集合,S中的成員記為(w1,w2,……,wn)，并記wn+1= w1。初始解可選為(1,……,n)
目標函數(shù) 此時的目標函數(shù)即為訪問所有城市的路徑總長度或稱為代價函數(shù)：
我們要求此代價函數(shù)的最小值。
新解的產(chǎn)生 隨機產(chǎn)生1和n之間的兩相異數(shù)k和m,
若k
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變?yōu)椋?/div>
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變?yōu)椋?/div>
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。
也可以采用其他的變換方法，有些變換有獨特的優(yōu)越性，有時也將它們交替使用，得到一種更好方法。
代價函數(shù)差 設將(w1,w2,……,wn)變換為(u1,u2,……,un)，則代價函數(shù)差為：
根據(jù)上述分析，可寫出用模擬退火算法求解TSP問題的偽程序：
Procedure TSPSA:
begin
init-of-T; { T為初始溫度}
S={1,……,n}; {S為初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 從當前回路S產(chǎn)生新回路S′}
Δt:=f(S′））-f(S);{f(S)為路徑總長}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模擬退火算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調(diào)度問題(Scheduling Problem)等等。
參數(shù)控制
模擬退火算法的應用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點：
⑴ 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結(jié)果進行若干次調(diào)整。
⑵ 退火速度問題。
模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質(zhì)和特征設置合理的退火平衡條件。
⑶ 溫度管理問題。
溫度管理問題也是模擬退火算法難以處理的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用如下所示的降溫方式：
T(t+1)=k×T(t)
式中k為正的略小于1.00的常數(shù),t為降溫的次數(shù)
優(yōu)缺點及改良方式
優(yōu)點：計算過程簡單，通用，魯棒性強，適用于并行處理，可用于求解復雜的非線性優(yōu)化問題。
缺點：收斂速度慢，執(zhí)行時間長，算法性能與初始值有關及參數(shù)敏感等缺點。
經(jīng)典模擬退火算法的缺點：
⑴如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；
⑵如果降溫過程過快，很可能得不到全局最優(yōu)解。
模擬退火算法的改進
⑴ 設計合適的狀態(tài)產(chǎn)生函數(shù)，使其根據(jù)搜索進程的需要
表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性。
⑵ 設計高效的退火策略。
⑶ 避免狀態(tài)的迂回搜索。
⑷ 采用并行搜索結(jié)構。
⑸ 為避免陷入局部極小，改進對溫度的控制方式
⑹ 選擇合適的初始狀態(tài)。
⑺ 設計合適的算法終止準則。
也可通過增加某些環(huán)節(jié)而實現(xiàn)對模擬退火算法的改進。
主要的改進方式包括：
⑴ 增加升溫或重升溫過程。在算法進程的適當時機，將 電子散熱器的溫度適當提高，從而可激活各狀態(tài)的接受概率，以調(diào)整搜索進程中的當前狀態(tài)，避免算法在局部極小解處停滯不前。 ⑵ 增加記憶功能。為避免搜索過程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當前遇到的最優(yōu)解，可通過增加存儲環(huán)節(jié)，將一些在這之前好的態(tài)記憶下來。
⑶ 增加補充搜索過程。即在退火過程結(jié)束后，以搜索到的最優(yōu)解為初始狀態(tài)，再次執(zhí)行模擬退火過程或局部性搜索。
⑷ 對每一當前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)，而非標準SA的單次比較方式。
⑸ 結(jié)合其他搜索機制的算法，如遺傳算法、混沌搜索等。
⑹上述各方法的綜合應用。
相關新聞
相關產(chǎn)品
|
