K-means聚類蟻群優(yōu)化算法求解大型TSP問題

鄭旭峰，周健勇 ZHENG Xufeng,ZHOU Jianyong

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引 言

旅行商問題，即TSP問題（Travelling Salesman Problem）是經(jīng)典組合優(yōu)化問題，其目標(biāo)是求出商人有且僅有一次經(jīng)過N個城市并最后回到原點的最短路徑。當(dāng)問題規(guī)模N較小時，枚舉法是求解TSP的簡單方法。隨著N的增大，該方法顯然在時間和空間上都是不可行的。20世紀(jì)90年代，意大利學(xué)者Dorigo，Maniezzo等人最先提出蟻群算法（Ant Colony Algorithm），并將這種新的啟發(fā)式算法應(yīng)用于TSP、資源二次分配問題等經(jīng)典優(yōu)化問題，得到了較好的效果[1]。

物流配送是TSP問題在物流領(lǐng)域的描述，是現(xiàn)代企業(yè)生產(chǎn)過程中的重要環(huán)節(jié)，其配送速度是決定了獨立的物流團隊以此來保證配送的服務(wù)質(zhì)量。隨著當(dāng)今電子商務(wù)平臺火熱發(fā)展，人們越來越傾向在網(wǎng)上購物，物流公司的經(jīng)營范圍日益擴大，配送對象也成倍增加，從而對配送路徑的選擇產(chǎn)生時間與空間的高復(fù)雜性問題。為了保證配送速度與配送成本，大規(guī)模的物流配送路徑優(yōu)化問題成為重要研究課題?，F(xiàn)實生活中物流配送對象常常具有地域空間特性：如A地區(qū)的若干個小區(qū)距離相近，且都由同一家物流公司配送，B地區(qū)同樣有若干小區(qū)，也有配送任務(wù)，這類物流配送問題帶有明顯的聚類特性。

文獻[2]針對傳統(tǒng)蟻群算法處理TSP問題時易于出現(xiàn)早熟停滯現(xiàn)象，引入局部信息激素及最優(yōu)最差路徑信息激素更新策略，有效抑制早熟停滯，加快算法收斂速度。戚玉濤等[3]通過自適應(yīng)規(guī)約免疫算法，采用多級歸約來求解大規(guī)模TSP問題。文獻[4]將遺傳算法的復(fù)制 、交叉和變異等遺傳算子引入蟻群算法，建立了帶約束條件的物流配送數(shù)學(xué)模型，可以有效而快速地求得問題的最優(yōu)解或近似最優(yōu)解。袁亞博等[5]在求解最短路徑問題上對經(jīng)典蟻群算法提出三方面改進，首先加入方向引導(dǎo)，提高搜索速度，隨后根據(jù)信息素重新分配更新局部濃度，最后引入動態(tài)因子提高算法自適應(yīng)性。文獻[6]以碳排放成本為目標(biāo)函數(shù)，在混沌系統(tǒng)及模擬退火機制上引入基本蟻群算法，研究了低碳物流配送路徑優(yōu)化問題。

盡管以上許多改進的蟻群算法成功應(yīng)用于多個組合優(yōu)化問題，但是仍存在一些不足，這在處理大規(guī)模問題時尤其明顯，如計算時間較長，誤差率增大等。本文針對這類帶聚類特性的TSP問題，提出K-means聚類蟻群算法（K-means Clustering Ant Colony Algorithm）。該算法首先對數(shù)據(jù)集中的城市采用K-means算法進行聚類分析，找出滿足最優(yōu)緊密度的聚類個數(shù)，隨后將大規(guī)模城市集合分成若干個小規(guī)模城市集合，分別運用傳統(tǒng)蟻群算法對其求出最短路徑，最后將這些已求解的小規(guī)模城市集中的出入度城市通過設(shè)定的規(guī)則連接起來，從而完成對原始問題的求解。本文結(jié)合K-means聚類和蟻群算法提出解決大規(guī)模城市集的聚類蟻群算法—K-means蟻群算法（KMACA），并與蟻群聚類蟻群算法（ACACA）和傳統(tǒng)的蟻群算法（ACA）進行比較。

