溫度可控的求解ＴＳＰ問(wèn)題的模擬退火算法

摘要：在現(xiàn)有求解 TSP 問(wèn)題的模擬退火算法的基礎(chǔ)上，通過(guò)引入新的兩點(diǎn)算子以及利用fprintf()函數(shù)﹑fscanf()函數(shù)和全局變量的作用，提出了一種溫度可控的模擬退火算法。對(duì)CHN144 以及標(biāo)準(zhǔn)的TSPLIB 中不同國(guó)家的城市的數(shù)據(jù)進(jìn)行測(cè)試。測(cè)試結(jié)果表明，該算法很容易收斂到問(wèn)題的最優(yōu)解。

關(guān)鍵詞：旅行商問(wèn)題；模擬退火算法；算子

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)05－0066－02

旅行商問(wèn)題 (Traveling Salesman Problem，TSP)，也稱為貨郎擔(dān)問(wèn)題， 是指給定n個(gè)城市并給出每?jī)蓚€(gè)城市之間的距離，旅行商必須以最短路徑訪問(wèn)所有的城市一次且僅一次， 并回到出發(fā)地。現(xiàn)已證明它屬于NP－h(huán)ard題。由于該問(wèn)題的描述簡(jiǎn)單，而其實(shí)際模型在印刷電路板的鉆孔路線方案、連鎖店的貨物匹送、網(wǎng)絡(luò)布線等優(yōu)化問(wèn)題中又有著廣泛的應(yīng)用，故長(zhǎng)期以來(lái)一直吸引著國(guó)內(nèi)外許多研究人員對(duì)其進(jìn)行研究。他們嘗試著用各種算法來(lái)求解TSP問(wèn)題，歸納起來(lái)有近似解法[1]、局部搜索法[2]、神經(jīng)網(wǎng)絡(luò)[3]、遺傳算法[4]、克隆算法[5]、模擬退火算法[6]等。本文在文獻(xiàn)[6]的基礎(chǔ)上，引入新的兩點(diǎn)算子:隨機(jī)選擇兩點(diǎn)，然后交換它們的位置。 這種新的算子增加了產(chǎn)生新解的變化。本文利用全局變量作用， 將要優(yōu)化的數(shù)據(jù)保存到全局變量g_path[]數(shù)組中，并定義全局變量t保存溫度，然后將模擬退火算法定義成一個(gè)線程函數(shù)。所以可以多次激活模擬退火線程函數(shù)，在重新設(shè)置溫度的情況下和上次優(yōu)化的基礎(chǔ)上重新優(yōu)化。本文還利用了fprintf（）函數(shù)的作用，將優(yōu)化得到的結(jié)果寫到文件中去。如果需要將保留在文件中的數(shù)據(jù)讀到g_path[]數(shù)組中去進(jìn)行重新優(yōu)化，則可以利用fscanf（）函數(shù)將保留在文件中的數(shù)據(jù)讀到g_path[]數(shù)組中，然后激活模擬退火線程函數(shù)對(duì)其進(jìn)行優(yōu)化。

1模擬退火算法求解TSP問(wèn)題

模擬退火算法源于對(duì)固體退火過(guò)程的模擬，固體退火過(guò)程是先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學(xué)過(guò)程。對(duì)固體退火過(guò)程的研究給人們以新的啟示。1982年，Kirpatrick等人首先意識(shí)到固體退火過(guò)程與組合優(yōu)化問(wèn)題之間存在著類似性。Metroplis等人對(duì)固體在恒定溫度下達(dá)到熱平衡過(guò)程的模擬也給人們以重要的啟示。于是研究者把Metroplis準(zhǔn)則引入到優(yōu)化過(guò)程中來(lái)，最終得到一種對(duì)Metroplis算法進(jìn)行迭代的組合優(yōu)化算法——模擬退火算法。

1．1模擬退火算法的介紹[6] 

下面用偽PASCAL語(yǔ)言對(duì)算法進(jìn)行描述：

Procedure simulated_Annealing(t;g;var f)

Begin

Repeat

a:=0;

For k:=1 to L do 

Begin

對(duì)待優(yōu)化問(wèn)題采用優(yōu)化算子;

