基于聚類集成的蟻群算法求解大規(guī)模TSP問題

葉家琪，符 強(qiáng)，2，賀亦甲，葉 浩

(1.寧波大學(xué)科學(xué)技術(shù)學(xué)院，浙江 寧波 315212； 2.寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江 寧波 315211)

0 引 言

TSP問題又稱貨郎擔(dān)問題。該問題描述的是由旅行商人拜訪給定的城市，而每個(gè)城市必須經(jīng)過且只能訪問一次，最后回到第一次拜訪的城市從而完成旅行，為滿足該條件旅行商人有多種不同的路線選擇，求解TSP問題是為了找出所有路線中具有最短距離的路線。當(dāng)代的車輛路徑規(guī)劃、物流配送等問題都屬于生活中常見的TSP問題。對(duì)該問題的求解方法可概括為精確算法和群智能算法。精確算法的目的是為了找到問題的最優(yōu)解，然而該算法在求解問題時(shí)的復(fù)雜度大，對(duì)計(jì)算機(jī)的性能要求很高，且隨著TSP問題數(shù)據(jù)規(guī)模的擴(kuò)大，求解問題的時(shí)間呈指數(shù)增長。故同時(shí)考慮到在求解TSP問題時(shí)的時(shí)間與精度，更多是運(yùn)用群智能算法求取問題的近似解。常見的群智能算法有ACA[1-6]、GA(Genetic Algorithm)[7-9]以及PSO(Particle Swarm Optimization)[10-12]。在這些群智能算法中，蟻群算法具有魯棒性強(qiáng)、求解組合優(yōu)化問題效率高的特點(diǎn)，故被廣泛應(yīng)用于解決TSP問題。

但在處理具有較大規(guī)模數(shù)據(jù)的TSP問題時(shí)，蟻群算法具有時(shí)間復(fù)雜度大、搜索結(jié)果精度低、求解效率不強(qiáng)等問題。文獻(xiàn)[13]針對(duì)蟻群算法求解TSP問題搜索時(shí)間長、易出現(xiàn)早熟停滯現(xiàn)象，利用變參數(shù)選擇城市策略,并且在交叉策略中選擇PMX(Partially Matched Crossover)交叉策略，從而減小了算法運(yùn)行時(shí)間，提高了算法效率。文獻(xiàn)[14]通過對(duì)信息素進(jìn)行方向引導(dǎo),并通過對(duì)信息素重新分配，在全局引入動(dòng)態(tài)因子，使得最后問題的結(jié)果更為精確。文獻(xiàn)[15]提出了一種改進(jìn)信息素二次更新局部優(yōu)化蟻群算法解決蟻群算法收斂速度慢、容易陷入局部最優(yōu)的缺陷。盡管以上文獻(xiàn)對(duì)蟻群算法的改進(jìn)可以有效解決數(shù)據(jù)規(guī)模較大的TSP問題，但是仍有不足。若數(shù)據(jù)規(guī)模再繼續(xù)擴(kuò)大，城市數(shù)目達(dá)到幾百甚至幾千時(shí)，算法求解TSP問題的效果便會(huì)越來越差，求解時(shí)間長，誤差率增大。

因此針對(duì)該現(xiàn)象，本文提出一種基于聚類集成[16-19]的蟻群算法?；诟倪M(jìn)聚類集成的蟻群算法采用了“分合治之”的思想，“分”是利用AP聚類[20-23]將大規(guī)模TSP問題分為若干子問題，并對(duì)每個(gè)子問題用蟻群算法進(jìn)行尋優(yōu)，“合”是利用改進(jìn)的集成方案對(duì)子問題進(jìn)行組合。最后，分別將蟻群算法、基本集成聚類的蟻群算法以及基本改進(jìn)集成聚類的蟻群算法對(duì)TSP的標(biāo)準(zhǔn)數(shù)據(jù)庫進(jìn)行測試，將各算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。所得結(jié)果表明，相比于傳統(tǒng)蟻群算法，基本改進(jìn)集成聚類的蟻群算法在求解大規(guī)模TSP問題時(shí)求解時(shí)間短，改進(jìn)的集成方案使該算法的求解質(zhì)量也得以保證。

1 算法原理及簡介

1.1 蟻群算法

