基于模擬退火算法的改進型退火策略研究

寧德圣， 曾 光， 雷 莉， 許 曦

(東華理工大學理學院，江西 南昌 330013)

?

基于模擬退火算法的改進型退火策略研究

寧德圣， 曾 光， 雷 莉， 許 曦

(東華理工大學理學院，江西 南昌 330013)

研究模擬退火算法中的降溫策略，將一種類似于多普勒效應(yīng)型溫度遞減曲線作為退火降溫曲線，有效避免了傳統(tǒng)模擬退火算法極易陷入局部極小值的缺陷。通過增加記憶功能使搜索全局最優(yōu)解的質(zhì)量得到提高。最后，利用這種新的算法對TSP問題進行了數(shù)值模擬，實驗結(jié)果表明，該降溫策略的性能確實優(yōu)于傳統(tǒng)降溫策略。

模擬退火算法; 降溫策略; 多普勒型; 記憶功能

寧德圣，曾光，雷莉，等.2016.基于模擬退火算法的改進型退火策略研究[J].東華理工大學學報：自然科學版，39(3)：298-300.

Ning De-sheng, Zeng Guang, Lei Li,et al.2016.Modified strategy of cooling based on simulated annealing algorithm[J].Journal of East China University of Technology (Natural Science), 39(3)：298-300.

模擬退火算法是經(jīng)典的組合優(yōu)化算法，一般在較高溫度的狀態(tài)下采用Metropolis抽樣準則隨機尋找最優(yōu)解，同時利用降溫過程來進行重復的抽樣過程，直到得到滿足相近最優(yōu)值。然而這種算法依然存在著其自身的不足, 例如算法運行時間過長、在局部最優(yōu)處終止不前以及解空間的搜索能力和范圍有限等缺陷。陳華根等(2006)、吳進波等(2007)從退火策略的角度出發(fā)，提出了一種帶有“回火”過程的降溫函數(shù)來替代傳統(tǒng)的指數(shù)降溫函數(shù)，達到提高退火效率的目的，但其本質(zhì)還是指數(shù)降溫，不具有記憶功能，沒有將兩個過程的結(jié)果進行比較，所以該算法有可能遺失最優(yōu)解；朱顥東等(2009)、周杰明等(2010)提出了帶記憶的模擬退火算法思想，引進自適應(yīng)溫度更新函數(shù)，這種算法具有記憶功能和自適應(yīng)性，但未給出具體的降溫函數(shù)表達式，其可行性無從考鑒。本文在上述研究基礎(chǔ)上，擬對模擬退火算法中的降溫函數(shù)做進一步的改進。

1 改進的模擬退火算法

Metropolis等(1953)提出了Metropolis準則，即模擬退火算法的解是否被接受的判斷準則。利用此準則編寫的模擬退火算法大大減少了CPU時間，提高了最優(yōu)解搜索效率。本文在陳華根等(2006)、孫海等(2014)研究基礎(chǔ)上對降溫函數(shù)作了進一步的改進，選取一種類似于多普勒效應(yīng)型溫度遞減曲線表達式：

