一種求解TSP的智能水滴改進(jìn)算法

張　峰

(安徽交通職業(yè)技術(shù)學(xué)院　水運(yùn)工程系，合肥　230051)

?

一種求解TSP的智能水滴改進(jìn)算法

張峰

(安徽交通職業(yè)技術(shù)學(xué)院水運(yùn)工程系，合肥230051)

摘要:智能水滴算法是模擬自然界中水滴群體和它附近環(huán)境相互作用，最終形成河道的過程而被研究者提出的一種新興的智能優(yōu)化算法。旅行商問題(TSP)是數(shù)學(xué)當(dāng)中組合優(yōu)化問題之一，也是一Non-deterministic Polynomial(NP)完全問題。針對智能水滴算法的缺陷提出了改進(jìn)的智能水滴算法——具有變異特征的智能水滴算法，并用TSP問題來驗(yàn)證改進(jìn)算法的可行性和有效性。經(jīng)過分析發(fā)現(xiàn)該改進(jìn)的算法對比之前的基本智能水滴算法具有很強(qiáng)的全局搜索能力，對順利找到最短路徑解決實(shí)際問題具有非常大的意義的。

關(guān)鍵詞:TSP問題；智能水滴算法；組合優(yōu)化；變異特征

1知識準(zhǔn)備

隨著經(jīng)濟(jì)的快速發(fā)展，道路負(fù)荷日益加重，交通擁擠。人們生產(chǎn)經(jīng)濟(jì)利潤的提高以及消費(fèi)者生活水平的提高，都對生鮮農(nóng)產(chǎn)品的流通提出更高要求，進(jìn)而就會要求旅行商在眾多路線當(dāng)中選擇一條最短路徑進(jìn)行送貨，達(dá)到消費(fèi)者的滿意度。因此，在很多學(xué)科(如計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)等)中，最短路徑問題漸漸成為一個(gè)研究熱點(diǎn)。

旅行商問題(Traveling Saleman Problem, TSP)是數(shù)學(xué)當(dāng)中組合優(yōu)化問題之一，也屬于一完全NP難題(非多項(xiàng)式算法問題)，被廣泛的應(yīng)用在很多領(lǐng)域里，是一種優(yōu)化問題的集中概括和簡化形式[1]。并且還經(jīng)常用來作為許多種啟發(fā)式算法的間接性的比較標(biāo)準(zhǔn)，所以我們一般在TSP上來驗(yàn)證某種算法的性能，假如能夠得到比較好的性能，則在別的相似的優(yōu)化組合問題上往往也能取得到很好的結(jié)果。

1932年K.Menger提出TSP問題，該問題是求解最小路徑成本問題，可以描述為一旅行商從起始點(diǎn)出發(fā)，遍歷所有已知給定的需求點(diǎn)之后，最終再回到起始點(diǎn)的最小路徑成本[2-3]。許多數(shù)學(xué)家對其產(chǎn)生了興趣，但是到目前為止，還未找到最好的求解方法，一直還處在研究當(dāng)中。Shah-Hosseini于2007年第一次使用智能水滴算法解決TSP問題，接著于2008年提出針對TSP問題改進(jìn)的智能水滴算法，并利用因特網(wǎng)上的TSP庫TSPLIB95進(jìn)行驗(yàn)證，結(jié)果說明智能水滴算法能夠較好地接近最優(yōu)解[4]。2009年Hamed Shah Hosseini闡述了一種自然群智能算法——智能水滴算法；Iman Kamkar等人在2010年使用智能水滴算法解決VRP問題[5]；2012年，我國學(xué)者張宏濱用智能水滴算法解決了在通信中的問題；2013年，周季華,葉春明研究了智能水滴算法置換流水線調(diào)度問題[6]；2014年，馬竹根對智能水滴算法做了研究綜述。然而在國內(nèi)還沒有學(xué)者用智能水滴算法解決TSP問題[6]。

