求解大規(guī)模TSP問題的帶導(dǎo)向信息素蟻群算法

顧競豪，王曉丹，賈 琪

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051）

0 引言

蟻群算法具有魯棒性強(qiáng)、簡單易行、易與其他方法融合的優(yōu)點(diǎn)，在解決TSP問題中得到廣泛應(yīng)用［1-2］，但在處理大規(guī)模數(shù)據(jù)時，存在時間、空間復(fù)雜性大，搜索過程導(dǎo)向性不強(qiáng)等問題。文獻(xiàn)［3］采用并行計(jì)算策略，減緩計(jì)算復(fù)雜度過高的不足，并提出了一種自適應(yīng)的信息交換方式，防止算法陷入局部最優(yōu)，但搜索策略未考慮全局信息，搜索過程導(dǎo)向性不強(qiáng)；文獻(xiàn)［4］引入C-均值法和近鄰函數(shù)法劃分問題規(guī)模，減少了算法時間復(fù)雜性；文獻(xiàn)［5］使用GPU并行運(yùn)算同時優(yōu)化數(shù)據(jù)存儲方式，極大地減少了算法運(yùn)行時間，實(shí)驗(yàn)結(jié)果表明，算法準(zhǔn)確性有待提升。

針對以上問題，本文提出具有導(dǎo)向信息素的蟻群算法（Ant Colony Algorithm With Oriented Pheromones，OPACA），OPACA 算法以蟻群系統(tǒng)［6］（Ant Colony System，ACS）為基礎(chǔ)算法融入了3個改進(jìn)策略，分別是：1）采用稀疏矩陣存儲信息素表，在螞蟻路徑選擇時可有效減少算法時間復(fù)雜度，同時節(jié)省存儲空間；2）利用自適應(yīng)密度聚類算法獲取全局導(dǎo)向信息，使算法在初期便能朝最優(yōu)解方向收斂；3）改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則，并采用2-opt局部搜索策略，加速算法迭代時間與提升算法的與準(zhǔn)確率。算法分兩步進(jìn)行，首先通過聚類求解出“骨干網(wǎng)絡(luò)”并以導(dǎo)向信息素形式體現(xiàn)，后利用改進(jìn)的狀態(tài)轉(zhuǎn)移策略及2-opt策略的蟻群系統(tǒng)求解原問題。

1 蟻群系統(tǒng)原理

OPACA算法采用蟻群系統(tǒng)作為基礎(chǔ)算法。其中，Jk（i）表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序列 Rk中的城市集合，η（i，j）是啟發(fā)式信息，（i，j）是信息素濃度。

參數(shù)qo確定進(jìn)行開發(fā)還是偏向搜索。當(dāng)產(chǎn)生的隨機(jī)數(shù)q>qo時，算法使用輪盤選擇策略，式（2）是位于城市i的螞蟻k選擇城市j作為下一個訪問對象的概率。

2 具有導(dǎo)向信息素的蟻群算法

OPACA算法為進(jìn)一步提升蟻群系統(tǒng)在處理大規(guī)模TSP問題時的性能，在蟻群系統(tǒng)的基礎(chǔ)上，通過采用稀疏矩陣簡化運(yùn)算，添加導(dǎo)向信息素及改進(jìn)狀態(tài)轉(zhuǎn)移策略共3個方面的改進(jìn)，使算法在減小問題復(fù)雜性的同時，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索。

2.1 采用稀疏矩陣存儲信息素表

傳統(tǒng)蟻群算法中，信息素表以二維矩陣形式進(jìn)行存儲，算法時間復(fù)雜性隨問題規(guī)模的增加而急劇上升。

通過對不同實(shí)例的解空間進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)對最優(yōu)解中的每一個節(jié)點(diǎn)i為中心，作半徑為R的圓，圓的半徑R從零開始逐漸地增大，一直到取得節(jié)點(diǎn)i的近鄰節(jié)點(diǎn)為止，記錄下此時圓內(nèi)的節(jié)點(diǎn)數(shù)目P，設(shè)Max（P）為實(shí)例中P的最大值，那么有如下統(tǒng)計(jì)結(jié)果如表1所示。

