劉一凡，游曉明+，劉 升

1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620

旅行商問題[1]（traveling salesman problem，TSP）是一類經(jīng)典的組合優(yōu)化問題，可以描述為：旅行商從一個城市出發(fā)，不重復(fù)地遍歷完所有城市并最終回到起始城市，需要在所有滿足以上條件的路徑中找出最短路徑的問題。國內(nèi)外學(xué)者采用多種算法來研究此問題，目前主要有遺傳算法[2]、模擬退火法[3]、粒子群算法[4]和蟻群算法[5]等。其中，蟻群算法具有較強(qiáng)的魯棒性、良好的并行性和易與其他算法結(jié)合等特點，在求解TSP 問題中取得很好的效果，并被廣泛應(yīng)用于車輛調(diào)度、圖像處理和多目標(biāo)組合優(yōu)化等諸多優(yōu)化領(lǐng)域。

蟻群算法是一種新興智能仿生優(yōu)化算法，最初于20 世紀(jì)90 年代由意大利學(xué)者Dorigo 等人提出。1996 年，Dorigo 等人在螞蟻系統(tǒng)（ant system，AS）[6]的基礎(chǔ)上，采用信息素全局更新和局部更新兩種信息素更新方式，提出蟻群系統(tǒng)（ant colony system，ACS）[7]算法，加快了算法收斂速度。2000年，Stutzle等人提出了最大最小螞蟻系統(tǒng)（max-min ant system，MMAS）[8]，為每條路徑上信息素濃度設(shè)定了上、下限閾值，避免信息素濃度無限累加而停滯，提高了算法的多樣性。以上基本蟻群算法具有高效的搜索能力，但仍存在著易陷入局部最優(yōu)、收斂速度慢等問題。

蟻群優(yōu)化算法（ant colony optimization，ACO）是對基本蟻群算法進(jìn)行改進(jìn)的一系列優(yōu)化算法，為了提高基本蟻群算法的性能，國內(nèi)外學(xué)者主要在路徑選擇、信息素更新、添加局部優(yōu)化算子和與其他算法結(jié)合等方面進(jìn)行改進(jìn)。文獻(xiàn)[9]引入精英策略思想，提出一種基于排序加權(quán)的信息素更新策略，通過強(qiáng)化較優(yōu)路徑信息對螞蟻的反饋作用，提高了算法收斂速度和求解質(zhì)量。文獻(xiàn)[10]從蟻群算法的理論研究、算法融合、多蟻群算法研究等方面對蟻群算法在移動機(jī)器人路徑規(guī)劃中的未來研究內(nèi)容和研究熱點進(jìn)行展望。文獻(xiàn)[11]依據(jù)聚類算法對環(huán)境復(fù)雜程度的準(zhǔn)確判別自動改變尋優(yōu)半徑，達(dá)到充分利用機(jī)器人有限的計算能力，提高收斂速度的目的，但算法多樣性仍有待提升。針對這一不足，文獻(xiàn)[12]利用改進(jìn)的頭尾搜索機(jī)制，并引入獎懲因子、信息素最大最小閾值和遺傳算法變異因子，提高了算法全局搜索能力和跳出局部最優(yōu)的能力。以上單種群蟻群優(yōu)化算法在解決中小規(guī)模TSP 問題方面得到了很大的改進(jìn)，但在解決大規(guī)模TSP 問題時，其求解精度仍需要進(jìn)一步提高。

為進(jìn)一步提高算法的搜索能力和求解性能，許多算法采用了多種群策略。在文獻(xiàn)[13]中，姜慧楠等人結(jié)合人工魚群算法（artificial fish swarms algorithm，AFSA）前期收斂速度快和混合蛙跳算法（shuffled frog leaping algorithm，SFLA）局部搜索能力強(qiáng)的優(yōu)勢，提出一種人工魚群-蛙跳混合優(yōu)化算法（AFSA-SFLA），提高了種群的質(zhì)量和算法的高效性。文獻(xiàn)[14]中魏士偉提出了一種基于協(xié)同進(jìn)化的遺傳算法（co-evolution genetic algorithm，CEGA）用于解決遺傳算法（genetic algorithm，GA）的缺陷，既保證了種群向最優(yōu)解的方向移動，又保持了種群的多樣性。此外，多種群策略在蟻群優(yōu)化算法中也有許多體現(xiàn)，文獻(xiàn)[15-17]利用蟻群算法與其他優(yōu)化算法的良好結(jié)合特性，提出了一系列的融合蟻群算法，有效提升了蟻群算法的收斂速度和算法多樣性，但對于大規(guī)模TSP 問題的求解精度和跳出局部最優(yōu)的能力有待進(jìn)一步改善。

