，

(哈爾濱工業(yè)大學(xué)(深圳)，廣東 深圳 518055)

0 引言

旅行商問題屬于NP問題，對于給定N個(gè)城市，旅行商需要從某個(gè)城市出發(fā)，到達(dá)每個(gè)城市一次，且最后回到出發(fā)的城市，求解旅行商遍歷所有的城市所需要的最短封閉路線。普遍采用智能啟發(fā)算法求解旅行商問題，常用的有遺傳算法[1-2]、蟻群算法[3-4]、PSO算法[5-6]和神經(jīng)網(wǎng)絡(luò)[7]等。雖然參考文獻(xiàn)[8]，文獻(xiàn)[5]，文獻(xiàn)[9]的算法，保證了一定的求解質(zhì)量，但存在求解時(shí)間長的問題。

為了解決蟻群優(yōu)化算法求解時(shí)間較長、收斂速度較慢、容易陷入局部最優(yōu)解的缺陷，本文提出了一種基于K-means信息揮發(fā)速率動(dòng)態(tài)調(diào)整的改進(jìn)蟻群算法。

1 改進(jìn)蟻群算法求解TSP

1.1 信息揮發(fā)素率動(dòng)態(tài)調(diào)整改進(jìn)蟻群算法

本文的改進(jìn)蟻群算法在下一城市的選擇上加入了輪盤賭規(guī)則，信息素的更新采用信息素全局更新規(guī)則和信息素局部更新規(guī)則，引入了信息素自適應(yīng)動(dòng)態(tài)調(diào)整策略。每只螞蟻選擇下一城市后即對經(jīng)過的這條邊(i,j)進(jìn)行局部信息素更新。在每輪迭代結(jié)束后，僅對最優(yōu)路徑上的信息素進(jìn)行全局更新。輪盤賭規(guī)則的加入使得蟻群在路徑探索時(shí)增加了隨機(jī)性，避免陷入局部最優(yōu)。

1.1.1 狀態(tài)轉(zhuǎn)移規(guī)則

偽隨機(jī)比例選擇下一城市

(5)

qo為[0,1]區(qū)間內(nèi)的一個(gè)設(shè)定參數(shù)；q為[0,1]區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù)。

當(dāng)產(chǎn)生的隨機(jī)數(shù)q≤q0時(shí)，螞蟻直接選擇使啟發(fā)式信息的指數(shù)α和信息素量的β指數(shù)乘積最大的作為下一個(gè)到達(dá)城市；當(dāng)產(chǎn)生的隨機(jī)數(shù)q>q0時(shí)，改進(jìn)算法采用輪盤賭策略，選擇下一城市為j的概率為

(6)

1.1.2 信息素更新規(guī)則

蟻群算法中，每輪迭代時(shí)路徑構(gòu)建完成后，每只螞蟻都可以釋放信息素。在改進(jìn)算法中，只有最優(yōu)螞蟻才能在路徑構(gòu)建完成后釋放信息素，信息素更新規(guī)則的改進(jìn)加強(qiáng)了算法搜索的導(dǎo)向性。在每輪迭代中，當(dāng)所有螞蟻完成路徑構(gòu)建后，當(dāng)前最優(yōu)路徑上的信息素發(fā)生全局更新。信息素全局更新規(guī)則為

τ(i,j)=(1-ρ)·τ(i,j)+

ρ·Δτb(i,j),?(i,j)∈τb

(7)

(8)

ρ為信息素全局揮發(fā)速率；Δτb(i,j)為至今最優(yōu)螞蟻在邊(i,j)釋放的信息素；Cb為至今最優(yōu)螞蟻構(gòu)建路徑的長度；信息素局部更新規(guī)則為

τ(i,j)=(1-ζ)·τ(i,j)+ξ·τo

(9)

ξ是信息素局部揮發(fā)速率。信息揮發(fā)素是蟻群系統(tǒng)算法中的一項(xiàng)重要參數(shù)。

信息素全局揮發(fā)速率ρ影響蟻群算法的全局搜索能力和收斂速度：當(dāng)ρ過小時(shí)，會使算法的隨機(jī)性能和全局搜索能力下降；當(dāng)ρ過大時(shí)，又會使算法的收斂速度降低。因此，需要合理選擇ρ，保證算法在有較好的全局搜索能力的同時(shí)能較快收斂。本文的改進(jìn)蟻群系統(tǒng)算法提出簡單而有效的自適應(yīng)策略來動(dòng)態(tài)調(diào)整信息揮發(fā)速率ρ，表達(dá)式為