表1 最優(yōu)值節(jié)點(diǎn)近鄰數(shù)目

因此，無論實(shí)例規(guī)模大小，P=1的概率基本為50%以上，即對任一節(jié)點(diǎn)i，選擇由i為起點(diǎn)的最短邊的概率極大。在算法中通過限定節(jié)點(diǎn)選擇范圍，能將解空間范圍由 n!縮小為 nmax（p）。

采用稀疏矩陣存儲信息素信息，并規(guī)定稀疏信息素矩陣中每一節(jié)點(diǎn)的元素初始值為30，上限為50，即稀疏信息素表大小小于50×N，不會影響算法得到最優(yōu)解的能力，而且能通過采用策略3中改進(jìn)的狀態(tài)轉(zhuǎn)移策略簡化運(yùn)算提升效率。

2.2 自適應(yīng)密度聚類算法獲取全局導(dǎo)向信息

2.2.1 粗劃分

從標(biāo)準(zhǔn)數(shù)據(jù)集中引入混合分布TSP實(shí)例a280。粗劃分采用自適應(yīng)密度聚類［7］的方法，該方法可以自動確定簇的數(shù)量，并能夠發(fā)現(xiàn)任意形狀的簇，算法將被稀疏部分隔開的稠密區(qū)域視為一簇，形成“省”的概念，稱其為“巨型城市”。因此，粗劃分可劃分任意形狀和大小的簇，且不受孤立點(diǎn)的影響。結(jié)果如圖1所示。

表2 粗、細(xì)劃分結(jié)果對比

2.2.2 細(xì)劃分

粗劃分后，巨型城市此時區(qū)域密度連續(xù)且不可再劃分，對節(jié)點(diǎn)數(shù)目超過200的實(shí)例進(jìn)行仿真，結(jié)果如表2所示，C粗表示粗劃分的實(shí)例分類數(shù)，C細(xì)表示細(xì)劃分后實(shí)例分類數(shù)，實(shí)驗(yàn)表明粗劃分不能有效劃分原問題，有時會出現(xiàn)節(jié)點(diǎn)聚集的現(xiàn)象。為解決此問題，引入節(jié)點(diǎn)細(xì)化分進(jìn)一步劃分原問題。

細(xì)化分通過K近鄰法（KNN，K-Nearest Neighbor）實(shí)現(xiàn)，指定城市上限，將巨型城市劃分形成若干城市集合。對a280實(shí)例細(xì)化分，并用改進(jìn)的蟻群系統(tǒng)求解初始路徑。

在自適應(yīng)密度聚類算法中，KNN不方便自動確定聚類數(shù)目，通過改用自適應(yīng)的DBSCAN［8］算法，通過分析節(jié)點(diǎn)之間的最大最小間隔，自適應(yīng)得到E領(lǐng)域大小，從而確定聚類數(shù)目。

在確定聚類數(shù)目后，各簇的連接規(guī)則通過蟻群算法完成，首先計(jì)算各個簇的中心點(diǎn)坐標(biāo)，然后將中心點(diǎn)坐標(biāo)帶入原蟻群算法進(jìn)行運(yùn)算得到初始路徑，最后以初始路徑作為粗劃分后各簇的最優(yōu)連接順序，供下一步運(yùn)算使用。

2.2.3 建立導(dǎo)向信息素濃度矩陣

在獲取城市集合最優(yōu)連接順序后，開始初始化導(dǎo)向信息素濃度矩陣，初始化方法如式（4）所示，其中|m-n|表示在最優(yōu)路徑中的序列編號差，Length代表初始化路徑總長度，N為問題規(guī)模。