為了在提升收斂速度的同時提高求解精度和穩(wěn)定性，需要進(jìn)一步平衡蟻群多樣性和算法收斂性，為此，本文提出一種基于動態(tài)重組和協(xié)同交流策略的蟻群優(yōu)化算法（ant colony optimization algorithm based on dynamic recombination and cooperative communication strategy，RCACO）。其主要改進(jìn)思想是：（1）多種群策略。將蟻群劃分為貪婪蟻群和探索蟻群，貪婪蟻群沿用ACS 的路徑構(gòu)建規(guī)則和信息素更新策略，主要負(fù)責(zé)尋找當(dāng)前較優(yōu)路徑，提高算法的收斂速度，探索蟻群采用改進(jìn)的路徑構(gòu)建規(guī)則和信息素更新策略，主要負(fù)責(zé)探索有潛力的非較優(yōu)路徑，增加算法的多樣性。（2）動態(tài)重組策略。提出一種基于線索二叉樹的新型重組算子，并采用不同的重組策略對解集進(jìn)行動態(tài)重組，避免隨機(jī)盲目重組的同時增加了算法的導(dǎo)向性，以提升算法的多樣性和平均求解質(zhì)量。（3）協(xié)同交流策略。提出一種基于相似度和潛力值的協(xié)同交流策略，讓兩類蟻群并行搜索那些有潛力成為最優(yōu)解的路徑，將所搜索到的優(yōu)良路徑作為共享信息進(jìn)行種群間的交流，從而有效提高算法的收斂速度。（4）停止規(guī)避策略。為避免算法因次優(yōu)路徑上信息素濃度過高而陷入停滯，加入了停滯規(guī)避策略，保證了算法后續(xù)循環(huán)的有效性，從而增強(qiáng)算法的搜索性能，以幫助蟻群跳出局部最優(yōu)，獲得標(biāo)準(zhǔn)最優(yōu)解。

1 相關(guān)工作

1.1 ACS 蟻群算法原理

1.1.1 路徑構(gòu)建

ACS 算法中每只螞蟻從城市i到城市j的狀態(tài)轉(zhuǎn)移規(guī)則如下：

其中，q是一個在區(qū)間[0,1]上的隨機(jī)數(shù)，q0(0 ≤q0≤1)是一個可調(diào)參數(shù)，τij表示i和j城市路徑上的信息素總量，ηij表示i和j城市之間距離的倒數(shù)，allowed表示當(dāng)前可選城市的集合。s是采用輪盤賭的方式選出的下一個城市，使得算法可以有偏向性地探索各條邊，城市之間信息素濃度高和距離近的城市被選擇的概率更大，但其他次優(yōu)路徑也有一定概率被選到，具體公式如下：

本文中的兩類蟻群沿用了ACS 的狀態(tài)轉(zhuǎn)移規(guī)則，但兩類算法分別采用不同的q0。貪婪蟻群采用較大的q0，對當(dāng)前最優(yōu)區(qū)域進(jìn)行深度探索，加快收斂速度；探索蟻群采用較小的q0，對其他次優(yōu)區(qū)域進(jìn)行廣度搜索，增加算法多樣性。

1.1.2 信息素的更新

ACS 算法中的信息素更新策略分為局部信息素更新和全局信息素更新兩部分。

局部信息素更新：當(dāng)每只螞蟻從城市i經(jīng)過下一個城市j之后，算法會對這條路徑進(jìn)行局部信息素更新，公式為：

其中，τ0為每條邊上的起始信息素濃度，ξ是局部信息素的蒸發(fā)率。局部信息素更新可以防止算法過早陷入局部最優(yōu)，增加算法的多樣性。

全局信息素更新：當(dāng)所有螞蟻都完成路徑構(gòu)建后，算法會對當(dāng)前全局最優(yōu)路徑進(jìn)行全局信息素更新，公式為：

其中，Δτij是信息素增量；Lgb是當(dāng)前全局最優(yōu)路徑的長度；ρ是全局信息素的蒸發(fā)率。全局信息素更新會對全局最優(yōu)螞蟻走過的路徑進(jìn)行信息素獎勵，可以起到正反饋的作用，增加算法的導(dǎo)向性和收斂速度。

1.2 線索二叉樹

在二叉樹的節(jié)點上加上線索的二叉樹稱為線索二叉樹，線索二叉樹中的線索能記錄每個節(jié)點前驅(qū)和后繼信息。為了區(qū)別線索指針和孩子指針，在每個節(jié)點中設(shè)置兩個標(biāo)志ltag 和rtag。

傳統(tǒng)線索二叉樹的節(jié)點結(jié)構(gòu)如表1 所示。

Table 1 Node structure of traditional clew binary tree表1 傳統(tǒng)線索二叉樹的節(jié)點結(jié)構(gòu)