(10)

i為當(dāng)前迭代輪數(shù)；Nmax為最大迭代次數(shù)。初始化時(shí)，給全局信息揮發(fā)速率ρ設(shè)定較小的值ρ0，這時(shí)以前搜索過的路徑被選擇的概率較大，收斂速度比較快。之后隨著迭代次數(shù)增加，逐漸增加ρ至最大值ρmax，信息正反饋的作用被削弱，那些從未被搜索過的路徑上的信息素增加，搜索的隨機(jī)性增強(qiáng)，全局搜索能力提高。

信息揮發(fā)速率動(dòng)態(tài)調(diào)整改進(jìn)蟻群算法具體流程如圖1所示。

圖1 改進(jìn)蟻群算法流程

1.2 基于K-means的改進(jìn)蟻群算法

利用蟻群算法求解大規(guī)模TSP問題存在求解時(shí)間過長的問題，采用“分而治之”的思想，利用簡單易行的K-means算法，將大規(guī)模TSP分體分解為多個(gè)小規(guī)模TSP問題，然后對每個(gè)小規(guī)模TSP問題采用上節(jié)提出的改進(jìn)蟻群算法求解，再將子問題的求解結(jié)果進(jìn)行類間連接，最終得到原大規(guī)模TSP問題的滿意解。

選取TSPlib庫中的eil101作為測試數(shù)據(jù)，數(shù)據(jù)包含了101個(gè)城市的坐標(biāo)。該實(shí)例的輪廓系數(shù)隨聚類數(shù)的變化關(guān)系如圖2所示。聚類數(shù)K=4時(shí)，輪廓系數(shù)最大，即聚類效果最佳。

圖2 輪廓系數(shù)

對每個(gè)小規(guī)模TSP問題采用本文提出的信息揮發(fā)速率動(dòng)態(tài)調(diào)整改進(jìn)蟻群算法求解后，對子問題進(jìn)行類間的連接。對于子問題，首先求解封閉路徑滿意解，在類間連接時(shí)，確定斷開鏈與連接鏈。

采用子區(qū)域最近鄰鄰接方法進(jìn)行類間連接。類間連接所得最優(yōu)路徑的目標(biāo)函數(shù)為

minZ=∑Zk-∑Si+∑Sj

(13)

Zk為子區(qū)域TSP最優(yōu)路徑長度；Si為子區(qū)域連接時(shí)的斷開鏈長度；Sj為子區(qū)域之間的連接鏈長度。

最近鄰鄰接方法的基本思路如下：確定子區(qū)域的連接順序；將相鄰兩簇距離較近的點(diǎn)作為潛在連接點(diǎn)集；對于每2個(gè)相鄰子區(qū)域，在其潛在連接點(diǎn)集中選擇出入度點(diǎn)，確定斷開鏈和連接鏈；由式(10)計(jì)算最優(yōu)路徑長度，得到原有大規(guī)模TSP問題的滿意解。

對于TSPlib實(shí)例eil101，城市數(shù)為101輪廓系數(shù)最優(yōu)時(shí)的聚類個(gè)數(shù)為4，因此簇?cái)?shù)設(shè)置為4個(gè)；每簇的螞蟻個(gè)數(shù)設(shè)置為與每簇的城市數(shù)相等。其他參數(shù)的設(shè)置如表1所示。

表1 改進(jìn)蟻群算法參數(shù)設(shè)置

采用TSPlib庫中eil101實(shí)例進(jìn)行聚類和子問題優(yōu)化路徑求解的結(jié)果如圖3所示。

4個(gè)子區(qū)域進(jìn)行類間連接后的優(yōu)化路徑求解結(jié)果如圖4所示。采用Berlin52和ch130對改進(jìn)算法進(jìn)行測試。改進(jìn)算法循環(huán)次數(shù)設(shè)定為50次。實(shí)例Berlin52中有52個(gè)城市的坐標(biāo)數(shù)據(jù)，其最優(yōu)解為7 544.37。采用改進(jìn)算法求解，得到最短路徑為7 544.37，最長路徑為7 807.57，平均路徑長度為7 604.65。實(shí)例ch130中有130個(gè)城市的坐標(biāo)數(shù)據(jù)，其最優(yōu)解為6 110。最短路徑為6 269.15，最長路徑為6 586.33，平均路徑長度為6 383.95。改進(jìn)算法連續(xù)運(yùn)行15次后所得的路徑長度結(jié)果分別如圖5和圖6所示。