早期的研究者在求解TSP問題時(shí)經(jīng)常使用經(jīng)典算法，但是隨著問題規(guī)模(走訪的城市增多)的增大，用經(jīng)典算法解決此類問題就會變得很棘手，求解此類問題所需要的時(shí)間相應(yīng)的就會很長。所以，在隨后的研究中，學(xué)者重點(diǎn)研究近似算法或啟發(fā)式算法在TSP問題中的應(yīng)用。由于群智能算法(遺傳算法、蟻群算法等)的群體搜索能力很強(qiáng)，但是此類算法可能會陷入搜索局部最優(yōu)解得問題，有可能不能找到全局的最優(yōu)解。鑒于以上原因，許多學(xué)者為了克服這個(gè)缺陷，常常將局部搜索算法和群智能算法結(jié)合研究出更高效的混合算法，克服以上算法的缺陷，采用相結(jié)合的算法求解TSP問題。本文介紹了組合優(yōu)化算法的一種新的求解法——智能水滴算法。因智能水滴算法存在的缺陷以致在解決大規(guī)模旅行商問題時(shí)會使其處理的速度下降，本研究針對智能水滴算法在求解實(shí)際問題方面的缺陷進(jìn)行修正，用TSP問題來驗(yàn)證改進(jìn)算法的可行性和有效性。對順利找到最短路徑解決實(shí)際問題具有非常大的意義的。

(1)

一般地，TSP的數(shù)學(xué)模型可以描述為

(2)

(3)

(4)

式 (1)表示的是距離之和，式(2)約束旅行者恰好從城市i走出來，式(3)約束旅行者恰好進(jìn)入城市j一次，式(2)、(3)結(jié)合一起代表任何一個(gè)城市僅被訪問一次，式(4)中的決策變量xij=1表示旅行者走訪的路線包括城市i到城市j的路徑, xij=0表示旅行者沒有選擇走訪從城市i到城市j的路徑。

2一種改進(jìn)的TSP問題智能水滴算法

2.1智能水滴算法的基本模型

智能水滴(IWD)具備兩個(gè)重要的屬性：我們一般用soil(IWD)表示水滴本身攜帶的泥土量，用velocity(IWD)表示水滴向前流動(dòng)行進(jìn)時(shí)本身具有的速度。在工程問題中，我們亟待解決的問題可以用智能水滴流動(dòng)時(shí)周圍的環(huán)境替代，而我們解決工程問題找到的最優(yōu)路徑可以用相互作用智能水滴尋找的最短路徑替代，在尋找最優(yōu)路徑的過程中，智能水滴具有的兩項(xiàng)重要屬性即soil(IWD)和velocity(IWD)是不斷變化的[9]。

以TSP為例說明Shah-Hosseini等人提出的水滴群系統(tǒng)(Intelligent Water Drop)模型，在TSP中，目標(biāo)是極小化

(5)

其中，d(Cx,Cy)代表兩城市x、y之間的路程。設(shè)bi(t)代表t時(shí)刻處在城市i的水滴數(shù)量，soilij(t)代表t時(shí)刻路徑(i,j)上的泥土量濃度，n為TSP規(guī)模，m為水滴群中水滴的總數(shù)目，即

在初始時(shí)刻各條路徑上泥土量濃度相等，設(shè)soilij(0)=C，C為常量。水滴k(k=1,2,…m)在行進(jìn)過程中，其轉(zhuǎn)移方向依據(jù)各條路徑上的泥土量濃度來決定。而水滴k當(dāng)前所走過的城市用禁忌表tabuk(k=1,2,…,m)來記錄，集合隨著tabuk進(jìn)化過程不斷地作出調(diào)整。在搜索過程中用每條路徑上的泥土量濃度來計(jì)算狀態(tài)轉(zhuǎn)移概率。為了避免殘留泥土量過多引起殘留泥土量所啟發(fā)的信息被淹沒。由此，城市t+n時(shí)刻在路徑(i,j)上泥土量可按照如下規(guī)則進(jìn)行調(diào)整[9]。

soilij(t+n)=ρ0*soilij(t)+ρn*Δsoilij(t)

(6)

式中：ρ0代表信息素?fù)]發(fā)系數(shù)，則ρn=1-ρ0代表信息素殘留因子，為了防止信息的無限積累，規(guī)定：ρ0?[0,1]。

2.2改進(jìn)智能水滴算法的提出

2011年，M.E、L.ThangaMariappan M.E和D.ArunShunmugam M.E提出一種改進(jìn)的智能水滴算法用來解決TSP問題，它與先前的智能水滴算法的不同之處在于改進(jìn)的算法在水滴移動(dòng)搜索最短路徑時(shí)，不僅局部對路徑之間的泥土量進(jìn)行了更新，而且對所有水滴遍歷整個(gè)節(jié)點(diǎn)后，所有節(jié)點(diǎn)之間泥土量都進(jìn)行了全局的更新變化，其表達(dá)式如下：