表1 中：ltag=0 時，lchild 指向左兒子；ltag=1 時，lchild 指向前驅(qū)；rtag=0 時，rchild 指向右兒子；rtag=1時，rchild 指向后繼。

2 改進(jìn)策略

2.1 多種群信息素更新策略

傳統(tǒng)的信息素更新策略會對全局最優(yōu)螞蟻走過的路徑進(jìn)行信息素獎勵，可以起到正反饋的作用，提高算法的導(dǎo)向性和收斂速度，本文將其作為信息素更新1 應(yīng)用于貪婪蟻群。但是，傳統(tǒng)蟻群算法的正反饋策略會在較短的路徑上留下更多的信息素，吸引更多的螞蟻選擇此路徑，在迭代一定次數(shù)后，這些較短的路徑上容易堆積大量信息素，即使最終這些路徑并不是最優(yōu)路徑，也會使后續(xù)的蟻群都去選擇這些次優(yōu)路徑，導(dǎo)致蟻群不能對解空間進(jìn)一步進(jìn)行廣度搜索，進(jìn)而出現(xiàn)停滯現(xiàn)象，陷入局部最優(yōu)解。

為此，本文引入貢獻(xiàn)度因子，借鑒精英策略和MMAS 的思想，提出一種改進(jìn)的信息素更新策略，并將其作為信息素更新策略2 應(yīng)用于探索蟻群。貢獻(xiàn)度因子是指每條路徑歷史累計更新的次數(shù)，在所有螞蟻完成路徑構(gòu)建后，對所有路徑進(jìn)行升序排序，取出本次迭代的前10%的螞蟻，并按照路徑長短進(jìn)行不同程度的信息素更新，對于當(dāng)前全局最優(yōu)的路徑會給予額外獎勵。在依次對這些精英螞蟻所經(jīng)過的路徑段進(jìn)行更新后，該路徑段貢獻(xiàn)度+1，當(dāng)貢獻(xiàn)度到達(dá)一定次數(shù)后，這段路徑就不予更新，以此達(dá)到控制路徑上信息素閾值的效果。具體公式如下：

2.2 動態(tài)重組策略

2.2.1 改進(jìn)線索二叉樹

螞蟻完成路徑構(gòu)建后得出一組城市序列，每2 個城市及連接它們的1 條路徑構(gòu)成一個最短子路徑。輸入兩組城市序列A、B，將A中的每個城市節(jié)點及其最短子路徑拿出來和B作對比，本文算法對傳統(tǒng)線索二叉樹結(jié)構(gòu)進(jìn)行改進(jìn)以存儲每個城市節(jié)點及其最短子路徑的相關(guān)信息，如表2 所示。

線索二叉樹構(gòu)建完成后，對Scount 求和再除以城市個數(shù)，可得出A和B兩組城市序列的相似度SAB，其取值范圍為[0,1]，相似度在后文的協(xié)同交流階段中控制兩類蟻群交流的頻率起作用。

例如有一個10 城市的TSP，其兩個解向量的城市序列分別為A=[1 2 3 4 5 6 7 8 9 10]和B=[5 7 8 6 9 1 10 2 3 4]。以城市4 為例，其在A和B序列中的前驅(qū)節(jié)點都為3，后繼節(jié)點都為5，說明3→4 和4→5 均是重復(fù)路徑，以此類推，兩個解向量具有4 個相同最短子路徑:2→3，3→4，4→5，7→8，即SAB=0.4。

2.2.2 新型動態(tài)重組算子

為加強(qiáng)算法多樣性和跳出局部最優(yōu)的能力，在以往的遺傳算法和與之結(jié)合的蟻群算法中大多會采用重組策略，可大致描述為：若兩條路徑節(jié)點序列中具有公共節(jié)點，則隨機(jī)選其一公共節(jié)點進(jìn)行交叉操作，產(chǎn)生兩條新路徑；若路徑節(jié)點序列沒有公共節(jié)點，則在該兩條路徑中分別隨機(jī)剔除一條路段，通過交叉拼接得到兩條新路徑。這樣的重組策略隨機(jī)性強(qiáng)，雖然多樣性會增加，但效率較低，往往得不到優(yōu)于目前最優(yōu)解的解。

為避免盲目隨機(jī)重組，本文采用結(jié)合線索二叉樹的新型重組算子對算法進(jìn)行動態(tài)重組。首先由城市序列A和B構(gòu)建出線索二叉樹矩陣，為保留一定的隨機(jī)性，增加多樣性，在全部城市節(jié)點中隨機(jī)選出一個節(jié)點作為新路徑的第一個節(jié)點，接下來循環(huán)進(jìn)行后續(xù)節(jié)點的選擇，最后依次將選出的節(jié)點添加到新路徑中，構(gòu)成新的城市序列。具體操作如下：

