基于動態重組和協同交流策略的蟻群優化算法

劉一凡，游曉明+，劉 升

1.上海工程技術大學 電子電氣工程學院，上海 201620

2.上海工程技術大學 管理學院，上海 201620

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

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

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

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

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

1 相關工作

1.1 ACS 蟻群算法原理

1.1.1 路徑構建

ACS 算法中每只螞蟻從城市i到城市j的狀態轉移規則如下：

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

本文中的兩類蟻群沿用了ACS 的狀態轉移規則，但兩類算法分別采用不同的q0。貪婪蟻群采用較大的q0，對當前最優區域進行深度探索，加快收斂速度；探索蟻群采用較小的q0，對其他次優區域進行廣度搜索，增加算法多樣性。

1.1.2 信息素的更新

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

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

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

全局信息素更新：當所有螞蟻都完成路徑構建后，算法會對當前全局最優路徑進行全局信息素更新，公式為：

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

1.2 線索二叉樹

在二叉樹的節點上加上線索的二叉樹稱為線索二叉樹，線索二叉樹中的線索能記錄每個節點前驅和后繼信息。為了區別線索指針和孩子指針，在每個節點中設置兩個標志ltag 和rtag。

傳統線索二叉樹的節點結構如表1 所示。

Table 1 Node structure of traditional clew binary tree表1 傳統線索二叉樹的節點結構

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

2 改進策略

2.1 多種群信息素更新策略

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

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

2.2 動態重組策略

2.2.1 改進線索二叉樹

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

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

例如有一個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序列中的前驅節點都為3，后繼節點都為5，說明3→4 和4→5 均是重復路徑，以此類推，兩個解向量具有4 個相同最短子路徑:2→3，3→4，4→5，7→8，即SAB=0.4。

2.2.2 新型動態重組算子

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

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

Table 2 Node structure of improved cue binary tree表2 改進的線索二叉樹的節點結構

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

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

2.2.3 動態重組策略

（1）種群內部動態重組

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

（2）種群之間動態重組

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

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

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

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

2.3 協同交流策略

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

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

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

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

2.3.2 引入潛力值的激勵策略

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

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

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

2.4 停滯規避策略

傳統蟻群算法迭代一定次數后，可能在次優路徑上積累大量信息素，進而出現停滯現象，而算法停滯后的循環都是在做無用功，為加強算法跳出局部最優的能力，應對停滯現象做出檢測及相應處理措施。

本文的算法停滯檢測分為兩種：第一種是當本次迭代所有螞蟻所構建的路徑相似度過高，甚至趨于一條路徑；第二種是在一定迭代次數內，仍未出現更優的解。具體檢測判斷公式如下：

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

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

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

2.5 算法步驟和算法流程圖

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

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

算法步驟：

步驟1參數初始化。

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

步驟3當每類蟻群完成路徑構建后，運用新型重組算子，根據式（9）對蟻群所產生的解集進行內部動態重組。

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

步驟5將兩類蟻群所產生解集混合并分組，根據式（10）對兩類蟻群之間進行動態重組，然后混洗蟻群。

步驟6進入協同交流階段，計算兩類蟻群的相似度，然后根據式（11）判斷是否進行交流，若是，轉步驟7，否則，轉步驟8。

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

步驟8根據式（13）對算法是否停滯做出檢測，若是，轉步驟9，否則，轉步驟10。

步驟9根據式（14）對算法停滯做出相應處理。

步驟10當NC≤NCmax時，NC=NC+1，跳轉到步驟2；否則，轉到步驟11。

步驟11輸出最優解。

3 實驗仿真

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

其中，LACO為三種ACO 算法所找到的最優解，LBest為測試集的標準最優解。

3.1 參數設置

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

Table 4 Setting of parameters表4 參數設置

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

經過多次實驗，統計對比其結果發現，參數設置如表4 所示效果更好。

3.2 算法性能分析

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

Table 5 Optimization scheme number表5 優化方案編號

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

由以上實驗結果可以看出，在小規模實例中，四

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

Table 6 Performance comparison of optimization schemes表6 優化方案性能對比

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

由優化方案B 的實驗數據和迭代情況可以看出，在對信息素更新規則進行優化并加入協同交流策略后，在城市數小于200 時均能得到標準最優解，在城市數大于200 時也能明顯降低迭代次數和誤差率。說明協同交流策略能在提高算法收斂速度的同時，增加算法的多樣性，改善求解精度。

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

由優化方案D 的實驗數據和迭代情況可以看出，在方案C 的基礎上加入停滯規避策略后，改進算法能在算法停滯后跳出局部最優，在選取的6 組不同規模的TSP 實例中均能在較少的迭代次數內找到標準最優解。說明停滯規避策略能夠幫助算法跳出局部最優，提高全局最優解的搜索能力。

3.3 與傳統蟻群算法對比分析

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

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

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

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

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

為了進一步分析改進算法在大規模問題中的性能表現，分別將三種算法運用到tsp225、gil262、a280、rand300、lin318 實驗中，實驗結果由表8 與圖4 所示。

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

由圖4 可以看出，改進算法的收斂速度較快，且具有較強的跳出局部最優的能力。例如在tsp225 的實驗中，改進算法的曲線圖下降速度明顯優于傳統蟻群算法，而且在算法多次迭代沒有變化時，改進的算法可以對停滯現象做出處理，跳出局部最優，最終得到標準最優解。

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

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

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

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

Table 9 Comparison of RCACO and other improved algorithms表9 RCACO 與其他改進算法對比

Fig.5 Comparison of algorithm stability圖5 算法穩定性對比

3.4 與當今最新改進算法對比分析

為進一步檢驗算法的性能，本文將RCACO 算法與最新的改進蟻群算法及其他算法進行比較，結果如表9 所示。表中數據為各算法所得到的最優解及其與標準最優解之間的誤差率。

根據表9 的對比結果可以看出：在小規模TSP 問題中，RCACO 算法求解的精度不遜色于其他算法；在中大規模的TSP 問題中，其他算法未能求出標準最優解的情況下，RCACO 算法依舊可以找到標準最優解。由此可見，RCACO 算法求解旅行商問題的性能更為高效。

4 結束語

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

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