溫度可控的求解ＴＳＰ問題的模擬退火算法

摘要：在現有求解 TSP 問題的模擬退火算法的基礎上，通過引入新的兩點算子以及利用fprintf()函數﹑fscanf()函數和全局變量的作用，提出了一種溫度可控的模擬退火算法。對CHN144 以及標準的TSPLIB 中不同國家的城市的數據進行測試。測試結果表明，該算法很容易收斂到問題的最優解。

關鍵詞：旅行商問題；模擬退火算法；算子

中圖分類號：TP301．6文獻標志碼：A

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

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

1模擬退火算法求解TSP問題

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

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

下面用偽PASCAL語言對算法進行描述：

Procedure simulated_Annealing(t;g;var f)

Begin

Repeat

a:=0;

For k:=1 to L do 

Begin

對待優化問題采用優化算子;

計算目標函數差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問題中模擬退火算法用到的相關內容的定義

(1）目標函數。訪問所有城市的路徑長度，或稱為代價函數：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）代價函數差(df)。新解的代價函數與產生新解之前的代價函數的差。

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

①2變換法：任選兩個序號u、v， 且u

②3變換法: 任選三個序號u、v、w，且u

③兩點變換法：除了使用兩種變換法之外，還引入兩點變換法，增加了產生新解的變化。任選兩個序號u、v，交換序號為u和v 的城市序號，其余的城市保持不變。例如：…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問題的模擬退火算法設計思路

1．3．1本算法用到的相關內容介紹

（1）定義了兩個全局變量。因為全局變量能夠在整個程序中起作用，所以定義了全局變量g_path[]數組來保存將要優化的數據及其優化后的結果，并定義全局變量t保存溫度數據。

（2)設計一個線程函數。該線程函數的作用是實現上述1.1節所介紹的模擬退火算法。

（3）介紹兩個重要的函數：

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

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

（2）在修改溫度子菜單下設計設置溫度，用戶可以根據需要設定溫度；在優化路徑菜單下設計通知操作系統創建一個線程，運行用模擬退火算法實現的線程函數。該線程函數對保存在g_path[]中的數據進行優化，優化完畢后線程函數返回，線程終止運行。

（3）如果需要再次優化時，則回到（2），重新設置溫度，在上次優化的基礎上再次進行優化。

（4）如果需要對所求得的結果進行保留，就可以選中文件菜單中的保存項。該保存項通知操作系統執行用fprintf（）函數實現的程序段，將g_path[]中的數據寫到由自己命名的文件中，所以可以將優化得到的結果保存下來。

（5）如果需要將保存下來的結果重新優化，則可以選中文件菜單下面的載入項。該載入項通知操作系統執行用fscanf（）函數實現的程序段，將指定的文件中的數據讀到g_path[]中，然后回到（2）。

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

1．3．3本算法的特點

（1）引入兩點變換法，增加了產生新解的變化，可以收斂到問題的最優解。

（2）它與回火退火算法很相似，即能夠對優化問題進行多次回火優化。

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

（4）它能夠多次保存優化結果，并可以將保存的結果重新載入和重新優化，從而收斂到問題的最優解。

2實驗及結果

實驗用到的各參數意義分別表示如下:控制參數的初值t;控制參數的變化系數dt;鏈的長度L。

實驗一:求解CHN144實例

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

為了更好地說明該算法的有效性， 本文選用了標準的TSP 測試庫 TSPLIB[7]中的多個實例進行測試。

實驗二:求解PR144實例

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

經多次模擬，得到最優結果為58 535，優于 TSPLIB 中提供的最優結果 58 537。 具體模擬走法如圖2所示。

實驗三:求解EIL101實例 

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

經多次模擬， 得到最優結果為627，優于TSPLIB 中提供的最優結果629。具體模擬走法如圖3所示。

3結束語

本文提出了一種溫度可控的模擬退火算法，并進行了實現。通過對 CHN144 以及標準的TSPLIB 中不同國家的城市的數據進行測試，結果表明了該算法很容易收斂

到問題的最優解。

參考文獻：

［1］

HOCHBAUM D S. Approximation algorithms for NP－hard 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]康立山，謝云，尤矢勇，等.非數值并行算法：模擬退火算法:第1冊[M].北京：科學出版社，1997.

[7]標準的 TSP 測試庫[EB/OL].http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”