式（4）的物理意義：在求解出各簇的最優(yōu)連接順序后，需要通過建立導(dǎo)向信息素濃度矩陣來指導(dǎo)算法在一定程度上按照該順序進(jìn)行連接和遍歷，為此，根據(jù)最優(yōu)連接順序，依次在粗劃分連接順序的前后節(jié)點(diǎn)上賦予不同簇之間的濃度值，使算法偏向于在相鄰簇之間尋找最優(yōu)遍歷點(diǎn)。

考慮利用問題的局部性簡化運(yùn)算，配合策略1應(yīng)用于算法中，導(dǎo)向信息素濃度矩陣也利用稀疏矩陣的方式存儲，并規(guī)定稀疏信息素矩陣中每一節(jié)點(diǎn)的元素上限為50。

2.3 策略3，改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則

建立候選集合Vi，將節(jié)點(diǎn)i所有訪問過的下一節(jié)點(diǎn)序號加入集合Vi中，下次遍歷時優(yōu)先考慮集合中的元素。當(dāng)且僅當(dāng)Vi中所有節(jié)點(diǎn)都不滿足條件時，遍歷所有節(jié)點(diǎn)。

在螞蟻每次完成迭代后，采用2-opt策略，進(jìn)一步提升算法準(zhǔn)確率。

Vi作為限制條件，并加入導(dǎo)向信息素后，新的狀態(tài)轉(zhuǎn)移規(guī)則如式（5）所示。

OPACA算法具體步驟如下所示：

Step1 城市總數(shù)為N，用自適應(yīng)密度聚類算法進(jìn)行粗劃分，設(shè)得到巨型城市G個，孤立城市L個；

Step3求出城市集合的中心城市C（ii=1，2，…，V），中心城市可以不是TSP問題中的城市，將孤立城市與城市集合合并成新TSP問題，利用基本蟻群算法計(jì)算最優(yōu)連接路徑M（jj=1，2，…，V+L）；

Step4 按照連接順序，求解出邊界城市，并根據(jù)邊界城市初始化城市集合內(nèi)最短連接順序。此時，對城市集合為最優(yōu)路徑下的邊界城市，表示除去邊界城市后所剩普通城市的連接順序，最優(yōu)全局路徑作為算法初始化路徑；

Step5 利用Step4中的初始路徑初始化改進(jìn)的蟻群系統(tǒng)，完成稀疏信息素矩陣與稀疏導(dǎo)向信息素矩陣的建立，確定參數(shù)及螞蟻數(shù)目，開始迭代；

Step6 判斷是否到達(dá)最大迭代代數(shù)或停止條件，若達(dá)到則算法結(jié)束，停止迭代，返回最優(yōu)解，否則進(jìn)行下一步；

Step7 判斷所有螞蟻是否均完成所有節(jié)點(diǎn)的遍歷，若完成，迭代次數(shù)加1，返回Step6，否則進(jìn)行下一步；

Step8 判斷當(dāng)前螞蟻是否遍歷完成所有節(jié)點(diǎn)，若完成，代表螞蟻完成個數(shù)的臨時變量加1，并利用2-opt策略，改進(jìn)當(dāng)前結(jié)果，取最優(yōu)值，并進(jìn)入下一步；若未完成，利用改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則，尋找下一節(jié)點(diǎn)，而后繼續(xù)執(zhí)行Step8；

Step9 利用新的稀疏信息素表更新方式，更新全局信息素信息，完成后返回Step7。

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

實(shí)驗(yàn)環(huán)境采用Matlab 2016a，在內(nèi)存為8G，Inter（R）i7-4790 3.60 GHz處理器的PC，選用標(biāo)準(zhǔn)TSP庫［9］中實(shí)例完成對比實(shí)驗(yàn)。

3.1 參數(shù)設(shè)定

根據(jù)式（5），并由于本文所提導(dǎo)向信息素是以和原有信息素濃度相加后的結(jié)果作為兩節(jié)點(diǎn)之間最終取值，因此，在數(shù)量級上因保持不變，所以選定α 為 1、β 為 2。

