模擬退火算法及其改進算法的研究

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

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

中圖分類號：TP312

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

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

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

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

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

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

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

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

2 改進的模擬退火算法和應用

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

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

表1分別給出了文獻【5】和文獻【6】所提出的兩種算法，在相同條件下運行，分別計算出來目標函數的最大、最小和平均值得情況。

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

MVFS算法改進的思路是：

（1）在高溫下，以模型的全局擾動方式代替目前的擾動方式，因為由隨機發(fā)生器發(fā)生的狀態(tài)便利能力要高于VFSA算法的特殊的模型擾動方式，并且由隨機數產生的全局擾動方式與溫度無關。

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

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

由表3可以看出原SA算法的抽樣次數要比改進后算法ISA多4倍，而目標結果還不如改進的算法，從這可以說明算法改進是成功的。

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

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

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

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

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

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

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

3 結束語

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

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

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

方向2：提高算法的計算效率。

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

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

參考文獻：

[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]江加和，宋子善，沈為群.模擬退火算法在連續(xù)變量全局優(yōu)化問題中應用[J].北京航空航天大學學報，2001（05）：556-559.

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

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

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

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

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

[11]韓嘯，劉淑芬，徐天琦.基于遺傳模擬退火算法的改進K-medoids算法[J].吉林大學學報，2014（44）.

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

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