圖3 eli101聚類子問題求解

圖4 eil101聚類連接示意

圖5 改進(jìn)算法求解Berlin52路徑長度

圖6 改進(jìn)算法求解ch130路徑長度

算法的平均解和最優(yōu)解相比TSPlib庫中已知的最優(yōu)解的偏差百分比可由式(14)和式(15)得出，自適應(yīng)信息素調(diào)節(jié)的改進(jìn)蟻群系統(tǒng)算法在Berlin52上測試后得到的偏差百分比分別為 0.799%和0.000%，在ch130上測試后得到的偏差百分比分別為4.484%和2.600%，即

(14)

(15)

2 實(shí)驗(yàn)驗(yàn)證

將基本蟻群算法ACO與本文改進(jìn)的蟻群算法進(jìn)行對比，選擇國際上通用的TSP lib數(shù)據(jù)集中的實(shí)例作為測試數(shù)據(jù)。基本蟻群算法的參數(shù)設(shè)置如表2所示。設(shè)置螞蟻數(shù)和城市數(shù)相等。對于本文改進(jìn)的蟻群算法，設(shè)置每簇的螞蟻個(gè)數(shù)與簇內(nèi)城市數(shù)相等。其他參數(shù)如表1所示。2種算法均對測試實(shí)例重復(fù)運(yùn)行15次，實(shí)驗(yàn)結(jié)果如表3所示。其中算法1為本文提出的改進(jìn)ACO算法，算法2為ACO算法。

表2 蟻群算法參數(shù)設(shè)置

表3 改進(jìn)ACO與ACO測試對比

改進(jìn)蟻群算法所得到的最優(yōu)解均優(yōu)于蟻群算法如圖7所示。2種算法運(yùn)行時(shí)間對比情況如圖8所示。由圖8可知，隨著城市數(shù)的增加，在求解時(shí)間上改進(jìn)的蟻群算法明顯少于蟻群算法，平均減少約62.9%左右。城市數(shù)達(dá)到280時(shí)，改進(jìn)蟻群算法的求解時(shí)間相比蟻群算法能減少76.6%。

圖7 優(yōu)化路徑長度對比

圖8 算法運(yùn)行時(shí)間對比

選取TSPlib庫中的ch150實(shí)例進(jìn)行測試。參數(shù)設(shè)置城市數(shù)N=150，螞蟻數(shù)量m=150，其他參數(shù)同表1。重復(fù)進(jìn)行5次，得到如圖9所示的路徑長度隨迭代次數(shù)變化的收斂曲線。由圖9可知改進(jìn)算法在前100次收斂速度較快，在400次左右基本收斂。

圖9 改進(jìn)蟻群算法的收斂性

蟻群算法的參數(shù)設(shè)置同表1。2種算法的收斂性對比如圖10所示。由圖10可知在迭代初期，改進(jìn)蟻群算法和蟻群算法均能快速收斂，在迭代次數(shù)達(dá)到600后，兩者基本收斂，但改進(jìn)蟻群算法得到的有效解明顯優(yōu)于改進(jìn)蟻群算法得到的有效解，避免了陷入局部最優(yōu)。

圖10 改進(jìn)蟻群算法與蟻群算法的收斂性對比

3 結(jié)束語

本文提出基于K-means信息揮發(fā)速率動(dòng)態(tài)調(diào)整的改進(jìn)蟻群算法，通過動(dòng)態(tài)調(diào)整蟻群的信息揮發(fā)速率，避免了蟻群陷入局部最優(yōu)路徑，同時(shí)加快了算法收斂。采用分治方法，將大規(guī)模TSP問題分解為數(shù)個(gè)子問題，大大減少了求解時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法在求解最優(yōu)路徑和求解時(shí)間上均優(yōu)于蟻群算法，所得的最優(yōu)路徑長度平均減少約10.0%，求解時(shí)間平均降低約62.9%，能較好地適用于求解TSP問題。