對蟻群系統(tǒng)，通過實(shí)驗(yàn)對比［6］當(dāng)α為1、β為2、qo為0.9時性能最佳。為保證算法最大性能，參數(shù)ρ與 ξ（ρ，ξ∈（0，1））的設(shè)置需要通過實(shí)驗(yàn)得出，取 TSP數(shù)據(jù)庫中 4 個典型實(shí)例 a280、d657、pr1002、pr2392，初始時將 ρ與 ξ設(shè)置為 0.1，令步長 Δρ=0.1，Δξ=0.1，每個取值計(jì)算得到的最優(yōu)路徑（COST）10次，結(jié)果取平均值。結(jié)果如圖2所示，Z軸表示最短路徑長度，實(shí)驗(yàn)表明，算法中，當(dāng)ρ與ξ分別取值為0.1與0.7時性能最佳。

3.2 3個策略有效性實(shí)驗(yàn)

將OPACA算法與標(biāo)準(zhǔn)蟻群系統(tǒng)進(jìn)行對比，參數(shù)設(shè)置如如表3所示。

實(shí)驗(yàn)表明，3個策略在處理大規(guī)模問題時對OPACA算法性能的提升均有幫助：策略1在效率上縮小了算法迭代的時間，當(dāng)規(guī)模增大時將算法終止時間縮短了2倍以上，采用稀疏矩陣對算法結(jié)果準(zhǔn)確性的影響幾乎可以忽略；策略2略微增加了算法運(yùn)行時間，在處理大規(guī)模問題時準(zhǔn)確性提升了5至10倍，導(dǎo)向信息素的加入使螞蟻在初期就能進(jìn)入尋找全局最優(yōu)的過程中去；策略3的局部搜索策略提升了算法尋找全局最優(yōu)解的能力，同時提升了算法的穩(wěn)定性使其更易朝最優(yōu)路徑中收斂，結(jié)果如圖3、圖4所示。

3.3 對比實(shí)驗(yàn)

將OPACA算法與蟻群算法的改進(jìn)版本TSIA-CO［10］、MMAS［11］、ESACO［7］、CPACA［4］及 ACS［6］進(jìn)行對比，參數(shù)設(shè)置如表3所示，規(guī)定終止迭代次數(shù)為1 000代，螞蟻數(shù)量10只。各算法均運(yùn)行10次，統(tǒng)計(jì)算法停止時所得最優(yōu)路徑的方差與平均值，結(jié)果如圖5及表4所示，實(shí)驗(yàn)表明OPACA算法在處理大規(guī)模問題時，相比同類改進(jìn)算法性能更優(yōu)且穩(wěn)定性好。

表4 不同實(shí)例下算法平均值與方差

4 結(jié)論

本文分析蟻群算法在求解大規(guī)模TSP問題時關(guān)鍵點(diǎn)，給出了3個改進(jìn)策略，提出了OPACA算法，OPACA算法在蟻群系統(tǒng)的基礎(chǔ)上通過采用稀疏矩陣簡化運(yùn)算，聚類算法產(chǎn)生導(dǎo)向信息素及改進(jìn)狀態(tài)轉(zhuǎn)移策略共有3個方面的改進(jìn)，在減小問題復(fù)雜性的同時，有效引導(dǎo)算法朝全局最優(yōu)方向進(jìn)行搜索，穩(wěn)定性高，克服了基本蟻群算法在解決大規(guī)模問題時，存在的易停滯在局部最優(yōu)導(dǎo)致準(zhǔn)確率低、收斂時間過長、最優(yōu)解偏差較大等問題。最后，采用標(biāo)準(zhǔn)TSP數(shù)據(jù)庫，對3個改進(jìn)策略及同類算法分別進(jìn)行對比實(shí)驗(yàn)，通過實(shí)驗(yàn)驗(yàn)證了算法性能，結(jié)果表明OPACA算法性能更佳，實(shí)現(xiàn)了針對大規(guī)模TSP問題的優(yōu)化，有利于蟻群算法的應(yīng)用與推廣。