Table 2 Node structure of improved cue binary tree表2 改進(jìn)的線索二叉樹的節(jié)點結(jié)構(gòu)

動態(tài)重組算子會保留公共子路徑，將非公共子路徑按策略重組，提升算法的收斂速度，具體操作為：將選出的第一個城市節(jié)點作為當(dāng)前節(jié)點node，若當(dāng)前節(jié)點有后繼節(jié)點Anode(Bnode)，說明原路徑A和B都包含有這段最短子路徑，則待選節(jié)點選其后繼節(jié)點；若無后繼節(jié)點，則優(yōu)先選擇距離當(dāng)前節(jié)點之間路徑距離近的、信息素濃度高的、貢獻(xiàn)度值大的城市節(jié)點作為后續(xù)節(jié)點，還有概率直接選擇原序列A或B中的下一節(jié)點，將其作為后續(xù)節(jié)點添加到新路徑中。

該重組策略根據(jù)線索二叉樹來保留公共路徑，根據(jù)城市距離矩陣、信息素表和貢獻(xiàn)度表共同影響進(jìn)行導(dǎo)向性重組，實驗發(fā)現(xiàn)重組后優(yōu)于原路徑的概率大大增加，而重組后沒有改進(jìn)的路徑會被舍棄，這就有效提升了蟻群整體的求解質(zhì)量。

2.2.3 動態(tài)重組策略

（1）種群內(nèi)部動態(tài)重組

在每次迭代過程中，算法會對兩類蟻群內(nèi)部所產(chǎn)生的解單獨進(jìn)行動態(tài)重組。具體操作為：當(dāng)種群內(nèi)的m只蟻群全部構(gòu)建完路徑后，對全部路徑進(jìn)行升序排序，用Li表示本次迭代中排名為i的解(0

（2）種群之間動態(tài)重組

在改進(jìn)蟻群算法中，貪婪蟻群和探索蟻群完成迭代后共得到2m個解，每個解包含路徑長度和城市序列，將每個解按照路徑長度進(jìn)行升序排列，將整個蟻群分為N組，每組包含M只螞蟻，即滿足2m=N×M。具體分組情況如表3 所示。

這樣劃分后的每組解的質(zhì)量相似，能保證種群中更多的差解得到進(jìn)化，提升解集的平均質(zhì)量。對于每組螞蟻，用Lb表示組中最短路徑的解，Lw表示組中最長路徑的解，Lg表示所有螞蟻當(dāng)前全局最短路徑的解，則有Lg≤Lb≤Lw。分別取Lb為A，Lw為B，利用上文中結(jié)合線索二叉樹的新型重組算子生成新解Lnew，然后對各組螞蟻中的Lb和Lw循環(huán)進(jìn)行更新，公式如下：

Table 3 Grouping situation table表3 分組情況表

動態(tài)重組算子很大程度上改善了整體蟻群解集的平均質(zhì)量，重組算子增加了算法的多樣性和跳出局部最優(yōu)的能力，有效提高了算法的收斂速度和求解精度。

2.3 協(xié)同交流策略

2.3.1 引入相似度的交流頻率策略

當(dāng)兩類蟻群交流間隔過短時，會造成算法多樣性下降，產(chǎn)生的結(jié)果會類似于一個種群，起不到分兩個種群的作用；而當(dāng)信息交流間隔過長時，會削弱兩類蟻群之間互相學(xué)習(xí)和促進(jìn)的作用，不利于提升收斂速度。

為此，本文采用引入相似度[18]的交流頻率策略，對交流間隔進(jìn)行自適應(yīng)調(diào)整。在兩類蟻群完成本次迭代后，進(jìn)入?yún)f(xié)同交流階段，首先分別用貪婪蟻群和探索蟻群得到的全局最優(yōu)路徑作為A和B，并構(gòu)建線索二叉樹，進(jìn)而得到兩條路徑的相似度。當(dāng)相似度過高時，兩類蟻群趨于一致，多樣性較差，不適合交流；當(dāng)相似度過低時，兩類蟻群的多樣性較高，應(yīng)進(jìn)行信息交流。每隔K次迭代，根據(jù)式（11）判斷是否交流，公式如下：

式中，L為判斷是否可交流的邏輯值，SAB是兩類種群最優(yōu)解的相似度，S是相似度閾值。

2.3.2 引入潛力值的激勵策略

傳統(tǒng)蟻群算法通常只對最優(yōu)的螞蟻進(jìn)行信息素更新，忽略了其他次優(yōu)螞蟻攜帶最優(yōu)路徑片段的潛力，從而容易陷入局部最優(yōu)解。

