劉建華模擬退火算法的改進.doc

《劉建華模擬退火算法的改進.doc》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、模擬退火算法　　模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當前解重復“產生新解→計算目標函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終

2、止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個t值時的迭代次數(shù)L和停止條件S。模擬退火算法的模型　　模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分?！∧M退火的基本思想:　　(1)初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點)，每個T值的迭代次數(shù)L　　(2)對k=1，……，L做第(3)至第6步：　　(3)產生新解S′　　(4)計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù)　　(5)若Δt′<0則接受S′作為新的當前解

3、，否則以概率exp(-Δt′/T)接受S′作為新的當前解.　　(6)如果滿足終止條件則輸出當前解作為最優(yōu)解，結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。　　(7)T逐漸減少，且T->0，然后轉第2步。模擬退火算法新解的產生和接受可分為如下四個步驟：　　第一步是由一個產生函數(shù)從當前解產生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。　　第二步是計算與新解所對應的目標函數(shù)差。因為

4、目標函數(shù)差僅由變換部分產生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。　　第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropo1is準則:若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S?！　〉谒牟绞钱斝陆獗淮_定接受時，用新解代替當前解，這只需將當前解中對應于產生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代?？稍诖嘶A上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續(xù)下一輪試驗。　　模擬退火算法與初始值無關，算

5、法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。模擬退火算法的改進在確保一定要求的優(yōu)化質量基礎上,提高模擬退火的搜索效率(時間性能),是對SA算法進行改進的主要內容.可行的方案包括:(1)設計合適的狀態(tài)產生函數(shù),使其根據(jù)搜索進程的需要表現(xiàn)出狀態(tài)的全空間分散性或局部區(qū)域性.(2)設計高效的退火歷程.(1)避免狀態(tài)的迂回搜索(2)采用并行搜索結構.(3)為避免陷入局部極小,改進對溫度的控制方式.(4)選擇合適的初始狀態(tài).(5)設計合適的算法終止準則.此外,對模擬退火算法的改進,也

6、可通過增加某些環(huán)節(jié)而實現(xiàn).主要的改進方式包括:(1)增加升溫或重升溫過程.在算法進程的適當時機,將溫度適當提高,從而可激活各狀態(tài)的接受概率,以調整搜索進程中的當前狀態(tài),避免算法在局部極小解處停滯不前.(2)增加記憶功能.為避免搜索進程中由于執(zhí)行概率接受環(huán)節(jié)而遺失當前遇到的最優(yōu)解,可通過增加存儲環(huán)節(jié),將”BestSoFar”的狀態(tài)記憶下來.(3)增加補充搜索進程.即在退火進程結束后,以搜索到的最優(yōu)解為初始狀態(tài),再次執(zhí)行模擬退火過程或局部趨化性搜索.(4)對每一當前狀態(tài),采用多次搜索策略,以概率接受區(qū)域內的最優(yōu)狀態(tài),而非標準SA的單次比較方式.(5)結合其他搜索機制的算法,如遺傳算法,混沌搜索

7、等.(6)上述各方法的綜合應用.下面介紹一種對退火過程和抽樣過程進行修改的兩階段改進策略.熟知，模擬退火算法在局部極小解處有機會跳出并最終趨于全局最優(yōu)的根本原因是算法通過概率判斷來接受新狀態(tài)，這在理論上了已得到嚴格證明，即當初溫充分高，降溫足夠慢，每一溫度下抽樣足夠長，最終溫度趨于零時，算法最終以概率1收斂到時全局最優(yōu)解。但由于全局收斂條件難以實現(xiàn)，并且“概率接受”使得當前狀態(tài)可能比搜索軌跡中的某些中間狀態(tài)要差，從而實際