摘 要：本文主要研究傳統(tǒng)模擬退火算法以及改進(jìn)算法的思想，在文中分別對(duì)各個(gè)改進(jìn)算法給出了實(shí)驗(yàn)對(duì)比數(shù)據(jù)，更好證明了改進(jìn)算法的有效性；在最后討論了模擬退火算法的優(yōu)缺點(diǎn)，并在對(duì)改進(jìn)算法的分析研究的基礎(chǔ)上歸納給出模擬退火算法可行的改進(jìn)方向。

關(guān)鍵詞：模擬退火算法；組合優(yōu)化；全局優(yōu)化

中圖分類號(hào)：TP312

在自然科學(xué)、管理科學(xué)、生物科學(xué)和工程技術(shù)等科技領(lǐng)域，存在著大量的組合優(yōu)化問題（Combinatorial Optimization Problem，簡稱COP），其中的NP完全問題（Nondeterministic Polynomial Complete Problem），其求解時(shí)間隨問題規(guī)模呈指數(shù)級(jí)增長，當(dāng)規(guī)模稍大時(shí)就會(huì)因時(shí)間限而失去可行性[1]。旅行商問題TSP（Traveling Salesman Problem）問題就是一個(gè)NP完全問題，目前求解TSP問題的方法有很多，主要有模擬退火算法、遺傳算法、啟發(fā)式搜索法、Hopfield神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等[2]。

80年代初期，模擬退火算法被用來求解大規(guī)模組合優(yōu)化問題，它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法。本文研究模擬退火算法及其改進(jìn)算法，分析算法的不足和缺點(diǎn)，討論算法可行的改進(jìn)和優(yōu)化方向。

1 傳統(tǒng)的模擬退火算法

模擬退火算法（Simulated Annealing，SA）最早的思想是由N.Metropois[3]等人于1953年提出。1983年，S.Kirkpatrick[4]等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。它是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。

傳統(tǒng)的模擬退火算法優(yōu)點(diǎn)主要有：

（1）以一定的概率接受惡化解；（2）引進(jìn)算法控制參數(shù)T；（3）使用對(duì)象函數(shù)值（即適應(yīng)值）進(jìn)行搜索；（4）隱含并行性；（5）搜索復(fù)雜區(qū)域。

傳統(tǒng)的模擬退火算法優(yōu)點(diǎn)在某些情況下反而會(huì)成為算法的缺點(diǎn)：

（1）求解時(shí)間太長；（2）溫度T參數(shù)的初始值和衰減程度較難確定；（3）在算法搜索的過程中，由于接受概率是隨機(jī)的或者是不確定的，使得有可能丟失全局最優(yōu)解。

2 改進(jìn)的模擬退火算法和應(yīng)用

傳統(tǒng)的模擬退火算法存在著很多缺點(diǎn)和不足，從1983年被引入組合優(yōu)化算法到至今為止，很多研究者在傳統(tǒng)的算法基礎(chǔ)之上進(jìn)行了研究和改進(jìn)，出現(xiàn)了很多比傳統(tǒng)模擬退火算法更為優(yōu)秀的改進(jìn)算法。

2.1 1997年，中國科學(xué)院系統(tǒng)科學(xué)研究所的楊若黎和顧基發(fā)提出了一種高效的模擬退火全局優(yōu)化算法[5]。文章中提出了一種新的啟發(fā)式準(zhǔn)則和概率密度函數(shù)，用來規(guī)范模擬退火算法中溫度的更新和隨機(jī)向量的生成。通過新的啟發(fā)式準(zhǔn)則，形成了一種新的溫度更新函數(shù)。退火時(shí)間的冪函數(shù)和新導(dǎo)出來的溫度更新函數(shù)成反比，并且溫度更新函數(shù)與優(yōu)化域的空間大小沒有關(guān)系。通過實(shí)驗(yàn)數(shù)據(jù)表明，驗(yàn)證了本文所提出算法的有效性，并具有較高解質(zhì)量和較高的運(yùn)算效率。

表1分別給出了文獻(xiàn)【5】和文獻(xiàn)【6】所提出的兩種算法，在相同條件下運(yùn)行，分別計(jì)算出來目標(biāo)函數(shù)的最大、最小和平均值得情況。