為此，本文引入潛力值的概念，潛力值受貢獻(xiàn)度和最小生成樹的共同影響。首先，貪婪蟻群和探索蟻群各有一份貢獻(xiàn)度表，將兩份貢獻(xiàn)度表整合成一張，某段路徑的貢獻(xiàn)度越高，代表這條路徑被兩類種群都選為最優(yōu)路徑片段的概率越高，即可認(rèn)為這條路徑段成為最優(yōu)路徑的潛力值就比較大，即潛力值和貢獻(xiàn)度呈正比關(guān)系。此外，在TSP 問題中，標(biāo)準(zhǔn)最優(yōu)路徑與最小生成樹中70%～80%的路徑是吻合的，而最小生成樹不是唯一的，因此多個最小生成樹所重復(fù)包含的路徑的潛力值也是比較大的。將潛力值因子結(jié)合到求解TSP 問題中去，對合并貢獻(xiàn)度表中貢獻(xiàn)度值較大的前n條路徑以及生成最小生成樹重合路徑最多的前n條路徑進(jìn)行額外的信息素獎勵，將會綜合兩類蟻群的優(yōu)點，提升算法的收斂性能，其公式如下：

其中，Δτij是由式（5）得出的信息素增量，ρ是全局信息素的蒸發(fā)率。對潛力值高的路徑進(jìn)行額外更新可以使兩類蟻群的信息得到交融，起到一定的正導(dǎo)向性，從而加快算法的收斂速度并提高收斂精度。

2.4 停滯規(guī)避策略

傳統(tǒng)蟻群算法迭代一定次數(shù)后，可能在次優(yōu)路徑上積累大量信息素，進(jìn)而出現(xiàn)停滯現(xiàn)象，而算法停滯后的循環(huán)都是在做無用功，為加強(qiáng)算法跳出局部最優(yōu)的能力，應(yīng)對停滯現(xiàn)象做出檢測及相應(yīng)處理措施。

本文的算法停滯檢測分為兩種：第一種是當(dāng)本次迭代所有螞蟻所構(gòu)建的路徑相似度過高，甚至趨于一條路徑；第二種是在一定迭代次數(shù)內(nèi)，仍未出現(xiàn)更優(yōu)的解。具體檢測判斷公式如下：

其中，L1為判斷是否停滯的邏輯值；Sall是所有螞蟻的相似度均值；T和q1是可調(diào)參數(shù)。

本文對算法停滯的具體措施如下：當(dāng)檢測到算法中兩類蟻群都停滯時，首先將兩類蟻群中所有路徑上的信息素置為初始值，然后篩選出兩類蟻群都停滯時所產(chǎn)生最優(yōu)路徑的公共路徑，最后加強(qiáng)公共路徑上的信息素。公式如下：

其中，τ0為每條邊上的起始信息素濃度，Δτij是兩類蟻群分別由式（5）得出的信息素增量。加強(qiáng)公共路徑的信息素會增強(qiáng)算法停滯后再次運(yùn)行的導(dǎo)向性，并使得算法減少在公共路徑上的搜索，將算法的側(cè)重點放在非公共路徑的城市序列的優(yōu)化中。該策略有利于算法發(fā)現(xiàn)更優(yōu)的路徑，幫助算法在后續(xù)的循環(huán)中能有效跳出局部最優(yōu)。

2.5 算法步驟和算法流程圖

算法整體流程圖如圖1 所示。

Fig.1 Algorithm overall flow chart圖1 算法整體流程圖

算法步驟：

步驟1參數(shù)初始化。

步驟2將蟻群劃分為貪婪蟻群和探索蟻群，并分別單獨進(jìn)行迭代，兩類蟻群均采用式（1）、式（2）的城市轉(zhuǎn)移規(guī)則以及式（3）的局部信息素更新策略。

步驟3當(dāng)每類蟻群完成路徑構(gòu)建后，運(yùn)用新型重組算子，根據(jù)式（9）對蟻群所產(chǎn)生的解集進(jìn)行內(nèi)部動態(tài)重組。

步驟4進(jìn)入全局信息素更新階段，貪婪蟻群采用式（4）、式（5）即ACS 中的全局信息素更新策略1，而探索蟻群采用式（6）～式（8）即改進(jìn)的全局信息素更新策略2。

步驟5將兩類蟻群所產(chǎn)生解集混合并分組，根據(jù)式（10）對兩類蟻群之間進(jìn)行動態(tài)重組，然后混洗蟻群。

步驟6進(jìn)入?yún)f(xié)同交流階段，計算兩類蟻群的相似度，然后根據(jù)式（11）判斷是否進(jìn)行交流，若是，轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟8。