計(jì)算目標(biāo)函數(shù)差df;

If (df<0) or (exp(－df/t)>random)

Then begin

接收新解;

f:=f+df;

a:=1;

end

t:=t*dt;

if a=0 then s:=s+1

else s:=0;

until s=1;

End;

End;

1．2TSP問(wèn)題中模擬退火算法用到的相關(guān)內(nèi)容的定義

(1）目標(biāo)函數(shù)。訪問(wèn)所有城市的路徑長(zhǎng)度，或稱為代價(jià)函數(shù)：f(S)=∑d[Cn(i)，Cn(i+1) mod N](i=1，2，3，…，N)。其中，d[Cn(i)，Cn(i+ 1) mod N]為城市Cn(i) 與Cn(i+1) mod N之間的距離。

(2）代價(jià)函數(shù)差(df)。新解的代價(jià)函數(shù)與產(chǎn)生新解之前的代價(jià)函數(shù)的差。

(3）產(chǎn)生新解所用到的一些變換算子

①2變換法：任選兩個(gè)序號(hào)u、v， 且u

②3變換法: 任選三個(gè)序號(hào)u、v、w，且u

③兩點(diǎn)變換法：除了使用兩種變換法之外，還引入兩點(diǎn)變換法，增加了產(chǎn)生新解的變化。任選兩個(gè)序號(hào)u、v，交換序號(hào)為u和v 的城市序號(hào)，其余的城市保持不變。例如：…Cn(u-1)Cn(u)Cn(u+1)…Cn(v-1)Cn(v)Cn(v+1)…，換后為…Cn(u-1)Cn(v)Cn(u+1) …Cn(v-1)Cn(u)Cn(v+1)…。

1．3溫度可控的求解 TSP問(wèn)題的模擬退火算法設(shè)計(jì)思路

1．3．1本算法用到的相關(guān)內(nèi)容介紹

（1）定義了兩個(gè)全局變量。因?yàn)槿肿兞磕軌蛟谡麄€(gè)程序中起作用，所以定義了全局變量g_path[]數(shù)組來(lái)保存將要優(yōu)化的數(shù)據(jù)及其優(yōu)化后的結(jié)果，并定義全局變量t保存溫度數(shù)據(jù)。

（2)設(shè)計(jì)一個(gè)線程函數(shù)。該線程函數(shù)的作用是實(shí)現(xiàn)上述1.1節(jié)所介紹的模擬退火算法。

（3）介紹兩個(gè)重要的函數(shù)：

1．3．2本文算法的介紹

（1）設(shè)計(jì)一個(gè)圖形用戶界面，它擁有文件和優(yōu)化兩個(gè)菜單。其中文件菜單下面有載入﹑保存和退出三個(gè)子菜單，優(yōu)化菜單下面有優(yōu)化路徑和修改溫度兩個(gè)子菜單。

（2）在修改溫度子菜單下設(shè)計(jì)設(shè)置溫度，用戶可以根據(jù)需要設(shè)定溫度；在優(yōu)化路徑菜單下設(shè)計(jì)通知操作系統(tǒng)創(chuàng)建一個(gè)線程，運(yùn)行用模擬退火算法實(shí)現(xiàn)的線程函數(shù)。該線程函數(shù)對(duì)保存在g_path[]中的數(shù)據(jù)進(jìn)行優(yōu)化，優(yōu)化完畢后線程函數(shù)返回，線程終止運(yùn)行。

（3）如果需要再次優(yōu)化時(shí)，則回到（2），重新設(shè)置溫度，在上次優(yōu)化的基礎(chǔ)上再次進(jìn)行優(yōu)化。

（4）如果需要對(duì)所求得的結(jié)果進(jìn)行保留，就可以選中文件菜單中的保存項(xiàng)。該保存項(xiàng)通知操作系統(tǒng)執(zhí)行用fprintf（）函數(shù)實(shí)現(xiàn)的程序段，將g_path[]中的數(shù)據(jù)寫到由自己命名的文件中，所以可以將優(yōu)化得到的結(jié)果保存下來(lái)。

（5）如果需要將保存下來(lái)的結(jié)果重新優(yōu)化，則可以選中文件菜單下面的載入項(xiàng)。該載入項(xiàng)通知操作系統(tǒng)執(zhí)行用fscanf（）函數(shù)實(shí)現(xiàn)的程序段，將指定的文件中的數(shù)據(jù)讀到g_path[]中，然后回到（2）。

（6）如果需要退出，則選擇文件菜單下面退出子菜單即可。

1．3．3本算法的特點(diǎn)

（1）引入兩點(diǎn)變換法，增加了產(chǎn)生新解的變化，可以收斂到問(wèn)題的最優(yōu)解。

（2）它與回火退火算法很相似，即能夠?qū)?yōu)化問(wèn)題進(jìn)行多次回火優(yōu)化。

