彭喬姿　盧宇婷　林禹攸　王穎喆

摘要：簡單介紹了傳統(tǒng)模擬退火算法的流程、算法所涉及的重要參數(shù)、當下模擬退火算法改進的主要改進角度以及一種已有的改進算法——加溫退火法。提出了一類基于改進新解產(chǎn)生方式及溫度函數(shù)的模擬退火算法，一共包含四種新的改進算法，命名為：多粒子尋優(yōu)模擬退火算法、混合溫度模擬退火算法、混合多粒子尋優(yōu)模擬退火算法、加溫多粒子尋優(yōu)模擬退火算法。最后分別將這四種改進算法應用于求解Sobolg函數(shù)最小值和碎紙片拼接問題。實驗證明改進后的算法是有效的，分別在解的質(zhì)量以及算法效率上有所提升。關(guān)鍵詞：模擬退火算法；新解產(chǎn)生方式；溫度函數(shù)；Sobolg函數(shù)；碎紙片拼接問題

中圖分類號：TP18， TP30 文獻標識碼：A 文章編號：2095-2163（2015）05-

Simulated Annealing Algorithm based on Improving Production of New Solutions and Temperature Function

PENG Qiaozi， LU Yuting， LIN Yuyou， WANG Yingzhe

（School of Mathematics Science， Beijing Normal University， Beijing 100875， China ）

Abstract： The paper simply introduces the traditional simulated annealing algorithm through its process， key parameters， main aspects of improvement of the algorithm at present， and a new improvement named Simulated Annealing Algorithm with Heating Process which was put forward by other scholars. Then the paper puts forward a new type of simulated annealing algorithm based on improving production of new solutions and temperature function， including four improved algorithms which are named Multi-objectives Optimization Simulated Annealing Algorithm， Combined Temperature Simulated Annealing Algorithm， Combined Multi-objectives Optimization Simulated Annealing Algorithm and Multi-objectives Optimization Simulated Annealing Algorithm with Heating Process respectively. At last， the paper applies these four improved algorithms to determine the minimum value of Sobolg function and restore the shredded paper respectively. The experiments demonstrate that the new type of simulated annealing algorithm is effective and show the improvement of both the solutions of those two problems and algorithms efficiency.

Key words： Simulated Annealing Algorithm； Production of New Solutions； Temperature Function； Sobolg Function； Restoration of the Shredded Psaper

0 引 言

模擬退火算法 （Simulated Annealing Algorithm）是一種應用廣泛的隨機優(yōu)化算法，最早的思想是由N. Metropolis等人于1953年提出。1983 年，S. Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。具體地，這是基于Monte-Carlo迭代求解策略的一種隨機優(yōu)化算法，能夠模擬物理中固體物質(zhì)的退火過程。模擬退火算法是一種通用的優(yōu)化算法，理論上具有概率的全局優(yōu)化性能，其在工程中獲得更大發(fā)展和普及應用的同時，更在現(xiàn)如今這個大數(shù)據(jù)的時代背景下，表現(xiàn)了重要而廣闊的發(fā)展應用空間。但是模擬退火算法也相應存在一些缺點。具體地，其收斂速度較慢、計算時間較長，并且當解決一些問題時在有限時間內(nèi)卻無法得到最優(yōu)解。

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領(lǐng)域都有著重要的應用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復原效率。

基于此，本文分別對Sobolg函數(shù)的最小值求解和碎紙片拼接進行探究，驗證改進模擬算法算法功效， Sobolg函數(shù)為復雜天氣系統(tǒng)中一個重要的實驗函數(shù)[1]，其形式如下：

（1）

其中， ，

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

模擬退火算法[2]在給定的控制參數(shù)初值下，從隨機的可行解出發(fā)，持續(xù)進行“產(chǎn)生新解—判斷—接受/舍棄”的迭代過程，在迭代遞減時產(chǎn)生一系列的Markov鏈，通過計算系統(tǒng)的時間演化過程，逐步逼近問題的最優(yōu)解。停止準則達到后，根據(jù)控制參數(shù)衰減函數(shù)減小控制參數(shù)的值，重復進行上述步驟，就可以在控制參數(shù)達到終止時，最終求得組合優(yōu)化問題的整體最優(yōu)解。這一搜索方法是結(jié)構(gòu)化、隨機化的。求解步驟如下：

（1）初始化：選定初始控制溫度和馬氏鏈長度，并在可行解空間中選定一個初始解；

（2）產(chǎn)生新狀態(tài)：根據(jù)控制參數(shù)溫度衰減函數(shù)依次降低控制溫度，控制溫度每降低一次產(chǎn)生一個隨機擾動，得到一個新狀態(tài)；

