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

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

?

基于模擬退火算法的改進(jìn)型退火策略研究

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

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

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

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

寧德圣，曾光，雷莉，等.2016.基于模擬退火算法的改進(jìn)型退火策略研究[J].東華理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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抽樣準(zhǔn)則隨機(jī)尋找最優(yōu)解，同時(shí)利用降溫過程來進(jìn)行重復(fù)的抽樣過程，直到得到滿足相近最優(yōu)值。然而這種算法依然存在著其自身的不足, 例如算法運(yùn)行時(shí)間過長、在局部最優(yōu)處終止不前以及解空間的搜索能力和范圍有限等缺陷。陳華根等(2006)、吳進(jìn)波等(2007)從退火策略的角度出發(fā)，提出了一種帶有“回火”過程的降溫函數(shù)來替代傳統(tǒng)的指數(shù)降溫函數(shù)，達(dá)到提高退火效率的目的，但其本質(zhì)還是指數(shù)降溫，不具有記憶功能，沒有將兩個(gè)過程的結(jié)果進(jìn)行比較，所以該算法有可能遺失最優(yōu)解；朱顥東等(2009)、周杰明等(2010)提出了帶記憶的模擬退火算法思想，引進(jìn)自適應(yīng)溫度更新函數(shù)，這種算法具有記憶功能和自適應(yīng)性，但未給出具體的降溫函數(shù)表達(dá)式，其可行性無從考鑒。本文在上述研究基礎(chǔ)上，擬對(duì)模擬退火算法中的降溫函數(shù)做進(jìn)一步的改進(jìn)。

1 改進(jìn)的模擬退火算法

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

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

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

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

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

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

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

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

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

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

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

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

2 數(shù)值實(shí)驗(yàn)

本文以TSP問題作為實(shí)驗(yàn)對(duì)象，用新的改進(jìn)模擬退火算法重新對(duì)該問題進(jìn)行試驗(yàn)，并將其與其他改進(jìn)的模擬退火算法進(jìn)行比較。

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

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

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

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

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

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

表1 改進(jìn)的算法所得結(jié)果與當(dāng)前文獻(xiàn)對(duì)比表

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

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

3 結(jié)束語

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

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

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

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

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

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

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

朱顥東, 鐘勇.2009. 一種改進(jìn)的模擬退火算法[J]. 計(jì)算機(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)；江西省教育廳科技項(xiàng)目(GJJ150576)

寧德圣(1992—)，男，碩士研究生，主要從事數(shù)值算法設(shè)計(jì)與優(yōu)化及矩陣計(jì)算研究。E-mail: 850640330@qq.com 通訊作者：曾 光(1984—)，男，博士，副教授，主要從事高性能科學(xué)計(jì)算及應(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