自然界中螞蟻會(huì)根據(jù)前面走過的其他螞蟻所留下的信息素對(duì)接下來要走的路徑進(jìn)行選擇。一條路徑的信息素濃度越強(qiáng)，螞蟻選擇該路徑的概率越高。因此，在由大量螞蟻組成的群體的路徑尋優(yōu)過程中，形成一種信息學(xué)習(xí)的正反饋現(xiàn)象。即某一條路徑走過的螞蟻越多，后邊的螞蟻選擇該路徑的概率越大。螞蟻的個(gè)體便通過信息素的反饋尋求通向食物的最短路徑。蟻群算法解決TSP問題的傳統(tǒng)方案可簡要概括如下：

Step1在初始時(shí)刻，把m只螞蟻隨機(jī)放在n個(gè)城市中，信息素初始值設(shè)為0。

Step2用dij(i,j=0,1,…,n-1)表示城市i和城市j之間的距離，螞蟻k(k=1,2,3，…，m)選擇下一個(gè)城市的轉(zhuǎn)移概率如公式(1)所示：

(1)

公式(1)中，τij(t)表示邊(i,j)上的信息素，allowedk表示可供螞蟻k下一步選擇的所有城市的集合；α為信息啟發(fā)式因子，表示路徑上的信息素濃度對(duì)螞蟻選擇路徑所起的影響程度；β為期望啟發(fā)式因子，表示能見度的相對(duì)重要性。

Step3為了讓每個(gè)城市僅訪問一次，用禁忌表tabuk記錄螞蟻k已經(jīng)走過的路徑。在m只都訪問完n個(gè)城市并回到出發(fā)城市時(shí)，保留最優(yōu)路徑，并更新信息素。信息素按公式(2)和公式(3)更新：

τij(t+n)=(1-ρ)×τij(t)+Δτij(t)

(2)

(3)

Step4若算法達(dá)到了結(jié)束要求，輸出最優(yōu)路徑以及長度。

1.2 AP聚類

AP聚類算法是2007年Frey和Dueck在Science雜志上提出的一種新的聚類算法。對(duì)于N個(gè)數(shù)據(jù)點(diǎn)，AP聚類算法可以對(duì)這些點(diǎn)之間的相似度進(jìn)行聚類。這些相似度組成N×N的相似度矩陣S。AP聚類算法不需要事先指定聚類數(shù)目,相反它將所有的數(shù)據(jù)點(diǎn)都作為潛在的聚類中心,并在迭代的過程不斷搜索合適的聚類中心,自動(dòng)從數(shù)據(jù)點(diǎn)間識(shí)別聚類中心的位置以及個(gè)數(shù)，使所有的數(shù)據(jù)點(diǎn)到最近的聚類代表點(diǎn)的相似度之和最大。AP聚類的算法流程如下：

Step1建立相似度矩陣S，計(jì)算數(shù)據(jù)點(diǎn)i和數(shù)據(jù)點(diǎn)j之間相似度s(i,j)。2個(gè)數(shù)據(jù)點(diǎn)間的相似度大小用歐氏距離的負(fù)數(shù)表示，如公式(4)所示：

s(i,k)=-‖xi-xk‖2

(4)

Step2聚類過程中，共有2種消息在各數(shù)據(jù)點(diǎn)間傳遞，分別是吸引度和歸屬度。建立吸引度矩陣r(i,k),表示數(shù)據(jù)點(diǎn)k適合作為數(shù)據(jù)點(diǎn)i的聚類中心的程度,歸屬度矩陣a(i,k)，表示數(shù)據(jù)點(diǎn)i選擇數(shù)據(jù)點(diǎn)k作為聚類中心的合適程度。

Step3按公式(5)和公式(6)迭代更新r(i,k)、a(i,k)：

(5)

(6)

Step4經(jīng)過若干次迭代后，對(duì)數(shù)據(jù)點(diǎn)的吸引度和歸屬度進(jìn)行求和，確定數(shù)據(jù)點(diǎn)的聚類中心。當(dāng)聚類中心保持不變或達(dá)到迭代次數(shù)時(shí)，算法結(jié)束。

2 基于改進(jìn)聚類集成的蟻群算法

針對(duì)在求解大規(guī)模TSP問題時(shí)傳統(tǒng)算法求解效率差、求解時(shí)間過長、誤差率增大等問題，本文通過運(yùn)用AP聚類，將一個(gè)大規(guī)模TSP問題(設(shè)城市數(shù)為n)分為若干個(gè)小規(guī)模的問題(設(shè)數(shù)量為m)，每個(gè)問題單獨(dú)作為一個(gè)分組，然后，將每一個(gè)分組都作為一個(gè)獨(dú)立的TSP問題，用蟻群算法求解它的最短路線。最后，為了縮短整個(gè)問題的路徑長度，本文設(shè)計(jì)了一個(gè)改進(jìn)的集成方案，以有效地將所有分組連接成一個(gè)整體。

