旅行售貨員問題TSP的模擬退火算法

張育藺

摘 要： 旅行售貨員問題（Traveling salesman problem）是計算機算法中的一個經典的難解問題，已被證明是一個NP-C（Nondeterministic Polynomial-Completeness）問題，其計算復雜度O（n！），無法找到一個多項式算法解決此類問題。本文利用最優化理論中的模擬退火法，簡述了TSP問題的近似算法。

關鍵詞： 旅行售貨員問題 NP-C 近似算法 模擬退火法 遺傳算法

1.旅行售貨員問題（Traveling salesman problem）

旅行售貨員問題（TSP）或稱為貨郎擔問題，可描述為：設有n個城市及表示城市i到城市j的距離D=|d■|，其中d■>0，d■=d■，并有d■+d■≥d■，且d■=0（i，j=1，2，3，…，n），一個貨郎從一個城市出發，不重復地遍歷所有城市并回到起點，求一條路程最短的路徑。

這個問題已被證明是一個NP-C（Nondeterministic Polynomial-Completeness）問題，其計算復雜度為O（n！），目前還不能找出一個多項式算法解決此類問題，但解決此類問題有較大的現實意義。例如：在網絡通信中求解路由問題時，可用節點間的路徑長度代表網絡節點間的通信代價，而求解一條代價最小路由回路即可轉化為TSP問題的求解。

下面將簡述TSP問題的兩種不同近似算法：模擬退火算法、遺傳算法。

2.模擬退火算法

KIRKPATRICK等于1983年首先提出模擬退火算法。模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e-ΔE/（kT），其中E為溫度T時的內能，ΔE為其改變量，k為Boltzmann常數。將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表（Cooling Schedule）控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

2.1模擬退火算法的模型

模擬退火算法可以分解為解空間、目標函數和初始解三部分。

模擬退火的基本思想：（1）初始化：初始溫度T（充分大），初始解狀態S（是算法迭代的起點），每個T值的迭代次數L；（2）對k=1，……，L做第（3）至第6步；（3）產生新解S′；（4）計算增量Δt′=C（S′）-C（S），其中C（S）為評價函數；（5）若Δt′<0則接受S′作為新的當前解，否則以概率exp（-Δt′/T）接受S′作為新的當前解；（6）如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接受時終止算法；（7）T逐漸減少，且T>0，然后轉第2步。

2.2在TSP問題中的應用

2.2.1解空間與初始解

將TSP的一個解表示為一個循環排列π=（π■，π■，…，π■），也可表示為：π■→π■→…π■的一條路徑，必須滿足π■≠π■（i≠j的解才是可行解），π■（1≤i≤n）是該路徑中第i個經過的城市，所有的可行解的集合構成解空間S。在TSP問題中解空間S為{1，2，…，n}的循環排列，其中每一循環排列表示遍訪n個城市的一條回路，并約定π■=π■，初始解定為{1，2，…，n}。

2.2.2目標函數

f（π）=min■d■ （1）

式中：■d■為訪問所有城市的路徑長度。

2.2.3新解的產生

采用二鄰域法這樣一種改進的相鄰狀態變換方法。如下圖所示，設（s，f）是討論問題的一個實例，而n■是一個二變換領域結構，則二變換n■（p，q）可看成是城市p與q間路徑的反向接入。

圖1 路徑變換

變換后的新路徑是π■…π■π■…π■π■π■…π■（u

2.2.4隨機移動準則

采用METROPOLIS準則，由隨機移動接受概率

p■（i？圯j）=1 f（j）≤f（i）exp[■]f（j）>f（i） （2）

上式中：t為控制參數，確定是否接受從當前解i到新解j的轉移。計算開始時t取較大值（與固體的熔解溫度相對應），在進行足夠多的轉移后，緩慢減小t值（與“徐徐”降溫相對應），如此重復，直至滿足某個停止準則時計算終止。

2.2.5算法描述

在本算法中，采用隨機數發生器來交換兩城市訪問次序的方法產生新解，冷卻進度表的衰減函數設為α，MAPKOB鏈的長度取為城市數n的100倍。城市坐標初始化按照前面的方法產生初始回路，并計算總路徑長度。

（1）采用二變換法更改初始路徑，并得到一條新路徑，計算更改后總路徑與初始路徑的長度差△f；

（2）如果滿足METROPOLIS準則，則更換路徑的行走方式，否則重復過程（1）；

（3）取衰減函數α，隨著t■=αt■（k=1，2，3，…，n）而降溫，并轉向（1）；

（4）當滿足停止準則而采用某一t值時，接受新解次數以小于10n為準。當次數大于該值時，則執行降溫過程，重新執行退火過程。

在程序中，隨機數發生器確定之后，需要經過多次實際選取合適溫度計劃表中的各個參數，包括控制參數t及其衰減函數α，對應MAPKOB鏈的長度本程序選擇如下：

（1）控制參數t=0.5；

（2）衰減函數α=0.95；

（3）MAPKOB鏈的長度L■=100n（n表示城市數）.

根據上述分析，可寫出用模擬退火算法求解TSP問題的偽程序：

Procedure TSPSA：

begin

init-of-T；{T為初始溫度}

S={1，……，n}；{S為初始值}

termination=false；

while termination=false

begin

for i=1 to L do

begin generate（S′form S）；{從當前回路S產生新回路S′}

Δt：=f（S′））-f（S）；{f（S）為路徑總長}

IF（Δt<0） OR （EXP（-Δt/T）>Random-of-[0，1]）

S=S′；

IF the-halt-condition-is-TRUE THEN

termination=true；

End；

T_lower；

End；

End

3.結語

模擬退火算法在解決TSP問題中顯示了與一般常用算法不同的優越性，具有思路清晰、使用靈活的特點。模擬退火算法可以在較短時間內求得更優近似解，而且允許任意選取初始路徑和隨機數序列，故減少了算法求解路徑的前期工作量。隨著METEOPOLIS規則的引入，使算法在解決問題時不再完全依賴初始路徑，并保證了最終路徑在二鄰域的最優。

參考文獻：

[1]Michael R.Garey，David S.Johnson COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness W.H.FREEMAN AND COMPANY，1979.

[2]高尚.基于Matlab遺傳算法優化工具箱的優化計算.微型電腦應用，2002.

[3]康立山，謝云，尤矢勇，等.模擬退火算法[M].北京：科學出版社，1994：50-97.

文章授江蘇省職業教育教學改革研究課題ZYB56資助。