1 算法原理及實現(xiàn)

1.1 KMACA聚類原理

對于求解大規(guī)模的TSP問題，KMACA算法第一步需要確定對大規(guī)模城市集如何聚類。經(jīng)典的K-means算法用于聚類時，若結(jié)果類是密集的，且類與類界限較明顯時，效果較好。該算法對于大規(guī)模數(shù)據(jù)集是相對可伸縮和高效率的[7-8]，因此用K-means算法來對大規(guī)模TSP問題聚類是合理的。

但作為一種無監(jiān)督的知識發(fā)現(xiàn)算法，K-means聚類算法缺點之一是需要事先確定聚類的個數(shù)K，因此在對數(shù)據(jù)分布一無所知的情況下，有必要對不同聚類K做有效性分析，類內(nèi)的凝聚度（Cohesion）和類間的分離度（Separation）通常作為聚類效果的主要特性，好的聚類結(jié)果應(yīng)具有較小的類間凝聚度，同時又具有較大的類間分離度[9]。輪廓系數(shù)指標(biāo)結(jié)合了凝聚度與分離度，具體公式如下：

假設(shè)樣本di聚集到A類，ai代表樣本di與A簇其他樣本的平均距離，令D（ di, ）C 為樣本di與C簇平均距離，則（di, C ）。對某次聚類來說，n為城市數(shù)，K為聚類數(shù)，Sk反應(yīng)了總體平均輪廓系數(shù)。Sk取值介于-1與1之間，值越大，聚類效果越好，本文選取K從2到10依次迭代，選取Si最大值時的K作為聚類個數(shù)。101個城市規(guī)模輪廓系數(shù)迭代效果與K-means聚類效果分別如圖1、圖2所示：

圖1 輪廓系數(shù)圖

圖2 大規(guī)模TSP問題的K-means算法聚類效果圖

從圖1可以發(fā)現(xiàn)以下特征：

（1）整個大規(guī)模數(shù)據(jù)集可以人為聚成K類，設(shè)每類包含的個數(shù)為nk，則有為總體城市規(guī)模個數(shù)，每個類i中都存在一個聚類中心點ci。

（2）對于某一特定類，我們可以用蟻群算法求解出最短路徑，并預(yù)留出入度城市。

（3）為了將最優(yōu)子結(jié)構(gòu)連接起來，設(shè)置一定規(guī)則連接出入度城市。

（4）當(dāng)式（1）中的K＞3時，需要對所分的類進行最短路徑的連接，此時可以對式（1）聚類中心點C1,C2,…,Ck求最短路徑，考慮到K值不會太大，故用傳統(tǒng)的TSP算法可以求解。

1.2 KMACA類內(nèi)連接順序

1.1 節(jié)完成了對大規(guī)模TSP問題的聚類，為了求解原始問題，下一步需要找到每個類中的出入度城市來完成與鄰類的相連。

類的出入度城市選擇對類內(nèi)的城市連接有很大的影響。本文優(yōu)先考慮類內(nèi)的最短路徑，與傳統(tǒng)的TSP問題不同的是，該最短路徑不需要回到起始點，即該路徑是開放的。開放的最短路徑在傳統(tǒng)的TSP最短路徑上需再進一步，對于類中的點集A，不妨設(shè)（m≠n，m,n∈A）為m與n點的距離，設(shè)封閉的最短總路徑為D，類的出入度城市隨機，則開放的類內(nèi)最短路徑為minDmin-，若還存在更短路徑DNEW，連接首尾，因為，因此DNEW+＜Dmin，出現(xiàn)矛盾，則Dmin-就是類內(nèi)最短開放路徑長度，且出入度城市為m和n。

1.3 KMACA類間連接順序