（3）產(chǎn)生新解：根據(jù)狀態(tài)接受函數(shù)判斷是否接受這個新狀態(tài)作為新解；

（4）輸出最優(yōu)解：根據(jù)停止準則判定算法是否終止，若不終止則返回（2）直到滿足停止準則輸出最優(yōu)解。

2 模擬退火算法的主要改進設(shè)計及加溫退火法

雖然模擬退火算法所得解能夠依概率收斂到全局最優(yōu)解[3]，但是其收斂速度比較慢，而且計算時間比較長，這些都在相當程度上降低了該算法的效率，導致模擬退火算法在實際應用中有較大的局限性，因此，不斷有學者對傳統(tǒng)的模擬退火算法提出一定改進，其目的主要是提高解的質(zhì)量（解質(zhì)）以及算法效率。改進設(shè)計主要表述為“移動策略”和“冷卻進度表”。其中，改進移動策略即為改進新解產(chǎn)生方式，改進冷卻進度表即改進冷卻進度表中所涉及的主要控制參數(shù)：降溫函數(shù)、初末溫和馬氏鏈長度。

加溫退火法[3]通過改變初始解的選取方式達到提高解的質(zhì)量的目的。其算法流程為：對組合優(yōu)化問題實例的任給的初始解，先令初溫T0=0，然后進行若干次試驗，當且僅當目標函數(shù)值增大時接受其轉(zhuǎn)移，同時令T0按某個增量函數(shù)h（T）增加，當試驗結(jié)束時，以所得的T0值作為控制參數(shù)T的初值，并以此時的當前解作為初始解 開始退火。

3 改進算法

為使得算法能保存當前最優(yōu)解，四種算法都增加了記憶功能，即把當前最優(yōu)解記憶下來。

3.1 多粒子尋優(yōu)模擬退火算法

這一改進是基于“移動策略”，目的是在允許時間范圍內(nèi)，提高解質(zhì)。

將傳統(tǒng)模擬退火算法中產(chǎn)生新解時的“一次擾動”求得新解，替換成“n次擾動”，分別計算n次擾動對應狀態(tài)的函數(shù)值，選擇其中函數(shù)值最小的作為新解。因為當前解的鄰域內(nèi)的每一個點都可以作為新解，假如x*是該鄰域內(nèi)的一個使得目標函數(shù)可達極小值的解，按照傳統(tǒng)模擬退火算法的流程，可能需要循環(huán)i次才能夠達到這個解。但如果一次生成n個解擇優(yōu)作為新解的話，達到x*的概率加大，并且循環(huán)次數(shù)也可以減少。如果馬氏鏈的長度不變的話，生成的解的質(zhì)量應該會有所提高。

下面通過Sobol g函數(shù)的例子來研究生成解個數(shù)與解質(zhì)及運行時間所形成的數(shù)值變量關(guān)系。

初末溫溫度比是100：1，溫度函數(shù)是TK= Ts ，馬氏鏈長度都是200時，分別生成1、2、3、5、7、9個解，重復運行30次，計算平均解質(zhì)與平均運行時間，結(jié)果如表1所示。

從表1可得，解質(zhì)隨生成解個數(shù)的增加而呈現(xiàn)提升態(tài)勢。解質(zhì)從1到2變化較大，之后解質(zhì)變化轉(zhuǎn)為很小。運行時間則基本上與生成解的個數(shù)成正比。

考慮到解質(zhì)和運行時間的單位不同，將最小值估計和運行時間作乘積后再作圖，結(jié)果如圖1所示。

由圖1可知，生成2個解時解質(zhì)變化提高最快，時間增加較少，算法效率最高。因此對Sobol g函數(shù)發(fā)生的改進中，選擇生成兩個解擇優(yōu)作為新解來進行驗證。此外，由于問題不同，該改進中生成新解的個數(shù)選擇是不同的，但由上述分析可以推測，無論是哪種具體問題，生成新解的個數(shù)也不會是越多越好。為使算法運行可得較高的效率，可以選擇使解質(zhì)改變最大、運行時間很長的生成解個數(shù)作為改進方案。

一次生成多個解擇優(yōu)會導致程序運行時間增長，這是因為對應改進相當于是加長了馬氏鏈的長度。因此，在給定解的精度后，可以適當縮短馬氏鏈長度，來控制運行時間。

3.2混合溫度模擬退火算法

該處是從“冷卻進度表”實施改進，目的是縮短運行時間。