T=T0αk(cos(π/(2(1-k/K)))+

cos(π/(2T0(1-k/K)))

式中，k為迭代次數(shù)，K為總的降溫次數(shù)。得出的曲線對比如圖1。

圖1 三種降溫曲線圖比較Fig.1 The comparisons of the three cooling curves

由圖1可見，指數(shù)降溫方式在迭代次數(shù)較少時，溫度難以達到低溫狀態(tài)；快速降溫方式則過早地降到了低溫狀態(tài)，使得后續(xù)的迭代求解無甚改變，基本已成定局。而中間的“多普勒”型曲線則很好地綜合了二者的優(yōu)點并消除了其缺陷，不但趨于低溫的速度不緊不慢，而且在退火過程的后半部分還進行了不斷地“回火升溫”過程，使得算法在優(yōu)化過程中具有多次跳出局部最優(yōu)的機會，從而更容易地找出全局最優(yōu)解。由于是多次降溫的過程，故此算法增加了記憶功能，使得算法在降溫過程中不會遺失最優(yōu)解。改進的模擬退火算法步驟具體為：

Step 1 初始化：初始溫度T0，終止溫度Tf，初始解狀態(tài)S，溫度衰減參數(shù)α，以及每個T值的迭代次數(shù)L，記憶矩陣M；對溫度T和k=1,2,…,L，做第2步至第5步工作；

Step 2 對初始解狀態(tài)S，采用兩點變換法、三點變換法以及兩點逆序法交替使用的方式產(chǎn)生新解S′，計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數(shù)；

Step 3 執(zhí)行Metropolis準則：若Δt′<0則將S′接受為下一次產(chǎn)生新解的當前解，或者當Δt′>0時，若概率exp(-Δt′/T)>rand(1)，也接受S′作為新的當前解，否則將當前解返回到上一次迭代時的當前解；

Step 4 執(zhí)行記憶功能：若迭代次數(shù)為1，則將當前產(chǎn)生的最好解記錄在記憶矩陣M之中；否則將當前產(chǎn)生的最好解與記憶矩陣M中的解進行比較，如果當前解優(yōu)于記憶矩陣中的解，則將當前解寫入記憶矩陣M中，否則保留記憶矩陣中的解；

Step 5 執(zhí)行溫度衰減函數(shù)：啟用“多普勒”型衰減函數(shù)衰減T值，返回第2步繼續(xù)尋優(yōu)迭代過程，直到達到終止溫度Tf時終止迭代；

Step 6 溫度衰減完畢，返回最優(yōu)目標函數(shù)值，結(jié)束程序。

2 數(shù)值實驗

本文以TSP問題作為實驗對象，用新的改進模擬退火算法重新對該問題進行試驗，并將其與其他改進的模擬退火算法進行比較。

實驗一 測試數(shù)據(jù)：CHN31，城市規(guī)模：31個。參數(shù)設(shè)置為：T0=100，L=10 000，α=0.99，Tf=0.6；

實驗二 測試數(shù)據(jù)：TSPLIB中的att48，城市規(guī)模：48個。參數(shù)設(shè)置：T0=100，L=10 000，α=0.99，Tf=0.6；

實驗三 測試數(shù)據(jù)：CHN144，城市規(guī)模：144個。參數(shù)設(shè)置：T0=100，L=10 000，α=0.99。

通過MATLAB 2015a測試得到相應(yīng)的最優(yōu)路徑圖如圖2。

圖2 三個數(shù)值實驗結(jié)果Fig.2 The results of three numerical experiments

測試得到具體數(shù)據(jù)與文獻對比結(jié)果如表1。

表1 改進的算法所得結(jié)果與當前文獻對比表

注：對于CHN31、Att48實例中的文獻最優(yōu)解來自辛振銘(2010)；CHN144實例中的文獻最優(yōu)解來自黃麗韶(2012)。

從表1試驗結(jié)果得出，利用本文改進后的算法在求解的質(zhì)量上都要高于文獻中所利用的模擬退火算法,且改進后的算法在避免求解陷入局部極小值上有著很大的提高。這三組試驗在matlab2015a仿真實驗中證明了其收斂性，其結(jié)果是可靠的，說明改進后的算法應(yīng)用于TSP問題中的正確性和可行性。

3 結(jié)束語

隨著TSP問題在現(xiàn)實生活中慢慢凸顯出的重要地位，對TSP問題求解性能要求的提高已經(jīng)迫在眉睫，各種優(yōu)化算法及改進方法需要經(jīng)過TSP問題來不斷驗證其正確性和可行性。本文對模擬退火算法的降溫策略進行了研究，提出了“多普勒”型降溫曲線，理論上此種改進既能增加算法跳出局部最優(yōu)的概率，一定程度上也提高了算法效率，使得算法在得到改進的同時并未增加實現(xiàn)的困難。

陳華根, 李麗華, 許惠平,等.2006. 改進的非常快速模擬退火算法[J]. 同濟大學學報, 34(8):1121-1125.

黃麗韶.2012. 基于模擬退火算法的TSP研究[J].應(yīng)用技術(shù)與研究, 4: 36-38.

孫海, 熊思燦, 吳志強, 2014. 基于改進SIR模型的甲型H1N1流感防控研究[J]. 東華理工大學學報:自然科學版,37(1):96-100.

吳進波, 熊盛武, 徐寧.2007. 溫度可控的求解TSP問題的模擬退火算法[J]. 計算機應(yīng)用研究, 24(5):66-67.

辛振銘.2010. 一種改進的模擬退火算法在TSP問題中的研究與應(yīng)用[D]. 東北師范大學.

周杰明, 鄧迎春, 黃婭.2010. 一種帶記憶的模擬退火算法求解TSP問題[J]. 湖南文理學院學報, 22(2):70-73.

朱顥東, 鐘勇.2009. 一種改進的模擬退火算法[J]. 計算機技術(shù)與發(fā)展, 19(6):32-35.

Metropolis N, Rosenbluth A W, Rosenbluth M N，et al. 1953. Equation of calculations by fast computing machines[J]. Journal of Chemical Physics, 21(4):1087-1092.

Modified Strategy of Cooling Based on Simulated Annealing Algorithm

NING De-sheng, ZENG Guang, LEI Li, XU Xi

(School of Sciences, East China University of Technology, Nanchang, JX 330013, China)

The cooling strategies of the algorithm is concerned. A kind of cooling curve which is similar to Doppler effect temperature decline curve is proposed. The memory function is increased, by which the defect of traditional simulated annealing algorithm easily falling into local minimum is avoided and the quality of searching global optimal solution is improved. With the experiment of TSP problem, the result shows that the strategy is superior to the conventional ones.

simulated annealing algorithm; cooling strategy; Doppler’s type; memory function

2015-10-31

國家自然基金(11661005,11301070)；江西省自然基金(20132BAB211016；20151BAB211012)；江西省教育廳科技項目(GJJ150576)

寧德圣(1992—)，男，碩士研究生，主要從事數(shù)值算法設(shè)計與優(yōu)化及矩陣計算研究。E-mail: 850640330@qq.com 通訊作者：曾 光(1984—)，男，博士，副教授，主要從事高性能科學計算及應(yīng)用研究。E-mail:zengguang5340@ecit.cn

10.3969/j.issn.1674-3504.2016.03.016

TP301.6

A

1674-3504(2016)03-0298-03