當(dāng)聚類個數(shù)超過3時，不妨設(shè)各類的聚類中心點為C1,C2,…,Ck，為使TSP問題的解最優(yōu)，類與類所連接的邊之和應(yīng)最小。因聚類數(shù)K較小，故用處理小規(guī)模的TSP問題算法對C1,C2,…,Ck進行排列連接即可。

1.4 KMACA類的出入度連接

在以類內(nèi)最短連接距離優(yōu)先的前提下，每類i自然會留下兩個開放點，不妨設(shè)入度城市為，出度城市為，對于第一個類1，其出度城市有兩個選擇，與類1相連的類2，其入度城市有也有兩個選擇，依次類推，K類中類的出入度總的連接方式為2k，迭代即可確定最短的連接方式?？紤]到K值較小，這種指數(shù)型增長仍可接受。整個算法流程如圖3所示：

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

圖3KMACA算法流程圖

2 實驗仿真及分析

2.1 實驗仿真

實驗選用TSP標(biāo)準(zhǔn)數(shù)據(jù)集中的5個實例eil101、pr299、d493、rat575、rat783，通過傳統(tǒng)蟻群ACA算法、KMACA算法與ACACA算法進行對比實驗，運行MATLAB R2010a，在內(nèi)存為4 GB，Intel corei7-3770處理器的PC機上進行模擬仿真。算法參數(shù)設(shè)置如表1所示：

NC_MAX為最大迭代次數(shù)；α表示信息素重要程度，增大α有利于后面的螞蟻吸取前面的經(jīng)驗，但取值過大容易陷入局部最優(yōu)；β表示啟發(fā)式因子重要程度，增大β有利于解的多樣化，探究到更優(yōu)的路徑，過大會使搜尋時間變長；RHO為信息素蒸發(fā)系數(shù)，對于迭代次數(shù)比較大的，敏感程度較小；Q為常系數(shù)，ACACA算法運用蟻群聚類時,設(shè)定迭代次數(shù)達到20 000次聚類即結(jié)束。數(shù)值優(yōu)化設(shè)定參考[10]。本次試驗按照以上參數(shù)對前4種規(guī)模的TSP問題進行了20次，rat783運行了5次，平均實驗結(jié)果如表2所示：

表2 5種規(guī)模下ACA/KMACA/ACACA效果對比

2.2 結(jié)果分析

根據(jù)表2得出的實驗數(shù)據(jù)，分別從算法運行時間與誤差率兩個方面分析比較3種算法的效果。如圖4、圖5所示：

從運行時間上看，3種算法運行時間均和城市規(guī)模呈正相關(guān)，跟最短路徑的長度沒有必然關(guān)系。其中對整個規(guī)模直接求解的ACA算法對數(shù)化后的運行時間與城市規(guī)模呈明顯的線性關(guān)系，如圖6所示：

因此用傳統(tǒng)的ACA算法運行時間T與規(guī)模N的關(guān)系為：

KMACA算法運行時間由聚類時間、各個子類的最短路徑求解時間和連接子類時間組成。仿真實驗中聚類與連接時間在總時間中的比例可忽略不計。因此其運行時間主要與聚類數(shù)K相關(guān)，同一規(guī)模下，聚類數(shù)越多，其速度越快，但聚類數(shù)過多會影響增大結(jié)果誤差，具體K參考1.1節(jié)的最大輪廓系數(shù)。

ACACA算法運行時間組成與KMCAC類似，不同的是蟻群聚類算法對數(shù)據(jù)的要求較少，無需事先確定聚類數(shù)，適用范圍較廣，但產(chǎn)生的問題是聚類時間占比很大，超過了各個子類最短路徑求解時間之和。效果上看，在前兩個eil101、pr299數(shù)據(jù)集中，ACA算法運行時間是KMACA時間10倍左右，在后3個數(shù)據(jù)集中，這個比值達到20倍以上。在ACA算法與ACACA算法對比中，除了第一個數(shù)據(jù)集以外，ACA運行時間是ACACA的2倍。由于ACACA聚類中以迭代次數(shù)為終止條件，因此在小規(guī)模數(shù)據(jù)集中，后面的迭代對聚類效果沒有改進，反而增加了求解時間。因此在運行時間對比上，KMACA算法比另外兩個算法速度快得多。