冷卻進度表中三種溫度函數(shù)降溫過程中變化如圖2所示。由圖2可知，在溫度變化次數(shù)k比較小時，變化速度由快到慢的依次是代數(shù)式收斂1/k、對數(shù)式收斂1/log（k）、指數(shù)式收斂0.99k；在溫度變化次數(shù)較大時，代數(shù)式函數(shù)1/k和指數(shù)式收斂0.99k的變化速度都很快，而對數(shù)式收斂1/log（k）的變化速度卻非常慢。根據(jù)模擬退火的收斂性理論，即溫度函數(shù)應選取比對數(shù)式收斂1/log（k）變化態(tài)勢更慢的類型，才可以保證算法依概率1收斂到全局最優(yōu)解。但對數(shù)式收斂1/log（k）的算法運行時間過長，具體實際中很難獲得使用。為加快算法的運行速度，選擇將兩種溫度函數(shù)拼接到一起，前m次溫度函數(shù)使用， 希望能迅速找到全局最優(yōu)解所在的鄰域，m次之后的溫度函數(shù)使用 ，以減少算法運行時間為總之，使其能夠在一定精度范圍內(nèi)較快地搜索到最優(yōu)解的估計值。

選擇使用降溫函數(shù)：

（2）

其中，m是預先固定的值。由上面三種溫度函數(shù)下降圖可知，找到log函數(shù)的拐點所對應的變化次數(shù)作為m。對log函數(shù)求導，可得m=15。

3.3 混合多粒子尋優(yōu)模擬退火算法

在這個算法中，從“移動策略”和“冷卻進度表”兩方面實行改進，將多粒子尋優(yōu)模擬退火算法、混合溫度模擬退火算法相結(jié)合，即降溫函數(shù)選擇混合降溫函數(shù)，產(chǎn)生新解則更改為產(chǎn)生兩個解擇優(yōu)作為新解，由此而達到提高解的質(zhì)量的顯示效果作用。

3.4 加溫多粒子尋優(yōu)模擬退火算法

在這個算法中，從“移動策略”和“冷卻進度表”兩方面來執(zhí)行改進，將加溫退火法與多粒子尋優(yōu)模擬退火算法相結(jié)合，即先用加溫退火法來得到所需的初溫，再進行多粒子尋優(yōu)，達到提高解的質(zhì)量，進而減少運行時間的作用。

4 將改進算法應用于實例驗證算法功效

下面將多粒子尋優(yōu)模擬退火算法、混合溫度模擬退火算法用于求解Sobolg函數(shù)最小值和碎紙片拼接問題進行實例驗證，將混合多粒子尋優(yōu)模擬退火算法、加溫多粒子尋優(yōu)模擬退火算法用于求解碎紙片拼接問題進行實例驗證。

4.1 應用于求解Sobol g函數(shù)最小值

下面分別將傳統(tǒng)的模擬退火算法（即改進前的模擬退火算法）、多粒子尋優(yōu)模擬退火算法及混合溫度模擬退火算法用于求解Sobolg函數(shù)最小值，并分別將改進后與改進前的算法進行了對比統(tǒng)計，得出算法改進功效。

4.1.1 算法流程

（1）多粒子尋優(yōu)模擬退火算法

Step 1：給定初溫t0、末溫tf、馬氏鏈長度L，令溫度t=t0。隨機生成一個5維的均勻分布隨機數(shù)作為初始解x0，計算其目標函數(shù)值作為當前目標函數(shù)值Gc，將初始解記為當前解xc。再令最優(yōu)解和最優(yōu)目標函數(shù)值xb和Gb分別為xc和Gc，令k=1；

Step 2：令r=1。產(chǎn)生2個5維的正態(tài)擾動，進行一定的處理使之加到當前解上不會超出定義域。記這兩個解為x1、x2，并計算其對應的目標函數(shù)值G1、G2，選擇結(jié)果中最小的作為新解，記為xn，相應的目標函數(shù)值記為Gn；

Step 3：比較Gn和Gc：若Gn Gc，生成一個隨機數(shù)rand，若rand < exp（（Gc-Gn）/tk），則令xc=xn，Gc=Gn，否則不做任何改變，回到xc。r=r+1。

Step 4：若r<=L，重復step 2。若r=L，判斷t是否小于tf，若是，則進行step 5；若不是，令t=t0*0.99^k，k=k+1，再回到step 2。

Step 5：輸出最優(yōu)解和最優(yōu)目標函數(shù)值。

（2）混合溫度模擬退火算法

將上面算法過程中的Step 2、Step 4修改為以下的Step 2、Step 4：

Step 2：令r=1。產(chǎn)生1個5維的正態(tài)擾動，進行一定的處理使之加到當前解上不會超出定義域。記這個新解為xn，并計算目標函數(shù)值Gn；

