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

張育藺

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

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

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

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

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

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

2.模擬退火算法

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

2.1模擬退火算法的模型

模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。

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

2.2在TSP問題中的應(yīng)用

2.2.1解空間與初始解

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

2.2.2目標(biāo)函數(shù)

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

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

2.2.3新解的產(chǎn)生

采用二鄰域法這樣一種改進(jìn)的相鄰狀態(tài)變換方法。如下圖所示，設(shè)（s，f）是討論問題的一個(gè)實(shí)例，而n■是一個(gè)二變換領(lǐng)域結(jié)構(gòu)，則二變換n■（p，q）可看成是城市p與q間路徑的反向接入。

圖1 路徑變換

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

2.2.4隨機(jī)移動(dòng)準(zhǔn)則

采用METROPOLIS準(zhǔn)則，由隨機(jī)移動(dòng)接受概率

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

上式中：t為控制參數(shù)，確定是否接受從當(dāng)前解i到新解j的轉(zhuǎn)移。計(jì)算開始時(shí)t取較大值（與固體的熔解溫度相對(duì)應(yīng)），在進(jìn)行足夠多的轉(zhuǎn)移后，緩慢減小t值（與“徐徐”降溫相對(duì)應(yīng)），如此重復(fù)，直至滿足某個(gè)停止準(zhǔn)則時(shí)計(jì)算終止。

2.2.5算法描述

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

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

（2）如果滿足METROPOLIS準(zhǔn)則，則更換路徑的行走方式，否則重復(fù)過程（1）；

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

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

在程序中，隨機(jī)數(shù)發(fā)生器確定之后，需要經(jīng)過多次實(shí)際選取合適溫度計(jì)劃表中的各個(gè)參數(shù)，包括控制參數(shù)t及其衰減函數(shù)α，對(duì)應(yīng)MAPKOB鏈的長度本程序選擇如下：

（1）控制參數(shù)t=0.5；

（2）衰減函數(shù)α=0.95；

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

根據(jù)上述分析，可寫出用模擬退火算法求解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）；{從當(dāng)前回路S產(chǎn)生新回路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.結(jié)語

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

參考文獻(xiàn)：

[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遺傳算法優(yōu)化工具箱的優(yōu)化計(jì)算.微型電腦應(yīng)用，2002.

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

文章授江蘇省職業(yè)教育教學(xué)改革研究課題ZYB56資助。