2.1 大規(guī)模TSP問題的聚類

首先，根據(jù)TSP問題給定的坐標(biāo)點(diǎn)，可以構(gòu)建坐標(biāo)點(diǎn)之間的相似度矩陣S(i,k)(見公式(4))，隨后每個(gè)坐標(biāo)點(diǎn)都作為聚類中心。之后在聚類的過程中以吸引度r(i,k)和歸屬度a(i,k)在各坐標(biāo)點(diǎn)之間傳遞，吸引度r(i,k)表示坐標(biāo)點(diǎn)k成為聚類中心的能力大小，歸屬度a(i,k)表示坐標(biāo)點(diǎn)i對(duì)坐標(biāo)點(diǎn)k作為聚類中心的合適程度。并通過迭代過程更新每個(gè)坐標(biāo)點(diǎn)的吸引度和歸屬度。具體迭代公式見公式(5)和公式(6)。

經(jīng)過若干次迭代后，綜合吸引度與歸屬度的值，取r(i,j)+a(i,j)的最大值時(shí)，對(duì)應(yīng)的坐標(biāo)點(diǎn)k為i的聚類中心。在聚類中心不變或達(dá)到一定迭代次數(shù)時(shí)，算法結(jié)束，得到劃分后的若干個(gè)簇。

2.2 子問題的求解

通過AP聚類將大規(guī)模TSP問題分為m個(gè)子問題后，為得到m個(gè)子問題連接成一個(gè)整體的最短路徑，需要得到每個(gè)子問題的最優(yōu)路徑。本文運(yùn)用蟻群算法對(duì)每個(gè)分組的給定節(jié)點(diǎn)(即城市點(diǎn))進(jìn)行路徑尋優(yōu)，得到該子問題的最優(yōu)路徑。每個(gè)子問題運(yùn)用蟻群算法的過程如下：

Step1輸入子問題。

Step2為每個(gè)節(jié)點(diǎn)相互之間的距離建立一個(gè)距離矩陣。

Step3為每個(gè)節(jié)點(diǎn)之間建立一個(gè)信息素矩陣。

Step4設(shè)有n只螞蟻，每一只螞蟻隨機(jī)選擇一個(gè)節(jié)點(diǎn)，作為自己的起點(diǎn)。

Step5計(jì)算每只螞蟻向不同的節(jié)點(diǎn)移動(dòng)的概率。

Step6每只螞蟻根據(jù)概率，通過輪盤法向下一個(gè)城市行動(dòng)。

Step7回到Step5，直到所有的節(jié)點(diǎn)都被走遍。

Step8揮發(fā)信息素。

Step9根據(jù)螞蟻?zhàn)哌^的節(jié)點(diǎn)和路徑長度，更新信息素表。

Step10回到Step4，直到迭代結(jié)束。

Step11迭代結(jié)束，給定最優(yōu)路徑。

2.3 改進(jìn)后的集成方案

在上文的步驟中，是通過比較歐氏距離來確定刪除的路徑和新路徑，但可能由于部分節(jié)點(diǎn)分布的特殊性，導(dǎo)致集成后端口附近出現(xiàn)路徑與路徑的交叉問題，如圖1所示。

圖1 可能存在的交叉問題

當(dāng)聚類算法劃分出很多子問題時(shí)，這類交叉必然會(huì)導(dǎo)致全局最優(yōu)解的精度大幅度降低，所以必須對(duì)路徑進(jìn)行進(jìn)一步的優(yōu)化。若是為此在集成完成后對(duì)路徑進(jìn)行全局搜索，雖然可以找到并解開交叉，但必然會(huì)耗費(fèi)大量的時(shí)間。因此，本文為該集成方案引入局部路徑優(yōu)化算子，以達(dá)到找到并且解開交叉的同時(shí)又花費(fèi)較少的時(shí)間。