Step 4：若r<=L，重復step 2。若r=L，判斷t是否小于tf，若是，則進行step 5；若不是，判斷k是否小于15，若是，令t=t0/log（k+1），k=k+1；若不是，則令t=t0*0.99^k，k=k+1，再回到step 2。

4.1.2 運行結(jié)果及分析：

（1）多粒子尋優(yōu)模擬退火算法

固定馬氏鏈長度L=100，末溫為1，初溫分別為50，100，200，300，500，1 000，重復運行30次，一次產(chǎn)生2個解擇優(yōu)作為新解。

溫度函數(shù)為TK= 時，改進前和改進后的解質(zhì)及運行時間如圖3、圖4所示。

溫度函數(shù)為TK= 時（由于運行時間關(guān)系只呈現(xiàn)兩組數(shù)據(jù)），改進前和改進后的算法所得解的質(zhì)量和運行時間如表2所示。

解質(zhì)上，改進后解質(zhì)比改進前解質(zhì)精確度提高了10倍，而改進后運行時間則約為改進前運行時間的3倍。

綜上，多粒子尋優(yōu)模擬退火適用于使用的降溫函數(shù)是TK= 、TK= ，這種溫度下降較快、運行時間也不是很長的算法，能夠在允許時間范圍內(nèi)得到比傳統(tǒng)模擬退火算法更為精確的解，而對于本身下降速度較慢、運行時間很長的TK= 來說，這種改進則有些得不償失。

（2）混合溫度模擬退火算法

固定末溫是1，初溫50、100、200、300、500、1 000，馬氏鏈長度300，重復30次取平均。改進后解質(zhì)及運行時間比較如圖7、圖8所示。（圖7中橫坐標是初溫，縱坐標是最優(yōu)解）

由圖7、圖8可知，解質(zhì)方面，在初溫較低時，改進后的解質(zhì)明顯優(yōu)于改進前TK= 的解質(zhì)，與 的解質(zhì)相差不大；在初溫較高時，三種函數(shù)的解質(zhì)相差不大。與初末溫比是10：1的降溫函數(shù)TK= 的解質(zhì)相比，雖比其稍差但卻有所接近。運行時間方面，改進后的運行時間比改進前溫度函數(shù)是 的運行時間普遍要更短，這一結(jié)論符合前面的理論分析。在初溫較低時，改進后的運行時間則大于改進前TK= 的運行時間；在初溫較高時，改進后的運行時間卻要低于TK= 的運行時間。而且，改進后的運行時間整體上要少于初末溫比是10：1時降溫函數(shù)TK= 的運行時間。

綜上，改進后的算法受初末溫比影響小，解質(zhì)比較穩(wěn)定，且與解質(zhì)較穩(wěn)定的降溫函數(shù)是 的算法相比，運行時間有所減少。

4.2 應用于求解碎紙片拼接問題

下面分別將傳統(tǒng)的模擬退火算法（即改進前的模擬退火算法）、多粒子尋優(yōu)模擬退火算法、混合溫度模擬退火算法、混合多粒子尋優(yōu)模擬退火算法及加溫多粒子尋優(yōu)模擬退火算法用于求解碎紙片拼接問題，紙片為碎紙機既縱切又橫切的情形，中文單面被切為1 119個碎片[4]，最后分別將四種改進算法的實際功效進行了仿真對比。

4.2.1 算法流程

將已分成11類的碎紙片依次編號為1、2、…、11，對應地將用模擬退火算法順序拼接編號為1至11的碎紙片類。

（1） 碎紙片類拼接傳統(tǒng)模擬退火算法步驟

Step 1：依照初始化過程，設(shè)置溫度初值，隨機生成紙片初始位置，根據(jù)距離矩陣算出初始位置下距離函數(shù)值，選擇降溫函數(shù)是 （C<1，充分接近1）。

Step 2：在溫度下，利用均勻分布對紙片位置進行一次隨機擾動，得到每張紙片的新位置，運用Metropolis準則決定紙片是否向新位置轉(zhuǎn)移，記錄紙片位置轉(zhuǎn)移后的最小距離函數(shù)值及其所對應的紙片位置（最優(yōu)紙片位置）；

Step 3：重復進行step 2，直至達到循環(huán)次數(shù)滿足層內(nèi)停止準則。記錄下過程中的最小距離函數(shù)值及其所對應的紙片位置；

Step 4：改變溫度TK，重復進行step 2、3，直至溫度達到預先設(shè)置的終值1，溫度達到終值后，由step 2、step 3確定的紙片位置終態(tài)的最優(yōu)紙片位置（即“記憶”）則將是最終拼接結(jié)果。

