改進(jìn)新解產(chǎn)生方式及溫度函數(shù)的模擬退火算法

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

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

中圖分類(lèi)號(hào)：TP18， TP30 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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īng)用廣泛的隨機(jī)優(yōu)化算法，最早的思想是由N. Metropolis等人于1953年提出。1983 年，S. Kirkpatrick等成功地將退火思想引入到組合優(yōu)化領(lǐng)域。具體地，這是基于Monte-Carlo迭代求解策略的一種隨機(jī)優(yōu)化算法，能夠模擬物理中固體物質(zhì)的退火過(guò)程。模擬退火算法是一種通用的優(yōu)化算法，理論上具有概率的全局優(yōu)化性能，其在工程中獲得更大發(fā)展和普及應(yīng)用的同時(shí)，更在現(xiàn)如今這個(gè)大數(shù)據(jù)的時(shí)代背景下，表現(xiàn)了重要而廣闊的發(fā)展應(yīng)用空間。但是模擬退火算法也相應(yīng)存在一些缺點(diǎn)。具體地，其收斂速度較慢、計(jì)算時(shí)間較長(zhǎng)，并且當(dāng)解決一些問(wèn)題時(shí)在有限時(shí)間內(nèi)卻無(wú)法得到最優(yōu)解。

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

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

（1）

其中， ，

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

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

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

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

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

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

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

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

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

3 改進(jìn)算法

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

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

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

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

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

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

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

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

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

一次生成多個(gè)解擇優(yōu)會(huì)導(dǎo)致程序運(yùn)行時(shí)間增長(zhǎng)，這是因?yàn)閷?duì)應(yīng)改進(jìn)相當(dāng)于是加長(zhǎng)了馬氏鏈的長(zhǎng)度。因此，在給定解的精度后，可以適當(dāng)縮短馬氏鏈長(zhǎng)度，來(lái)控制運(yùn)行時(shí)間。

3.2混合溫度模擬退火算法

該處是從“冷卻進(jìn)度表”實(shí)施改進(jìn)，目的是縮短運(yùn)行時(shí)間。

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

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

（2）

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

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

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

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

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

4 將改進(jìn)算法應(yīng)用于實(shí)例驗(yàn)證算法功效

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

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

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

4.1.1 算法流程

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

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

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

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

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

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

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

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

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

Step 4：若r<=L，重復(fù)step 2。若r=L，判斷t是否小于tf，若是，則進(jìn)行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 運(yùn)行結(jié)果及分析：

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

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

溫度函數(shù)為T(mén)K= 時(shí)，改進(jìn)前和改進(jìn)后的解質(zhì)及運(yùn)行時(shí)間如圖3、圖4所示。

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

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

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

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

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

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

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

4.2 應(yīng)用于求解碎紙片拼接問(wèn)題

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

4.2.1 算法流程

將已分成11類(lèi)的碎紙片依次編號(hào)為1、2、…、11，對(duì)應(yīng)地將用模擬退火算法順序拼接編號(hào)為1至11的碎紙片類(lèi)。

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

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

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

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

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

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

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

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

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

4.2.2 運(yùn)行結(jié)果

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

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

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

平均運(yùn)行時(shí)間為111.488 3。

4.2.3 結(jié)果分析

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

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

加溫多粒子尋優(yōu)模擬退火算法與混合溫度多粒子模擬退火算法解質(zhì)相差不大，前者的平均運(yùn)行時(shí)間約為后者的2.4倍，因?yàn)榍罢弑群笳叩慕禍睾瘮?shù)的下降速度要更快。

5 結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

[1] 劉來(lái)福，黃海洋，等. 數(shù)學(xué)建模實(shí)驗(yàn)[M]. 北京：北京師范大學(xué)出版社，2014.

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

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

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