從誤差率方面看，ACA算法隨著規(guī)模增大而緩慢增加，KMACA算法在eil101規(guī)模上誤差率較大，隨后緩慢下降，ACACA算法的誤差率明顯高于另外兩種算法。由于ACACA與KMACA原理實現(xiàn)的唯一區(qū)別是聚類方式，因此推斷ACACA中的蟻群聚類效果不好，不適合對二維空間上的點進行聚類。對KMACA算法在eil101中的高誤差率分析發(fā)現(xiàn)，eil101數(shù)據(jù)集的最短距離基數(shù)過小，僅為629，導(dǎo)致聚類間相連的距離相對過大，為134.5，因此聚類對小規(guī)模的數(shù)據(jù)集影響過大，分類后的總體距離效果不佳，這也從側(cè)面反映了KMACA算法不是處理小規(guī)模問題的優(yōu)秀算法。

圖4 算法運行時間對比圖

圖5 算法誤差率對比圖

3 結(jié)束語

本文針對傳統(tǒng)ACA算法處理大規(guī)模TSP問題出現(xiàn)的不足，結(jié)合物流配送過程中目的地聚集特征，提出了K-means聚類蟻群算法—KMACA，并與ACACA算法和ACA算法分別從運行時間與誤差率上進行比較。根據(jù)結(jié)果分析，K-means蟻群算法在運行時間上遠好于ACA與ACACA算法，在結(jié)果誤差率上，K-means算法小于ACA算法，而ACACA算法則由于蟻群聚類效果不佳導(dǎo)致誤差率很高?？傮w來講，K-means算法對比傳統(tǒng)的ACA算法在兩個方面均有提升，運行時間上尤其明顯?，F(xiàn)實生活中，盡管能確定適當(dāng)?shù)木垲悢?shù)K，但是該數(shù)量聚類下緊密程度對實驗值與真實值誤差的影響事先難以確定，故其實用性有一定的限制；另外當(dāng)前優(yōu)秀的物流配送常常帶有配送時間的限制，需要考慮時間窗因素，本文未把其考慮在內(nèi)，以后將進一步研究。

圖6 規(guī)模運行時間關(guān)系圖

[1] Tzle T,Dorigo M.ACO algorithms for the quadratic assignment problem[M].McGraw-Hill Ltd.UK,1999.

[2] 張軍英，敖磊，賈江濤.求解TSP問題的改進蟻群算法[J].西安電子科技大學(xué)學(xué)報，2005,32(5):681-685.

[3] 戚玉濤，劉芳，焦李成.求解大規(guī)模TSP問題的自適應(yīng)歸約免疫算法[J].軟件學(xué)報，2008,19(6):1265-1273.

[4] 張維澤，林劍波，吳洪森.基于改進蟻群算法的物流配送路徑優(yōu)化[J].浙江大學(xué)學(xué)報（工學(xué)版），2008,42(4):574-578.

[5] 袁亞博，劉羿，吳斌.改進蟻群算法求解最短路徑問題[J].計算機工程與應(yīng)用，2016,52(6):8-12.

[6] 張立毅，王迎，費騰.混沌擾動模擬退火蟻群算法低碳物流路徑優(yōu)化[J].計算機工程與應(yīng)用，2017,53(1):63-68.

[7] 孫士保，秦克云.改進的k-平均聚類算法研究[J].計算機工程，2007,33(13):200-201.

[8] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報，2008(1):48-61.

[9] 朱連江，馬炳先，趙學(xué)泉.基于輪廓系數(shù)的聚類有效性分析[J].計算機應(yīng)用，2010(s2):139-141.

[10]柳長源，畢曉君，韋琦.基于蟻群算法求解TSP問題的參數(shù)優(yōu)化與仿真[J].信息技術(shù)，2009(4):129-131.