（3）它比回火退火算法更加靈活方便。回火退火算法的回火次數(shù)和每次回火的溫度是在運(yùn)行前確定的，如果要修改溫度和回火次數(shù)，則要求程序員重新修改程序。而上述算法可以根據(jù)需要由人從鍵盤多次輸入溫度的值，然后進(jìn)行多次優(yōu)化，而無(wú)須修改程序。

（4）它能夠多次保存優(yōu)化結(jié)果，并可以將保存的結(jié)果重新載入和重新優(yōu)化，從而收斂到問(wèn)題的最優(yōu)解。

2實(shí)驗(yàn)及結(jié)果

實(shí)驗(yàn)用到的各參數(shù)意義分別表示如下:控制參數(shù)的初值t;控制參數(shù)的變化系數(shù)dt;鏈的長(zhǎng)度L。

實(shí)驗(yàn)一:求解CHN144實(shí)例

所使用的參數(shù):t=22，dt=0.95，L=60 000，t模擬20次，得到如表1所示的結(jié)果。

為了更好地說(shuō)明該算法的有效性， 本文選用了標(biāo)準(zhǔn)的TSP 測(cè)試庫(kù) TSPLIB[7]中的多個(gè)實(shí)例進(jìn)行測(cè)試。

實(shí)驗(yàn)二:求解PR144實(shí)例

所使用的參數(shù):t=80， dt=0.95，L=960 000。

經(jīng)多次模擬，得到最優(yōu)結(jié)果為58 535，優(yōu)于 TSPLIB 中提供的最優(yōu)結(jié)果 58 537。 具體模擬走法如圖2所示。

實(shí)驗(yàn)三:求解EIL101實(shí)例 

所使用的參數(shù):t=50，dt=0.95，L=8 000。

經(jīng)多次模擬， 得到最優(yōu)結(jié)果為627，優(yōu)于TSPLIB 中提供的最優(yōu)結(jié)果629。具體模擬走法如圖3所示。

3結(jié)束語(yǔ)

本文提出了一種溫度可控的模擬退火算法，并進(jìn)行了實(shí)現(xiàn)。通過(guò)對(duì) CHN144 以及標(biāo)準(zhǔn)的TSPLIB 中不同國(guó)家的城市的數(shù)據(jù)進(jìn)行測(cè)試，結(jié)果表明了該算法很容易收斂

到問(wèn)題的最優(yōu)解。

參考文獻(xiàn)：

［1］

HOCHBAUM D S. Approximation algorithms for NP－h(huán)ard problems[M].[S.l.]:World Books Press，1995.

[2]LIN S， KERNIGHAN B W. An effective heuristic algorithm for the traveling salesman problem[J].Operations Research，1973，21(2):498－516.

[3]HOPFIELD J J ，TANK D W. Neural computation of decision in optimization problems[J].Biological Cybernetics，1985，54(3):141－152.

[4]VIGNAUX G，MICHALEWITCZ Z. A genetic algorithm for the linear transportation problems[J ].IEEE Sys.Man Cybe.，1991，21(2):445－452.

[5]CASTRO D L N， ZUBEN V F J. Learning and optimization using the clonal selection principle[J].IEEE Transactionon Evolution Computation，2002，6(3):239－251. 

[6]康立山，謝云，尤矢勇，等.非數(shù)值并行算法：模擬退火算法:第1冊(cè)[M].北京：科學(xué)出版社，1997.

[7]標(biāo)準(zhǔn)的 TSP 測(cè)試庫(kù)[EB/OL].http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”