步驟7由各路徑的貢獻(xiàn)度和最小生成樹計算潛力值，并根據(jù)式（12）進(jìn)行各種群間的交流。

步驟8根據(jù)式（13）對算法是否停滯做出檢測，若是，轉(zhuǎn)步驟9，否則，轉(zhuǎn)步驟10。

步驟9根據(jù)式（14）對算法停滯做出相應(yīng)處理。

步驟10當(dāng)NC≤NCmax時，NC=NC+1，跳轉(zhuǎn)到步驟2；否則，轉(zhuǎn)到步驟11。

步驟11輸出最優(yōu)解。

3 實驗仿真

為了驗證RCACO算法的有效性，使用MATLAB-2019a 對TSPLIB 標(biāo)準(zhǔn)庫中的15 個不同規(guī)模的城市進(jìn)行實驗仿真，其中包括10 個中小規(guī)模城市實例和5個大規(guī)模城市實例。以上述TSP 實例為對象，分別對ACS、ACS+3opt 和不同優(yōu)化方案下的RCACO 進(jìn)行15 次實驗，每輪迭代2 000 次，同時從收斂速度（迭代次數(shù)）、誤差率（最優(yōu)解）、穩(wěn)定性（平均解）等幾個方向進(jìn)行實驗分析。其中，誤差率用來衡量每種ACO與測試集最優(yōu)解之間的差距，計算公式如下：

其中，LACO為三種ACO 算法所找到的最優(yōu)解，LBest為測試集的標(biāo)準(zhǔn)最優(yōu)解。

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

為保證實驗合理性，ACS、ACS+3opt 和RCACO算法在各TSP 實例中的實驗參數(shù)設(shè)置均如表4 所示。

Table 4 Setting of parameters表4 參數(shù)設(shè)置

表4 中，m為螞蟻數(shù)量，螞蟻數(shù)量越多，得到的最優(yōu)解就越精確，但會產(chǎn)生不少重復(fù)解，增加時間復(fù)雜度；α為信息啟發(fā)因子，α值越小，螞蟻選擇之前走過的路徑可能性就越小，可以加強(qiáng)搜索路徑的隨機(jī)性，但容易陷入局部最優(yōu)；β為期望啟發(fā)因子，β值越大，蟻群就越容易選擇局部較短路徑，可以加快收斂速度，但是多樣性較差；q0是式（1）中的參數(shù)，q0越大，貪婪性卻強(qiáng)，收斂速度越快，但多樣性越低；ρ是全局信息素蒸發(fā)率，ξ是局部信息素蒸發(fā)率，蒸發(fā)率過小時，會影響到算法的收斂速率，蒸發(fā)率過大時，會影響到最優(yōu)值的搜索；S是式（11）中的相似度閾值，相似度均值超過S后不再進(jìn)行交流；K是交流間隔，K值過大會降低交流策略的效果，K值過小會讓兩種蟻群趨于一致，失去設(shè)立多蟻群的意義。

經(jīng)過多次實驗，統(tǒng)計對比其結(jié)果發(fā)現(xiàn)，參數(shù)設(shè)置如表4 所示效果更好。

3.2 算法性能分析

為驗證RCACO 算法中不同改進(jìn)策略的作用，本文將不同的改進(jìn)策略重新組合為不同的優(yōu)化方案，并進(jìn)行對比分析，優(yōu)化方案編號如表5 所示。

Table 5 Optimization scheme number表5 優(yōu)化方案編號

從進(jìn)行仿真實驗的15 個不同規(guī)模的TSP 實例中，分別選取小規(guī)模實例Eil51 和rat99、中規(guī)模實例ch130和KroA200、大規(guī)模實例tsp225 和a280，并采用表5 中的四種優(yōu)化方案對每個TSP 實例都進(jìn)行15 次實驗，每次實驗均迭代2 000 次。選取四種優(yōu)化方案在各組TSP 實例中的最小值作為最優(yōu)解，并根據(jù)實驗數(shù)據(jù)計算出誤差率和平均誤差率，實驗結(jié)果如表6 與圖2 所示。

由以上實驗結(jié)果可以看出，在小規(guī)模實例中，四

種優(yōu)化方案均能得到標(biāo)準(zhǔn)最優(yōu)解，而從圖2 中的rat99的迭代情況來看，改進(jìn)算法的收斂速度明顯較快。在中大規(guī)模實例中，優(yōu)化方案A 不論是收斂速度還是求解精度上都不是很理想，其平均誤差率也高于改進(jìn)算法。

Table 6 Performance comparison of optimization schemes表6 優(yōu)化方案性能對比

Fig.2 Comparison of partial test set experiments圖2 部分測試集實驗對比