(1)智能水滴算法改進(jìn)的思想。

提出了一種改進(jìn)的算法——具有變異特征的智能水滴算法。

設(shè)某滴水滴所走線路可以表示為：

如果滿足：

與智能水滴算法中的迭代過程相比，變異的這個(gè)過程用到的運(yùn)算量更為簡便，因此在運(yùn)算量上減少了時(shí)間，并且目前的最優(yōu)解的性能在這種變異算子作用后，便得到明顯的改善，進(jìn)而使整個(gè)群體的性能得以提高，節(jié)省了時(shí)間，提高了算法的收斂速度。此部分的算法可以用偽代碼表示為begin，初始化;

ncycle=0;

bestcycle=0;

soil(i,j)=C;

Δsoil(i,j)=0;

tabuk={};

while(not termination condition)

{

ncycle=ncycle+1;

for(index=0:index

/* index 表示已走城市的個(gè)數(shù)*/

選擇城市j;

將最好的路徑和最好的結(jié)果輸出

把以上兩種改進(jìn)算法的核心思想相結(jié)合，可知改進(jìn)的算法不僅可以將基本智能算法的收斂速度得以提高，而且還能搜索到全局最優(yōu)解，提高解的質(zhì)量。

(2)改進(jìn)智能水滴算法求解TSP步驟。

第一步：靜態(tài)參數(shù)的初始化。可定義水滴的數(shù)量NIWD是一個(gè)正整數(shù)，并且一般情況下，與城市的個(gè)數(shù)Nc相等。對于速度變化的參數(shù)av,bv,cv，可定義av=1，bv=0.01，cv=1。對于泥土量的更新參數(shù)as,bs,cs，可定義as=1，bs=0.01，cs=1。局部泥土量更新參數(shù)ρn=0.9，全局泥土量更新參數(shù)ρIWD，一般在[-1,0]區(qū)間內(nèi)取值，令ρIWD=-0.9.另外，初始狀態(tài)下得每兩個(gè)城市之間的泥土量初始化為InitSoil=1000，初始狀態(tài)下的水滴本身具有的速度初始化為InitVel=4。這個(gè)最優(yōu)解TTB被定義為q(TTB)=-∞，最大迭代次數(shù)用itmax表示[10-12]。

第二步：動(dòng)態(tài)參數(shù)的初始化。對于每一個(gè)水滴，一個(gè)被訪問過的節(jié)點(diǎn)Vc(IWD)被放在一個(gè)空的矩陣中的，用Vc(IWD)={},每一個(gè)水滴的初始速度定義為InitVel和每一個(gè)水滴本身攜帶的泥土量定義為0.

第三步：對于每一個(gè)水滴，它們都是自由選擇下一個(gè)節(jié)點(diǎn)。

第四步：對被訪問過的節(jié)點(diǎn)，我們要更新禁忌表tabulist={}，被訪問過的節(jié)點(diǎn)要依次加進(jìn)這個(gè)表格中。

對任一水滴而言，從節(jié)點(diǎn)i走到節(jié)點(diǎn)j，其更新水滴具有的速度，其表達(dá)式為：

這里velIWD(t+1)是水滴更新過的速度。計(jì)算此時(shí)兩個(gè)節(jié)點(diǎn)之間減少的泥土量Δsoil(i,j)

此式中的

第六步：找出最優(yōu)解(即最短路徑)

第七步:設(shè)某滴水滴所走線路可以表示為

然后引入變異機(jī)制，并運(yùn)用2-opt簡便高效的特點(diǎn)，來代替水滴群的多次迭代循環(huán)來尋找最優(yōu)解，這樣的變換可以節(jié)省時(shí)間，加快收斂速度。如果滿足：

進(jìn)行的主要的操作為：Inversion(S1,S2,Inversion)。

3仿真實(shí)驗(yàn)

為了說明此改進(jìn)的算法具有實(shí)用性和可操作性，選用一組城市，它們的坐標(biāo)見表1。為了方便，在此選用簡單的TSP模型，應(yīng)用10個(gè)點(diǎn)之間坐標(biāo)。先創(chuàng)建一個(gè)二維坐標(biāo)軸。在坐標(biāo)軸上恰當(dāng)?shù)倪x擇10個(gè)點(diǎn)，描繪10個(gè)城市。將這10個(gè)點(diǎn)所在坐標(biāo)軸的坐標(biāo)分別給出。以備主函數(shù)調(diào)用文本文件中點(diǎn)得坐標(biāo)的坐標(biāo)軸位置進(jìn)行計(jì)算兩個(gè)之間的路徑距離建立個(gè)表格，如表1所示。

表1　城市坐標(biāo)

運(yùn)用MATLAB編程，參數(shù)選用av=1，bv=0.01，cv=1。對于泥土量的更新參數(shù)as,bs,cs，定義as=1，bs=0.01，cs=1。InitVel=4，InitSoil=1 000。通過計(jì)算機(jī)仿真，得出實(shí)驗(yàn)結(jié)果如下所示：

tabu_list =

8 910 1 3 2 4 5 6 7

3 210 9 8 7 6 5 4 1

2 3 110 9 8 7 6 5 4

10 9 8 7 6 5 4 1 3 2

910 7 8 6 5 4 1 3 2

6 7 8 910 1 3 2 4 5

7 8 910 1 3 2 4 5 6

5 4 1 3 210 9 8 7 6

4 5 6 7 8 910 1 3 2

1 3 210 9 8 7 6 5 4

2 3 110 9 8 7 6 5 4

10 9 8 7 6 5 4 1 3 2

5 4 1 3 210 9 8 7 6

4 5 6 7 8 910 1 3 2

1 3 210 9 8 7 6 5 4

8 910 1 3 2 7 6 5 4

6 7 8 910 1 3 2 4 5

910 1 3 2 4 5 6 7 8

3 210 9 8 7 6 5 4 1

7 8 910 1 3 2 4 5 6

4 8 910 7 6 5 1 3 2

7 8 910 1 3 2 4 5 6

910 1 3 2 4 5 6 7 8

8 7 6 5 4 1 3 210 9

2 3 110 9 8 7 6 5 4

10 9 8 7 6 5 4 1 3 2

3 2 110 9 8 7 6 5 4

6 7 8 910 1 3 2 4 5

5 4 1 3 210 9 8 7 6

110 9 8 7 6 5 4 3 2

5 6 7 8 910 1 3 2 4

shortest_path =

10 9 8 7 6 5 4 1 3 2(見圖1)

shortest_length =

270.273 2(見圖2)

從上面的結(jié)果可以看出，這幾個(gè)城市的最短路徑為270.273 2，依次遍歷的城市為

J→I→H→G→F→E→D→A→C→B

圖1 表示改進(jìn)水滴算法迭代3次遍歷10個(gè)城市的軌跡

圖2 表示改進(jìn)水滴算法迭代3次搜索10個(gè)城市最短路徑的收斂性

仿真實(shí)驗(yàn)表明：改進(jìn)的算法相比基本算法而言，它總是可以找到可以實(shí)現(xiàn)并最優(yōu)化的路徑，但基本的智能算法無法實(shí)現(xiàn)這一點(diǎn)；改進(jìn)的算法在收斂速度以及求最優(yōu)解方面比基本的智能水滴算法更有效，并且該算法使求最優(yōu)解的能力進(jìn)一步加強(qiáng)，防止算法陷入局部最優(yōu)。

當(dāng)城市的規(guī)模問題小的時(shí)候，改進(jìn)的算法較最初算法的收斂快的優(yōu)勢表現(xiàn)的并不明顯，即最原始的算法就可以解決城市規(guī)模較小的最短路徑問題。但當(dāng)城市的規(guī)模相當(dāng)大時(shí)，改進(jìn)的算法的優(yōu)勢就會展現(xiàn)出來。

4研究結(jié)論

智能水滴算法是模擬自然界中水滴群體和它附近環(huán)境相互作用最終形成河道的過程而被研究者提出的一種新興的智能優(yōu)化算法。在工業(yè)、農(nóng)業(yè)、科研等領(lǐng)域都有該算法的廣泛應(yīng)用。本文針對智能水滴算法的缺陷提出了改進(jìn)的智能水滴算法——具有變異特征的智能水滴算法。為了證實(shí)該改進(jìn)的智能水滴算法的有效性和可行性，本文將改進(jìn)的智能水滴算法在實(shí)際問題中加以運(yùn)用，用TSP問題來驗(yàn)證改進(jìn)算法的可行性和有效性。選用了一個(gè)10個(gè)城市規(guī)模的問題，用水滴算法和改進(jìn)的水滴算法進(jìn)行求解[12]，得出在問題規(guī)模較小時(shí)，兩種算法尋找的最優(yōu)解一樣，所需要的時(shí)間幾乎沒有差異，改進(jìn)的水滴算法沒有發(fā)現(xiàn)出很大的優(yōu)勢。經(jīng)過分析，該改進(jìn)的算法對比之前的基本智能水滴算法具有很強(qiáng)的全局搜索能力，對順利找到最短路徑解決實(shí)際問題具有非常大的意義的，大大地提高了算法的收斂速度。

參考文獻(xiàn)：

[1]孫亦冰. 基于實(shí)時(shí)路況的城市道路動(dòng)態(tài)路由研究[D].武漢: 華中科技大學(xué)控制科學(xué)與工程系,2009.

[2]劉云翔.最短路徑分析及GIS/GPS集成技術(shù)研究[D].長沙: 國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院,2002,1.

[3]Hamed Shah-Hosseoni.Intelligent Water Drops Algorithm: A New Optimization Method for Solving the Multiple Knapsack Problem[J].International,2008,1(2): 193-212.

[4]勞眷.TSP問題中的蟻群優(yōu)化算法研究[D].長沙: 湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,2007.

[5]李洪海.基于移動(dòng)機(jī)器人的雙目立體視覺技術(shù)研究[D].南京: 南京航空航天大學(xué)自動(dòng)化學(xué)院,2011.

[6]馬竹根.智能水滴算法研究[J].懷化學(xué)院計(jì)算機(jī)工程系,2014(6): 964-968.

[7]胡中功,李靜.群智能算法的研究進(jìn)展[J].控制理論與應(yīng)用,2008(2): 13-15.

[8]Kamkar I,Akbarzadeh-T M R,Yaghoobi M.Intelligent Water Drops a New Optimization Algorithm for Solving the Vehicle Routing Problem[C]//Systems Man Cybernetics(SMC),2010 IEEE International Conference on IEEE,2010: 4142-4146.

[9]周季華,葉春明,盛曉華.基于智能水滴算法置換流水線調(diào)度問題的研究[J].計(jì)算機(jī)科學(xué),2013,40 (9): 250-253.

[10] 李至立.船舶制造車間作業(yè)管理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].黑龍江: 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)與科學(xué)技術(shù)學(xué)院,2011.