2.2 在2006年，同濟(jì)大學(xué)海洋地質(zhì)國家重點(diǎn)實(shí)驗(yàn)室的陳華根等研究人員提出了一種改進(jìn)的非常快速模擬退火算法[7]。在文獻(xiàn)【7】中，作者在研究模退火機(jī)理分析的基礎(chǔ)上，提出了一種改進(jìn)的算法（MVFSA算法）的具體方案，目的是為了改進(jìn)原算法（VFSA算法）中存在的缺陷，以提高算法的效率。在模型試驗(yàn)中，對(duì)改進(jìn)后的算法與原算法的過程和結(jié)果進(jìn)行了一些列的比較，發(fā)現(xiàn)改進(jìn)后算法不僅保持了原算法全局尋優(yōu)的優(yōu)點(diǎn)，而且提高了算法的穩(wěn)健性和效率。

MVFS算法改進(jìn)的思路是：

（1）在高溫下，以模型的全局?jǐn)_動(dòng)方式代替目前的擾動(dòng)方式，因?yàn)橛呻S機(jī)發(fā)生器發(fā)生的狀態(tài)便利能力要高于VFSA算法的特殊的模型擾動(dòng)方式，并且由隨機(jī)數(shù)產(chǎn)生的全局?jǐn)_動(dòng)方式與溫度無關(guān)。

（2）在低溫下，對(duì)模型擾動(dòng)進(jìn)行某種約束，邊擾動(dòng)邊逐步減小模型擾動(dòng)空間，快速逼近最優(yōu)解，從而提高新模型被接受的幾率。

（3）2009年中國科學(xué)院朱顥東和鐘勇研究人員提出了一種改進(jìn)的模擬退火算法[8]。在文章中，對(duì)傳統(tǒng)的模擬退火算法進(jìn)行了改進(jìn)，增加了記憶功能，可以記憶運(yùn)算過程中的最好解，避免了因接受概率的問題而丟失目前最優(yōu)解，使改進(jìn)的算法成為了具有記憶功能的智能算法。具體的算法參考文獻(xiàn)【8】，本文僅給出實(shí)驗(yàn)數(shù)據(jù)結(jié)果如下表2所示。

由表3可以看出原SA算法的抽樣次數(shù)要比改進(jìn)后算法ISA多4倍，而目標(biāo)結(jié)果還不如改進(jìn)的算法，從這可以說明算法改進(jìn)是成功的。

（4）2010年楊衛(wèi)波和趙燕偉兩位研究人員，在計(jì)算機(jī)工程與應(yīng)用上發(fā)表的一篇文章提出了一種改進(jìn)的模擬退火算法求解TSP問題[9]。

在文獻(xiàn)【9】中，參考了文獻(xiàn)【8】中提出的改進(jìn)方法，增加記憶狀態(tài)避免遺失當(dāng)前最優(yōu)解，設(shè)置雙閾值以減少計(jì)算量。設(shè)計(jì)適應(yīng)TSP問題和模擬退火算法的個(gè)體鄰域搜索方法和狀態(tài)改變方法，使算法的運(yùn)行速度有了很大的提高。經(jīng)過試驗(yàn)數(shù)據(jù)驗(yàn)證，本文提出的方法是行之有效的，并且具有較高的有化解和收斂速度。詳細(xì)的算步驟參看文獻(xiàn)【8】和【9】，通過研究改進(jìn)的模擬退火算法的步驟，算法具有以下的優(yōu)點(diǎn)：

（1）算法的搜索效率有了很大的提高。

（2）設(shè)置了雙閾值，使得算法在保持最優(yōu)解得情況下提高了算法的計(jì)算效率。

（3）增加了記憶存儲(chǔ)功能。在算法搜索過程中存儲(chǔ)計(jì)算過程中的最優(yōu)解，并在過程中更新，使之能記住搜索過程中遇到的最好解，避免了由于接受概率的隨機(jī)性或不確定性而丟失當(dāng)前遇到的最優(yōu)解。

（4）2014年吉林大學(xué)的韓嘯等研究人員提出了一種基于遺傳模擬退火算法的改進(jìn)K-medoids算法[10]。針對(duì)標(biāo)準(zhǔn)的K-medoids算法在大數(shù)據(jù)聚類應(yīng)用中易陷入局部最優(yōu)解、以及聚類效果受初始中心限制的缺點(diǎn)，提出了基于遺傳模擬退火算法的K-medoids改進(jìn)算法。該算法結(jié)合遺傳算法和模擬退火算法，可以增強(qiáng)標(biāo)準(zhǔn)K-medoids算法在聚類時(shí)的全局搜索能力，并加快其收斂速度。