假設(shè)A組與B組路徑連接，所需要?jiǎng)h除的路徑是A組中i與i+1之間的路徑和B組中j與j+1之間的路徑。研究發(fā)現(xiàn)，導(dǎo)致交叉的4個(gè)節(jié)點(diǎn)位置必然存在于(i-1，i，i+1，i+2，j-1，j，j+1，j+2)之中，那么，只要在此范圍內(nèi)判斷出現(xiàn)交叉的位置，即可大幅度減少搜索交叉的時(shí)間。本文根據(jù)此構(gòu)想，設(shè)計(jì)了局部路徑優(yōu)化算子，具體實(shí)現(xiàn)步驟如下：

Step1判斷上文8個(gè)節(jié)點(diǎn)中所有可能形成的2條路徑之間是否存在交叉，具體方案如下：

1)設(shè)2條路徑分別為AB、CD，判斷以AB為對(duì)角線形成的矩形和以CD為對(duì)角線形成的矩形是否有重合的部分(見圖2)。

圖2 2個(gè)矩形是否有重合部分

即判斷以下式子是否成立：

min (Ax,Bx)max (Dx,Cx)&min (Cx,Dx)max (Ax,Bx)

min (Ay,By)max (Dy,Cy)&min (Cy,Dy)max (Ay,By)

(7)

2)若滿足以上要求，則判斷路徑AB的2個(gè)節(jié)點(diǎn)是否分布在路徑CD的2側(cè)，具體方案如下：引入平面向量，若相關(guān)向量滿足以下公式：

(8)

則路徑AB的2個(gè)節(jié)點(diǎn)必定分布在路徑CD的2側(cè)。

3)當(dāng)以上2個(gè)條件均滿足時(shí)，即可判斷路徑AB與CD之間存在交叉。

Step2若AB與CD之間存在交叉，即可刪去路徑AB和路徑CD，建立新路徑AD、BC，如圖3所示。

圖3 優(yōu)化后的新路徑

Step3完成局部路徑優(yōu)化。

最后，經(jīng)過改進(jìn)后的集成方案的效果如圖4所示。

圖4 解開交叉后的路徑效果圖

從圖4可明顯看出，通過設(shè)計(jì)局部路徑優(yōu)化算子，本文算法以極少的時(shí)間成本解決了圖1中的交叉問題，找到了更優(yōu)的路徑方案。

最后，基于改進(jìn)聚類集成的蟻群算法過程如下：

Step1輸入大規(guī)模TSP問題。

Step2運(yùn)用AP聚類將大規(guī)模TSP問題分為m個(gè)子問題。

Step3每個(gè)子問題用蟻群算法進(jìn)行尋優(yōu)，得到最優(yōu)子路徑。

Step4利用蟻群算法對(duì)聚類中心點(diǎn)的尋優(yōu)找到最佳組合序列。

Step5將所有的最優(yōu)子路徑根據(jù)最佳組合序列進(jìn)行組合。

Step6組合的過程中用局部路徑優(yōu)化算子解決可能存在的交叉問題。

Step7所有子路徑組合完畢，輸出整體最優(yōu)路徑。

3 實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)仿真環(huán)境是在Window 10系統(tǒng)Core i5的環(huán)境下進(jìn)行，測試平臺(tái)為MATLAB R017b。在實(shí)驗(yàn)中ACA、APACA、IACA蟻群算法均設(shè)置螞蟻數(shù)為2/3的城市數(shù)目，信息啟發(fā)式因子α均為1，期望啟發(fā)式因子β均為5，信息素?fù)]發(fā)系數(shù)ρ為0.5，信息素總量Q為100。本文使用的數(shù)據(jù)均來自于TSPLIB標(biāo)準(zhǔn)庫中的測試數(shù)據(jù)，每組實(shí)驗(yàn)均測試10次，為公平起見，每種算法在連續(xù)5次迭代過程中結(jié)果不變化時(shí)立即輸出路徑長度以及所需時(shí)間。

3.1 小規(guī)模城市下ACA算法的優(yōu)越性

設(shè)置PSO中個(gè)體經(jīng)驗(yàn)保留率和全局經(jīng)驗(yàn)保留率為0.8，粒子數(shù)為40。GA中初始種群大小為200，交叉概率和變異概率為0.8。結(jié)果如表1所示。

表1 ACA、PSO及GA小規(guī)模城市仿真結(jié)果

TSP問題ACAPSOGA平均值/m最優(yōu)值/m時(shí)間/s平均值/m最優(yōu)值/m時(shí)間/s平均值/m最優(yōu)值/m時(shí)間/sBays29931792733.517286165871198019944474ch3115647156024.630383295671215993157205eil5145444619121811662051247813Berlin52771376812021987210382193308596615pr76119771190964453194438631313132520458gr96548543131270726404119101761115