[11] 李翼.物流中心選址問題的分支定界法研究[D].山東: 山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,2012.

[12] YANG Fan.A Study on the Intelligent Water Drop Based Routing Technique for Mannet[D].Beijing: Beijing University of Posts and Telecommunications，School of Information and Communication Engineering,2011.

[責(zé)任編輯：張永軍]

An Improved Algorithm to Solve TSP Problem of Intelligent Water Droplets

ZHANG Feng

(Department of Water Engineering, Anhui Communications Vocational & Technical College,Hefei 230051,China)

Abstract:the intelligent water drop algorithm is a new kind of intelligent optimization algorithm, which put forward by researchers.It is because that this algorithm simulates the interaction between water droplets in nature and its environment,and eventually forms the river. Traveling salesman problem (TSP) is one of the combination optimization problems in mathematics, and it is also a complete problem of NP. In this paper, an improved intelligent water drop algorithm, which has the characteristic of variation, is proposed to improve the intelligent water drop. The feasibility and effectiveness of the improved algorithm is verified by using TSP. Through the analysis, it is found that the improved algorithm has a strong global search ability, and it has a very large significance to the smooth path to solve the actual problem.

Key words:TSP problem; intelligent drop algorithm; combination optimization; variation characteristic

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A

文章編號：1673-162X(2016)01-0023-07

作者簡介：張峰(1981—)，男，安徽蕭縣人，安徽交通職業(yè)技術(shù)學(xué)院水運(yùn)工程系講師，碩士；研究方向：基礎(chǔ)數(shù)學(xué)、計(jì)算數(shù)學(xué)。

基金項(xiàng)目：：2016年高校優(yōu)秀青年人才支持計(jì)劃重點(diǎn)項(xiàng)目(編號gxyqZD2016484)階段性成果。

收稿日期：2015-10-05修回日期：2015-12-20