實(shí)驗(yàn)數(shù)據(jù)選取UCI中的4個(gè)數(shù)據(jù)集：Soybean（Small）、Iris、Pima Indians Diabetes以及yeast，此外，為了直觀比較，還選取了101個(gè)二維數(shù)據(jù)點(diǎn)繪制聚類效果圖；參數(shù)設(shè)置為：結(jié)束條件ED=1.0e-9，交叉概率pc=0.6，變異概率pm=0.5，終止進(jìn)化代數(shù)T=1000，溫度衰減率w=0.95。實(shí)驗(yàn)結(jié)果如下表3所示：

3 結(jié)束語

模擬退火算法是一種通用、高效、可行的擬物型隨機(jī)近似算法，適合求解大規(guī)模組合優(yōu)化問題，因此具有很大的使用價(jià)值。

在對(duì)傳統(tǒng)的模擬退火算法和改進(jìn)的算法進(jìn)行分析研究，模擬退火算法的改進(jìn)總體上可以分為兩個(gè)方向：

方向1：提高全局優(yōu)化解得質(zhì)量。

方向2：提高算法的計(jì)算效率。

針對(duì)方向1，我們可以通過增加某些環(huán)節(jié)來實(shí)現(xiàn)，具體的方案有：增加升溫或者重升溫過程、增加算法的記憶功能、增加局部搜索過程、增加新的搜索策略、結(jié)合其他智能優(yōu)化算法等。

對(duì)于方向2，我們可以通過選擇合適的初始值、設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)、設(shè)計(jì)高效的退火過程、采用并行的搜索結(jié)構(gòu)、改進(jìn)溫度的衰減方式、研究新的算法終止規(guī)則等方式來實(shí)現(xiàn)。

參考文獻(xiàn)：

[1]Papadimitriou，C.H.and teiglitz.K.Combinatorial optimization：Algorithms and complexity，Prentice-Hall，1982.

[2] KIRKPATRICK S，GELATT J R， VECCHI J R.Optimization by simulated annealing[J].Science，1983（220）：671-680.

[3]Metropolis N，Rosenbluth A， Rosebluth Metal.Equation of State Calculation by Fast Computing Machines[J].The Journal of Chemical Physics，1953（21）：1087-1092.

[4]Kirkpatrick S，Jr Gelatt C D，Vecchi MP.Optimization by simulated annealing[J].Sciennce，1983（11）：650-671.

[5]江加和，宋子善，沈?yàn)槿?模擬退火算法在連續(xù)變量全局優(yōu)化問題中應(yīng)用[J].北京航空航天大學(xué)學(xué)報(bào)，2001（05）：556-559.

[6]楊若黎，顧基發(fā).一種高效的模擬退火全局優(yōu)化算法[J].系統(tǒng)工程理論與實(shí)踐，1997（05）.

[7]Ingber L.Very Fast Simulated Reannealing.Mathematical and Computer Modeling，1989（12）：967-973.

[8]陳華根，李麗華，許惠平.改進(jìn)的非?？焖倌M退火算法[J].同濟(jì)大學(xué)學(xué)報(bào)，2006（08）：1121-1125.

[9]朱顥東，鐘勇.一種改進(jìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009（06）：32-35.

[10]楊衛(wèi)波，趙燕偉.求解TSP問題的改進(jìn)模擬退火算法[J].計(jì)算機(jī)工程與應(yīng)用，2010（15）：34-36.

[11]韓嘯，劉淑芬，徐天琦.基于遺傳模擬退火算法的改進(jìn)K-medoids算法[J].吉林大學(xué)學(xué)報(bào)，2014（44）.

作者簡介：李金旭（1986-），男，河南鄭州人，助教，碩士，研究方向：人工智能、智能算法。

作者單位：鄭州幼兒師范高等?？茖W(xué)校 信息網(wǎng)絡(luò)部，鄭州 450001；黃河科技學(xué)院 國際學(xué)院，鄭州 450001；鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，鄭州 450001