由優(yōu)化方案B 的實驗數(shù)據(jù)和迭代情況可以看出，在對信息素更新規(guī)則進(jìn)行優(yōu)化并加入?yún)f(xié)同交流策略后，在城市數(shù)小于200 時均能得到標(biāo)準(zhǔn)最優(yōu)解，在城市數(shù)大于200 時也能明顯降低迭代次數(shù)和誤差率。說明協(xié)同交流策略能在提高算法收斂速度的同時，增加算法的多樣性，改善求解精度。

由優(yōu)化方案C 的實驗數(shù)據(jù)和迭代情況可以看出，在方案B 的基礎(chǔ)上加入動態(tài)重組策略后，收斂速度和求解精度得到了進(jìn)一步提高，平均誤差率也得到了明顯下降。說明動態(tài)重組策略能夠提高算法多樣性和改善解的質(zhì)量，但仍未能找到標(biāo)準(zhǔn)最優(yōu)解。

由優(yōu)化方案D 的實驗數(shù)據(jù)和迭代情況可以看出，在方案C 的基礎(chǔ)上加入停滯規(guī)避策略后，改進(jìn)算法能在算法停滯后跳出局部最優(yōu)，在選取的6 組不同規(guī)模的TSP 實例中均能在較少的迭代次數(shù)內(nèi)找到標(biāo)準(zhǔn)最優(yōu)解。說明停滯規(guī)避策略能夠幫助算法跳出局部最優(yōu)，提高全局最優(yōu)解的搜索能力。

3.3 與傳統(tǒng)蟻群算法對比分析

為了分析RCACO 在中小規(guī)模問題中的性能，將ACS、ACS+3opt 及RCACO 分別應(yīng)用于不同城市規(guī)模的TSP 實例中，結(jié)果如表7 與圖3 所示。

Table 7 Performance comparison of test sets for small and medium-sized cities表7 中小規(guī)模城市測試集的性能對比

Fig.3 Experimental comparison of small and medium-sized test sets圖3 部分中小規(guī)模測試集實驗對比

由表7 中實驗數(shù)據(jù)可以看出，對于Oliver30、Eil51、Eil76、rat99、KroA100 等城市數(shù)量在100 及100以下的小規(guī)模TSP 問題中，三種算法都能得到標(biāo)準(zhǔn)最優(yōu)解，但ACS 和ACS+3opt 收斂速度較慢，而RCACO在迭代次數(shù)小于100 的情況下就得到了標(biāo)準(zhǔn)最優(yōu)解，有效提高了算法的收斂速度。對于ch130、ch150、KroB150、KroA200、KroB200 等城市數(shù)量在100 以上及200 以下 的中規(guī) 模TSP 問題，ACS 和ACS+3opt 均陷入局部最優(yōu)，未能得到標(biāo)準(zhǔn)最優(yōu)解，且誤差率偏高。而RCACO 除KroB200 外均在1 000 代之內(nèi)得到了標(biāo)準(zhǔn)最優(yōu)解，KroB200 雖未得到最優(yōu)解，但也有效地將誤差率控制在0.1%以內(nèi)，表明改進(jìn)的算法能夠在提高算法收斂速度的同時，提高解的精度及降低誤差率。

圖3 為Eil76、ch130、KroB150、KroA200 四組實驗使用RCACO 算法得到解的路徑和三種算法在四組實驗中的性能對比。由圖3 可以看出，RCACO 算法顯著改進(jìn)解的質(zhì)量，并且相較經(jīng)典算法，改進(jìn)算法有更好的收斂速度表現(xiàn)。例如在ch130 實驗中，改進(jìn)算法曲線有最快的下降速度和最小的數(shù)據(jù)值，并且具有跳出局部最優(yōu)的能力。

為了進(jìn)一步分析改進(jìn)算法在大規(guī)模問題中的性能表現(xiàn)，分別將三種算法運(yùn)用到tsp225、gil262、a280、rand300、lin318 實驗中，實驗結(jié)果由表8 與圖4 所示。

由表8 可以看出，在5 組大規(guī)模問題中，ACS 和ACS+3opt都未能取得標(biāo)準(zhǔn)最優(yōu)解，且迭代次數(shù)較多，收斂速度都需要進(jìn)一步優(yōu)化，而RCACO 在tsp225 和a280 得到了標(biāo)準(zhǔn)最優(yōu)解，在另外3 組不同規(guī)模城市的實驗中，都能將最優(yōu)解的誤差率控制在1%以下，且迭代次數(shù)都比較少，表明改進(jìn)算法能很好地改善解的質(zhì)量，提高求解速度。