（2） 多粒子尋優(yōu)模擬退火算法將（1） Step 2中“利用均勻分布對紙片位置進行一次隨機擾動”改為“利用均勻分布對該紙片位置進行n次隨機擾動，比較n次隨機擾動后的距離函數(shù)，選取距離函數(shù)最小的擾動作為紙片擾動新位置”。

（3） 混合溫度模擬退火算法將（1）中溫度變化改為“前n次的溫度函數(shù)為TK= ，之后溫度函數(shù)為TK= ”。

（4） 加溫多粒子尋優(yōu)模擬退火算法將加溫模擬退火算法和多粒子尋優(yōu)模擬退火算法的改進實現(xiàn)了應用結(jié)合。

（5） 混合多粒子尋優(yōu)溫度模擬退火算法將混合溫度模擬退火算法和多粒子尋優(yōu)模擬退火算法的改進實現(xiàn)了應用結(jié)合。

4.2.2 運行結(jié)果

中文碎紙片橫縱拼接，已將屬于同一橫條的紙片歸為一類，進行紙片橫向拼接。以下退火算法（除涉及加溫的算法外）初溫均為100，末溫均為1。

混合溫度多粒子模擬退火算法：

粒子數(shù)為5；前15次降溫函數(shù)為TK= ，之后降溫函數(shù)為TK= ；馬氏鏈長度為1 000。 所得解平均需要人工干預1.866 67次；

平均運行時間為111.488 3。

4.2.3 結(jié)果分析

由表3可知，多粒子尋優(yōu)模擬退火算法的解質(zhì)優(yōu)于傳統(tǒng)模擬退火算法和加溫模擬退火算法，但其平均運行時間比后兩個算法更長，在獲得較好解質(zhì)的同時，花費了較多的時間。

混合溫度模擬退火算法的解質(zhì)優(yōu)于傳統(tǒng)模擬退火算法及多粒子尋優(yōu)模擬退火算法，運行時間與傳統(tǒng)模擬退火算法相差不大，在以上兩個只從一個角度實行改進的算法中，算法呈現(xiàn)的運行時間最短，解質(zhì)最優(yōu)。混合溫度模擬退火算法前階段的TK= 的下降速度在k<16時大于TK= ， 后階段的TK= 的下降速度在k>15時大于TK= ，因此混合模擬退火算法的運行速度更快，從運行結(jié)果可知其解質(zhì)優(yōu)于傳統(tǒng)模擬退火算法。

加溫多粒子尋優(yōu)模擬退火算法與混合溫度多粒子模擬退火算法解質(zhì)相差不大，前者的平均運行時間約為后者的2.4倍，因為前者比后者的降溫函數(shù)的下降速度要更快。

5 結(jié)束語

本文從不同的改進角度提出了多粒子尋優(yōu)模擬退火算法和混合溫度模擬退火算法，在此基礎(chǔ)上，結(jié)合已有加溫退火算法，構(gòu)造了加溫多粒子尋優(yōu)模擬退火算法與混合溫度多粒子尋優(yōu)模擬退火算法。實例運算結(jié)果表明，采用多粒子尋優(yōu)模擬退火算法可以顯著提高求解全局最優(yōu)化問題的解質(zhì)，采用混合溫度模擬退火算法可以提高求解全局最優(yōu)化問題的算法效率，加溫多粒子尋優(yōu)模擬退火算法與混合溫度多粒子尋優(yōu)模擬退火算法，均達到算法改進的目的。

另外，通過對比這四種算法的求解結(jié)果還得到一個結(jié)論：只從一個角度進行改進的算法所得結(jié)果明顯優(yōu)于同時從兩個角度進行改進的算法，表現(xiàn)為所得解質(zhì)相差不大但是時間大大減少，因而在綜合考慮解質(zhì)及算法效率，并對算法效率要求較高的情況下，選擇只是變化一個角度的改進算法將會更好。

參考文獻：

[1] 劉來福，黃海洋，等. 數(shù)學建模實驗[M]. 北京：北京師范大學出版社，2014.

[2] MISEVICIUS A. A modified Simulated Annealing Algorithm for the quadratic assignment problem[J]. INFORMATICA， 2003， 14（ 4）：497–514.

[3] 康立山，等. 非數(shù)值并行算法（第一冊）：模擬退火算法[M]. 北京：科學出版社，1994-4：29-30，84-124

[4] 馬俊明，賴楚廷，等. 基于文字特征的規(guī)則碎紙片自動拼接[J]. 汕頭大學學報（自然科學版），2014，29： 4-10.