如表1所示，ACA算法相比于PSO算法在TSP問題的解決上具有壓倒性的優(yōu)勢。相比較于GA算法，ACA算法在速度上略低于GA算法，但其在魯棒性和求解質(zhì)量上明顯優(yōu)于GA算法，尤其在城市數(shù)大于50的測試數(shù)據(jù)中。因此本文在選擇算法求子路徑回路時(shí)，選擇了ACA算法。

3.2 驗(yàn)證IAPACA算法可以更有效求解大規(guī)模TSP問題

表2 ACA與GA仿真結(jié)果

TSP問題已知最優(yōu)解ACAGAAPACAIAPACA最小值/m平均值/m偏差率/%時(shí)間花費(fèi)/s最小值/m平均值/m偏差率/%時(shí)間花費(fèi)/s最小值/m平均值/m偏差率/%時(shí)間花費(fèi)/s最小值/m平均值/m偏差率/%時(shí)間花費(fèi)/sKroA1002128221887223262.819.107021956225643.115.3482442224994.514.75.86312346623727.210.36.0937a28025793149.53280.722.1494.18702990.03005.816.3101.532979.73067.7215.512.4582929.92992.5613.615.505rat7838806118461190834.515965117531250833.419569839.59849.211.727.0639766.3980810.931.470dsj10001.86×10721163000213300012.825711288670002895000055.230283209100002122850012.190.477208720002111710011.893.523u215264253————————————————————————734837463814.4168.873731987435213.8176.231pcb3038137694————————————————————————15419015474811.9252.35921451301531985.4255.7424

偏差率的計(jì)算公式為：

通過表2的實(shí)驗(yàn)結(jié)果可以看到，在求解KroA100這種小規(guī)模TSP問題時(shí)，ACA及GA算法的求解時(shí)間較短，所得結(jié)果精度良好，然而隨著問題的規(guī)模逐漸增大，它們的求解質(zhì)量開始大幅度下降。比如在解決a280、rat783、dsj1000問題時(shí)，花費(fèi)的時(shí)間大幅度增加，偏差率也隨之增大，顯然不能滿足求解需求，而APACA以及IAPACA的最小值、偏差率和平均值均優(yōu)于ACA，且大大降低了時(shí)間的成本。之后隨著問題的規(guī)模再逐漸增大，這些不足也被隨之放大。故在解決大規(guī)模TSP問題時(shí)，本文又設(shè)計(jì)了改進(jìn)的集成方案，從實(shí)驗(yàn)結(jié)果可看出，IAPACA的平均值和最小值的偏差均優(yōu)于APACA，有效證明了通過對(duì)集成方案的改進(jìn)，提升了所得結(jié)果的精度，驗(yàn)證了IAPACA在求解精度與求解時(shí)間上做到了很好的權(quán)衡，相比ACA、GA、IAPACA既大幅度減小了求解時(shí)間，又保證了求解精度。

最后，本文繪制了部分問題的路徑圖，因篇幅限制，圖5僅顯示dsj1000、u2152的測試結(jié)果。

(a) dsj1000

4 結(jié)束語

隨著TSP問題的規(guī)模逐漸增大，蟻群算法的求解質(zhì)量會(huì)大幅度下降，求解時(shí)間指數(shù)增長，誤差率增大。本文設(shè)計(jì)了基于聚類集成的蟻群算法的大規(guī)模TSP問題解決方案，運(yùn)用AP聚類將大規(guī)模TSP問題分為若干子問題，用蟻群算法對(duì)每個(gè)子問題進(jìn)行路徑尋優(yōu)，得到每個(gè)子問題的路徑方案。最后，為了提高最終結(jié)果的精度，用一種改進(jìn)的集成方案對(duì)所有子問題的路徑方案進(jìn)行組合，得到大規(guī)模TSP問題的解。實(shí)驗(yàn)結(jié)果表明，在求解大規(guī)模TSP問題時(shí)，IAPACA相對(duì)ACA，不僅大幅度縮短了花費(fèi)時(shí)間，而且減小了求解問題的誤差率。故本文設(shè)計(jì)的基于改進(jìn)聚類集成的蟻群算法在求解大規(guī)模TSP問題具有優(yōu)秀的性能。