由圖4 可以看出，改進(jìn)算法的收斂速度較快，且具有較強(qiáng)的跳出局部最優(yōu)的能力。例如在tsp225 的實驗中，改進(jìn)算法的曲線圖下降速度明顯優(yōu)于傳統(tǒng)蟻群算法，而且在算法多次迭代沒有變化時，改進(jìn)的算法可以對停滯現(xiàn)象做出處理，跳出局部最優(yōu)，最終得到標(biāo)準(zhǔn)最優(yōu)解。

圖5 是參加實驗的15 個TSP 實例的穩(wěn)定性對比圖，其中，平均誤差率是指對每個TSP 實例進(jìn)行15 次實驗的誤差率均值，也即平均解的誤差率。其值越小，說明算法隨機(jī)進(jìn)行某次實驗得到高質(zhì)量解的概率越大，也即穩(wěn)定性越強(qiáng)。在不同規(guī)模的TSP 實例中，兩種傳統(tǒng)蟻群算法的平均誤差率各有高低，而RCACO 算法的平均誤差率一直優(yōu)于傳統(tǒng)蟻群算法，且穩(wěn)定在2%以內(nèi)，這表明RCACO 算法能有效改善平均解的質(zhì)量，增強(qiáng)算法的穩(wěn)定性。

綜合以上對實驗結(jié)果的對比分析，可以明確看出：相比于傳統(tǒng)蟻群算法而言，RCACO 算法無論是在中小規(guī)模還是大規(guī)模的TSP 實例中，其收斂速度都更快、收斂精度都更高、穩(wěn)定性都更強(qiáng)，表明了改進(jìn)算法能夠有效平衡解的質(zhì)量和收斂速度之間的矛盾，并進(jìn)一步提升了算法的穩(wěn)定性和跳出局部最優(yōu)的能力。

Table 8 Performance comparison of test sets for large-scale cities表8 大規(guī)模城市測試集的性能對比

Fig.4 Experimental comparison of large-scale test sets圖4 部分大規(guī)模測試集實驗對比

Table 9 Comparison of RCACO and other improved algorithms表9 RCACO 與其他改進(jìn)算法對比

Fig.5 Comparison of algorithm stability圖5 算法穩(wěn)定性對比

3.4 與當(dāng)今最新改進(jìn)算法對比分析

為進(jìn)一步檢驗算法的性能，本文將RCACO 算法與最新的改進(jìn)蟻群算法及其他算法進(jìn)行比較，結(jié)果如表9 所示。表中數(shù)據(jù)為各算法所得到的最優(yōu)解及其與標(biāo)準(zhǔn)最優(yōu)解之間的誤差率。

根據(jù)表9 的對比結(jié)果可以看出：在小規(guī)模TSP 問題中，RCACO 算法求解的精度不遜色于其他算法；在中大規(guī)模的TSP 問題中，其他算法未能求出標(biāo)準(zhǔn)最優(yōu)解的情況下，RCACO 算法依舊可以找到標(biāo)準(zhǔn)最優(yōu)解。由此可見，RCACO 算法求解旅行商問題的性能更為高效。

4 結(jié)束語

針對傳統(tǒng)蟻群算法收斂速度慢、易陷入局部最優(yōu)等問題，本文提出了一種基于動態(tài)重組和協(xié)同交流策略的蟻群優(yōu)化算法（RCACO）。算法將蟻群劃分為貪婪蟻群和探索蟻群，兩類蟻群分別執(zhí)行不同的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則，共同向最優(yōu)解靠近，有效平衡了算法的收斂速度和多樣性。其次，本文提出了一種基于線索二叉樹的新型重組算子，并采用不同的重組策略對解集進(jìn)行動態(tài)重組，避免了傳統(tǒng)的盲目隨機(jī)重組，有效提升了算法的多樣性和平均求解質(zhì)量。此外，本文提出了一種基于相似度和潛力值的協(xié)同交流策略，讓兩類蟻群將潛力較大的優(yōu)良路徑片段作為共享信息進(jìn)行種群間的交流，有效提高了算法的收斂速度。最后，算法還加入了停滯規(guī)避策略，保證了算法后續(xù)循環(huán)的有效性，大大增強(qiáng)了算法跳出局部最優(yōu)的能力。

在標(biāo)準(zhǔn)TSP 實例上的仿真結(jié)果表明，改進(jìn)的蟻群算法在收斂速度、求解精度和算法穩(wěn)定性等方面均有顯著提升。算法能在較少的迭代次數(shù)內(nèi)找到中小規(guī)模TSP 問題的最優(yōu)解，能較好改善大規(guī)模TSP 問題上解的平均質(zhì)量，但對于超大規(guī)模TSP 問題求解精度仍需進(jìn)一步提高。為提高超大規(guī)模TSP 問題中解的精度，今后將在優(yōu)化多種群之間的博弈策略和信息素更新策略上作進(jìn)一步研究。