孟靜雯，游曉明+，劉 升

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

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

旅行商問題（traveling salesman problem，TSP）是指從任一個地方出發(fā)，遍歷完所有的城市后，最終回到出發(fā)點，使所走的總路程最短。

20 世紀90 年代，意大利學者Dorigo 等人提出蟻群系統(tǒng)（ant system）[1]，這是受螞蟻覓食行為的啟發(fā)提出的一種元啟發(fā)式算法，隨后引起了專家學者的重視，并運用于求解TSP。最初螞蟻系統(tǒng)（ant system，AS）有三個不同的版本，分別稱為螞蟻數(shù)量（ant quantity）、螞蟻密度（ant-density）、螞蟻周期（antcycle）[2]。如今經(jīng)常使用的是螞蟻周期（ant-cycle）這個版本。隨著測試規(guī)模的擴大，AS 算法在工作過程中存在需要較長搜索時間和易于陷入局部最優(yōu)問題，隨后Dorigo 等人在AS 算法的基礎上進行了改進——使用精華策略的螞蟻系統(tǒng)（elitist strategy for ant system，EAS）[2]。它的思想與AS 不同之處在于向全局最優(yōu)路徑添加額外的反饋信息。1996 年，Dorigo在AS的基礎之上提出了蟻群系統(tǒng)（ant colony system，ACS）[3]，加入全局信息素更新規(guī)則，并且采用了一種更積極的行為選擇規(guī)則，使得ACS 在解決規(guī)模較大的TSP 問題時會得到更優(yōu)解。然而ACS 算法在求解TSP問題時仍然存在收斂速度慢、多樣性較差的問題。

針對上述問題，許多改進策略被提出。張濤等人[4]將螞蟻劃分為不同等級，采取等級反饋機制策略對不同等級的螞蟻走過的路徑進行不同程度的正或負反饋，加快算法收斂速度。王昕宇等人[5]利用全局記憶矩陣指導負載螞蟻向最相似的數(shù)據(jù)對象方向前進，避免螞蟻漫無目的移動，保證了算法較快收斂。這些改良方案雖然提高了收斂性，但是沒有提高解的質量。針對這一缺點，張玉茹等人[6]在進行路徑構建時，引入貪心算法平衡信息素濃度與啟發(fā)式信息兩者對螞蟻的影響，加強尋優(yōu)性能。運用插入、逆轉變異算子對路徑優(yōu)化，提高解的質量。趙亞文等人[7]把捕食搜索策略與蟻群算法融合，在最優(yōu)解附近進行搜索，提高尋優(yōu)潛力。采用更換信息素揮發(fā)策略，優(yōu)化各路徑信息素分布，跳出局部最優(yōu)。彭岳等人[8]將蟻群分為多個蟻群系統(tǒng)，并設置不同的參數(shù)來區(qū)分蟻群，每個蟻群各自搜索最優(yōu)路徑，多蟻群之間進行交流學習增強尋優(yōu)能力，增加算法多樣性避免陷入停滯。這三種改進的算法提高了跳出局部最優(yōu)的能力，多樣性增加，卻沒有考慮收斂性能。針對這一缺點，周克良等人[9]運用區(qū)域破壞與重建策略提高解的質量；引用2-Opt 算法進行局部優(yōu)化，解決由于信息素堆積造成的點交叉現(xiàn)象，增加全局搜索的能力，加快算法收斂速度的同時提高算法多樣性。袁汪凰等人[10]采用兩異構種群并行搜索，并采用獎罰機制進行不同的反饋，平衡算法的收斂速度和多樣性。姜道銀等人[11]運用信息交流策略對選取的一部分較優(yōu)路徑進行更新，改進解的質量，避免解多樣性不足。與此同時該策略通過對部分較優(yōu)解進行維變量互換得到優(yōu)質子解，可以加快收斂。這些改進的策略雖然平衡了算法收斂性和多樣性，但是對于大規(guī)模問題有待進一步改善。

因此，本文提出結合協(xié)同機制與動態(tài)調控策略的雙蟻群算法（dynamic regulation strategy and collaborative mechanism,DCACS）。將蟻群根據(jù)適應度值動態(tài)劃分為導向蟻和合作蟻兩個異構雙蟻群，運用協(xié)同機制兩個種群分工合作找到最優(yōu)解。導向蟻考慮周圍信息素的濃度的影響，在路徑選擇時引入傳播因子，降低螞蟻一直選擇某個城市的概率，從而改變螞蟻的選擇，增強尋優(yōu)性能。合作蟻在局部信息素更新時引入合作算子，受導向蟻中的最優(yōu)路徑的影響，當路徑相似度達到閾值，合作蟻啟動合作算子，加快算法收斂速度。兩個異構雙種群分工合作，在保證算法多樣性的同時增強收斂性。當所有螞蟻完成周游時，運用動態(tài)調控策略，在全局信息素更新時引入自適應調控算子，對全局最優(yōu)路徑進行正向激勵或反向懲戒的調整，不僅加快了算法收斂速度，又能防止算法過早停滯。實驗結果表明，本文提出的改進蟻群算法相較傳統(tǒng)的蟻群算法在TSP 問題上算法多樣性和收斂速度有了明顯提高，并且在大規(guī)模問題上優(yōu)勢更加明顯。

1 前期工作

1.1 蟻群系統(tǒng)

1.1.1 路徑選擇

蟻群算法（ACS）根據(jù)偽隨機比例規(guī)則選擇下一個要遍歷的城市j，如式（1）：

式中，q0(0 ≤q0≤1)是一個參數(shù)，q0值大小影響著對新路徑的探索度；q是一個隨機變量，分布區(qū)間為[0,1]；ηij=1/dij代表啟發(fā)式信息；β是參數(shù)，它的大小決定啟發(fā)式信息在螞蟻選擇城市時發(fā)揮的作用；τij表示邊(i,j)上信息素的值；J是一個隨機變量，如式（2）：

其中，α的大小決定信息素的影響力；allowed代表了位于城市i的螞蟻k可以選擇下個城市的集合。

1.1.2 全局信息素更新

在ACS 中，只有至今最優(yōu)的一只螞蟻才被允許在每一次迭代完成后釋放信息素，即只有全局最佳巡回路線上的信息素才會得到加固。全局信息素更新機制與式（1）一起使用，是為了使搜索更具針對性。更新規(guī)則如式（3）：

式中，Lgb表示至今全局最優(yōu)路徑；0<ρ<1 表示全局信息素揮發(fā)率；表示增量。

1.1.3 局部信息素更新

局部信息素更新的作用在于：每只螞蟻遍歷完所有城市后，調用式（5）進行局部信息素更新，使得該路徑上的信息素會有一定程度的揮發(fā)，該路徑被選中的概率相對減小，其他路徑被探索的幾率增大。

其中，0<ξ<1 為局部信息素揮發(fā)率；τ0=1/(nCnn)為各邊信息素初值，n代表城市數(shù)目，Cnn是由最近鄰方法得出的路徑的長度。

1.2 3-opt算子

3-opt[12]是局部優(yōu)化的一種常用方法，通過對全局最優(yōu)解進行優(yōu)化得到更優(yōu)解。優(yōu)化過程通常分為以下幾步：（1）選取待優(yōu)化路徑上的任意三條邊；（2）斷開后嘗試與原先不同的連接方式；（3）計算重新連接后的長度并與原路徑長度對比，若重新連接后的路徑更短，則選用優(yōu)化后的連接方式。反之，保留原路徑；重復（2）、（3），直至完成所有連接方式，其中一種優(yōu)化方式如圖1。

Fig.1 3-opt schematic diagram圖1 3-opt示意圖

1.3 蝴蝶算法

蝴蝶算法（butterfly algorithm，BA）是Arora等人[13-14]依據(jù)蝴蝶覓食等行為的啟發(fā)提出的一種智能優(yōu)化算法。每只蝴蝶都可以在空中產(chǎn)生一定強度的氣味，散發(fā)后被其他蝴蝶感知到，蝴蝶通過感知空氣中的氣味向著氣味濃度大的方向移動，以此來確定食物中心或者伴侶的方向。這就是蝴蝶如何與其他蝴蝶和社會知識網(wǎng)絡分享自己的個人信息。香味大小F計算公式如式（6）：

式中，γ為冪指數(shù)；I為刺激強度；c為蝴蝶感知形式；F為香氣的感知強度。

2 改進的蟻群算法

2.1 種群的劃分

蟻群算法在求解旅行商問題時對于加快收斂速度與保持路徑多樣性總是不可兼得，探索過度導致收斂性較差，而學習過快忽略了解的質量。為了協(xié)調蟻群間的探索和利用，本文采用異構雙種群的結構，將蟻群劃分為導向蟻和合作蟻。導向蟻負責探索新路徑，提高算法尋優(yōu)的多樣性，避免陷入停滯，合作蟻負責加快算法的收斂速度。為了保證前期算法多樣性，后期加快收斂，故隨著迭代次數(shù)的增多，導向蟻逐漸減少，合作蟻逐漸增加。規(guī)定路徑長短用適應度值來描述，路徑越短表示適應度值越高，每次迭代完根據(jù)適應度值進行由高到低的排序，重新劃分導向蟻與合作蟻。導向蟻由適應度值較高即路徑較短的螞蟻組成，合作蟻由適應度值較低即路徑較長的螞蟻組成，兩蟻群的數(shù)量如式（7）、式（8）：

式中，m為螞蟻總數(shù)，Nc為最大迭代次數(shù)，N為當前迭代數(shù)，A、B分別代表導向蟻、合作蟻的數(shù)量。x為一比例系數(shù)，比例系數(shù)的大小影響螞蟻數(shù)量變化速度，如圖2。若比例系數(shù)過大（如x=1），將會使合作蟻數(shù)量增長過快，算法收斂速度加快。但同時解的多樣性較差，容易陷入局部最優(yōu)，得到的是局部最優(yōu)解。若比例系數(shù)過?。ㄈ鐇=5/8），合作蟻增長速度較慢，導向蟻較長時間處于優(yōu)勢地位，導致算法長期處于探索階段，收斂速度較慢。為了更好地平衡多樣性與解的精度，根據(jù)實驗確定x的取值，實驗見3.1.2 小節(jié)。

Fig.2 Diagram of the number of ants in different proportion coefficients圖2 不同比例系數(shù)下螞蟻數(shù)量變化圖

圖2 為不同比例系數(shù)下螞蟻數(shù)量變化曲線圖，通過實驗測得x取7/8 時算法性能最好。由圖2 可以看出，合作蟻的數(shù)量與迭代次數(shù)呈正相關，導向蟻數(shù)量與迭代次數(shù)呈負相關，且由圖像斜率可以看出整個變化過程兩種群螞蟻數(shù)量變化平緩。算法前期導向蟻的數(shù)量較多，發(fā)揮主導作用，保證路徑的多樣性，提高解的質量；算法后期合作蟻的數(shù)量較多，合作蟻發(fā)揮主要作用，加快收斂。為了保證導向蟻可以繼續(xù)探索，避免陷入局部最優(yōu)的困境，最后一次迭代時導向蟻的數(shù)量仍為螞蟻總數(shù)的

2.2 協(xié)同機制

協(xié)同是兩個或兩個以上的個體或群體共同朝著某一目標前進，且兩者相互配合產(chǎn)生的效果大于各個個體單獨作用時的總和。故本文引入?yún)f(xié)同機制，把蟻群劃分為異構雙蟻群：導向蟻和合作蟻，雙蟻群分工協(xié)作尋找最優(yōu)路徑。導向蟻職能是擴大搜索范圍，開發(fā)新路徑；合作蟻職能是提高算法收斂性能。引入?yún)f(xié)同機制把兩個蟻群聯(lián)系在一起，達到合作交流、信息共享、相互促進的目的，使得算法能夠更快地找到全局最優(yōu)解，同時保證算法多樣性，避免算法過早陷入停滯狀態(tài)。

2.2.1 傳播因子及傳播域

若某路徑在之前的迭代中多次出現(xiàn)，出現(xiàn)頻率較高，這些路徑上的信息素會逐漸積累，最終得到的這個解往往是局部最優(yōu)解，且這種局部最優(yōu)不易跳出。為了避免算法過早收斂于某個局部最優(yōu)解，造成算法早熟，將蝴蝶算法的思想引入導向蟻中，擴大搜索范圍。導向蟻在選擇下一個城市時可以感知周圍路徑上的信息素，把這種影響定義為傳播因子f，計算公式如式（9）：

式中，i為當前螞蟻的位置，j為螞蟻將要訪問的城市，Δτij為路徑(i,j)上的信息素；為以i為圓心的區(qū)域中所有可訪問節(jié)點的路徑信息素總和；n為以i為圓心的區(qū)域中可以訪問的城市個數(shù)。導向蟻在以i為圓心的區(qū)域中，到所有可訪問節(jié)點的信息素總和是一定的。要訪問城市不同，邊(i,j)上的信息素量不同。當邊(i,j)上信息素值較小時，邊(i,j)上的信息素量與鄰域信息素總和差值較大，傳播因子f的值越大。

引入傳播因子后的狀態(tài)轉移規(guī)則如2.2.2 小節(jié)的敘述。當路徑(i,j)上的信息素值較大時，即與鄰域信息素總和差值較小時，傳播因子的值較小，使得當前最優(yōu)城市被選擇的概率較沒有引入傳播因子時減小；當路徑(i,j)上的信息素較小，即與鄰域信息素總和差值較大時，傳播因子的值較大。使得螞蟻在選擇下個城市時能跳出當前最優(yōu)城市，轉換目標，增大較優(yōu)城市被選擇的概率，擴大搜索路徑，提高算法多樣性。

文獻[6]借鑒貪心算法的思想，在概率選擇公式中引入間接期望啟發(fā)式及相應的啟發(fā)式因子即考慮當前節(jié)點到其他節(jié)點距離的均值對路徑構建的影響，增加算法多樣性。文獻[10]通過設置獎懲模型，對學習后較差的種群進行懲罰，增加種群多樣性。文獻[15]引入探索率因子，通過對全局概率選擇方式進行修正，增大信息素較弱的路徑被選擇的概率，增強搜索能力。這些改進方式對于小規(guī)模問題而言算法多樣性整體得到了提高，但對于大規(guī)模問題，隨著信息素的積累，算法在中后期依然容易陷入局部最優(yōu)，解的精度并沒有改善。

因此，本文借鑒蝴蝶算法的思想在導向蟻構建路徑時引入傳播因子。算法前期路徑信息素差距不大，傳播因子的引入可以平衡各路徑被選擇的概率，使螞蟻移動的隨機性增強，擴大搜索范圍，達到提升算法多樣性的目的。在算法中后期，特別是對于大規(guī)模城市而言，路徑信息素差距增大，導致選擇可能會被局限在某個城市上，陷入局部最優(yōu)。傳播因子的引入可以降低出現(xiàn)次數(shù)最高的城市被選擇的概率，提高較優(yōu)路徑被選擇的概率。深入挖掘潛力值較高的路徑，避免了算法由于當前路徑信息素濃度影響力過大而陷入局部最優(yōu)，從而提高解的質量。

考慮到螞蟻進行路徑選擇時除了受信息素濃度的影響，還受到兩城市之間路徑長短的影響，因此距離過大的城市即使考慮進去也不會作為下一個訪問的節(jié)點。為了進一步節(jié)省程序運行時間，提出傳播域的概念。但是傳播域過小往往會忽略掉潛在最優(yōu)，在一定程度上抑制了算法的多樣性，不能保證解的質量。最終經(jīng)過多次實驗分析得到傳播域的定義：

以i為圓心，r為半徑畫圓得到圓形傳播域,半徑r大小如式（10）：

式中，n表示可以訪問的城市的總數(shù)，din表示城市i到城市n的距離。

本文選取的TSP 城市數(shù)目較多且分布比較緊密，同時半徑r的選擇相對較大，保證了解的質量。傳播域之外的城市到i點的距離較長，最終也不會考慮其作為下一個要遍歷的地方。因此傳播域在保證解的質量的同時減少了程序的運行時間。

2.2.2 改進的狀態(tài)轉移規(guī)則

導向蟻中的螞蟻在選擇下一個城市時除了受ηij、τij這兩個參數(shù)的影響外，還要考慮傳播因子f產(chǎn)生的影響。考慮到周圍信息素的影響引入傳播因子，使得導向蟻在進行路徑選擇時增大較優(yōu)路徑周圍城市被選擇的概率，擴大搜索范圍。改進后的路徑選擇規(guī)則如式（11）：

在經(jīng)典ACS 算法中，各路徑信息素初始值相同，前期主要依據(jù)城市之間的距離選擇下個節(jié)點，隨著迭代次數(shù)的增多，局部距離較短的路徑上信息素濃度過高，導致選擇范圍減小，陷入停滯狀態(tài)，難以得到更優(yōu)解。傳播因子的引入影響城市被選擇的概率，若當前城市i到下一城市j路徑上的信息素濃度與周圍信息素濃度總和相差較小時，受周圍信息素濃度的影響較小，使得城市j被選中的概率比不考慮傳播因子時被選中的概率減小。因此傳播因子的引入使得原先被選中概率大的城市概率減小，從而調整選擇的目標，增加探索未使用過的邊的機會，提高算法多樣性，避免算法前期由于啟發(fā)式信息發(fā)揮主要作用造成信息素積累而陷入局部最優(yōu)的問題。

2.2.3 路徑相似度

所有的導向蟻進行局部信息素更新后，合作蟻按照ACS 的規(guī)則開始路徑構建，在局部信息素更新之前，每只螞蟻都要與導向蟻中的最優(yōu)路徑計算路徑相似度S。通過建立數(shù)學模型來求解路徑相似度：Route_Abest為導向蟻中最優(yōu)路徑構成的位置矩陣，如式（12）。Route_Bk為合作蟻中第k個螞蟻路徑構建完得到的位置矩陣，如式（13）。導向蟻的最優(yōu)路徑與第k個合作蟻的公共路徑用Same表示，如式（14）。最后路徑相似度S的計算公式如式（15）：

式中，Same表示公共路徑；numberSame表示導向蟻的最優(yōu)路徑與第k個合作蟻相同路徑的個數(shù)；r表示城市數(shù)。當?shù)趉個合作蟻得到的路徑與導向蟻的最優(yōu)路徑重復率較高時，即路徑相似度達到閾值時，合作蟻進行局部信息素更新時啟動合作算子，使得當前合作蟻構建的路徑上保留的信息素量增多。這一過程導向蟻發(fā)揮了引導作用，加強了兩蟻群之間的合作，從而加快算法的收斂速度。

2.2.4 基于合作算子的局部信息素更新

當路徑相似度達到閾值時，合作蟻進行局部信息素更新時引入合作算子σ，如式（16）、式（17）：

局部信息素更新的目的是通過信息素的揮發(fā)限制較優(yōu)路徑信息素的積累，增加多樣性。由式（16）可看出，合作算子0<σ<1。引入合作算子后，使得信息素的揮發(fā)系數(shù)在[0,0.1]之間動態(tài)變化。合作算子與導向蟻中最優(yōu)路徑上信息素總量有關，信息素積累得越多，說明該路徑越優(yōu)，合作算子σ值就越小，進而合作蟻中局部信息素揮發(fā)率越小，達到加快信息素積累的目的。當合作蟻與導向蟻的最佳路徑相似度達到閾值，合作蟻在局部信息素更新時會啟動合作算子，合作蟻進行局部信息素更新時路徑上信息素的揮發(fā)量比沒有引入合作算子揮發(fā)量減少，即路徑上剩余的較原來多。加快算法的收斂速度，使得信息素的正反饋作用得以體現(xiàn)。且在算法后期合作蟻占據(jù)主導地位，進一步提升了算法收斂性能。

2.3 動態(tài)調控策略

導向蟻與合作蟻都完成路徑構建后，運用動態(tài)調控策略進行全局信息素更新。當此次迭代導向蟻與合作蟻都遍歷完成，蟻群的全局最優(yōu)路徑都要被檢測，即此次迭代得到的最優(yōu)解與全局最優(yōu)比較：若第t次迭代得到更優(yōu)解，表明此時路徑上的信息素分布更具指導性，進行全局信息素更新時實施正向激勵，加快收斂；若第t次迭代得到的最優(yōu)解劣于全局最優(yōu)解，表明該當前路徑信息素分布沒有指導作用，進行全局信息素更新時實施反向懲戒，減少信息素積累，避免陷入停滯狀態(tài)；若第t次迭代得到的最優(yōu)解與全局最優(yōu)解相同，信息素更新規(guī)則不做變動。由此引入適應性調控算子U，如式（18）、式（19）。改進的全局信息素更新公式如式（20）。

式中，N為當前迭代數(shù)；global_best為前(t-1)次的最短路徑，即全局最優(yōu)；length_best(t)表示第t次迭代產(chǎn)生的最短路徑。由式（18）、式（19）可以看出，適應性調控算子與迭代次數(shù)和路徑長度有關，隨著迭代次數(shù)的增大而減小，且隨著兩個最優(yōu)路徑差值的增大而減小。前期適應性調控算子的值較大，影響較大，使信息素更具導向性。后期迭代次數(shù)N值較大，適應性調控算子值較小，對更新機制產(chǎn)生的影響也較小，避免U產(chǎn)生的影響過大使算法陷入局部最優(yōu)。由式（20）可以看出，當?shù)趖次迭代找到更優(yōu)解時，適應性調控算子U發(fā)揮正反饋作用，加快收斂。當?shù)趖次迭代找到的最優(yōu)解與全局最優(yōu)相同時，適應性調控算子U不發(fā)揮作用即不做任何改變。當?shù)趖次迭代找到的最優(yōu)解劣于全局最優(yōu)時，適應性調控算子U發(fā)揮負反饋作用，調節(jié)路徑上的信息素，增加次優(yōu)路徑被選中的幾率，避免算法陷入停滯狀態(tài)。

2.4 算法性能分析

蟻群算法的改進主要是提高算法多樣性、加快收斂速度這兩方面的性能，但是往往改進的單種群蟻群算法不能兼顧兩方面的性能，一方面的性能得到了提高，另一方面性能會變差。為了平衡兩者之間的矛盾，把蟻群動態(tài)地劃分為異構雙蟻群：導向蟻、合作蟻，兩蟻群在迭代過程中執(zhí)行各自的任務。導向蟻在路徑構建時，若當前城市到下一城市信息素濃度較高，受鄰域信息素的影響該城市被選中的概率較之前低；反之，若當前城市到下一城市信息素濃度較低，該城市被選擇的概率較之前略有提高。以此增大次優(yōu)城市被選中的概率，擴大搜索范圍，擴展新路徑提高算法多樣性。當所有導向蟻構建完路徑后合作蟻開始構建，每個合作蟻構建的路徑都要與導向蟻中的最優(yōu)路徑進行比較，當路徑相似度達到閾值時，合作蟻進行局部信息素更新時啟動合作算子，使得路徑上信息素揮發(fā)量減少，積累量增多。發(fā)揮信息素的導向作用，加快收斂。兩蟻群相互合作以平衡算法收斂速度和解的多樣性。

從全局來看，導向蟻與合作蟻隨著迭代次數(shù)動態(tài)變化，前期導向蟻數(shù)量多于合作蟻，導向蟻發(fā)揮主要作用增加解的多樣性。隨著迭代次數(shù)的增加，導向蟻數(shù)量逐漸減少，合作蟻數(shù)量增多，合作蟻發(fā)揮主要作用使得較優(yōu)路徑上的信息素快速積累，加快收斂，得到最優(yōu)路徑。

在全局信息素更新規(guī)則中引入適應性調控算子U進行調控。若此次迭代出現(xiàn)更優(yōu)路徑，調控算子則對該路徑信息素進行正反饋調整，即對該最優(yōu)路徑信息素進行獎勵，使信息素更具導向性，加快算法收斂。若此次迭代得到的路徑較差，調控算子則在全局信息素更新時對最優(yōu)路徑信息素進行懲罰，減少最優(yōu)路徑信息素的積累，使?jié)撛谧顑?yōu)路徑被選擇的概率增大，提高路徑多樣性。前期適應性調控算子的值較大，影響較大。后期迭代次數(shù)較大，適應性調控算子值變小，對更新機制產(chǎn)生的影響也較小，避免產(chǎn)生過大的影響使算法陷入局部最優(yōu)。達到了通過控制調控算子來平衡收斂速度與多樣性的目的。

2.5 算法流程圖

DCACS 算法流程圖如圖3。首先對蟻群劃分，第一次迭代時所有螞蟻劃分為導向蟻，導向蟻在路徑構建時引入傳播因子，擴大搜索范圍。每次迭代完后根據(jù)螞蟻的路徑優(yōu)劣根據(jù)式（7）、式（8）把螞蟻分為導向蟻與合作蟻，標記路徑較好的螞蟻為導向蟻，其余為合作蟻，且隨著迭代次數(shù)的增多導向蟻的數(shù)量是逐漸減小的。合作蟻會受到導向蟻中最優(yōu)路徑的影響，當路徑相似度達到閾值時，合作蟻啟動合作算子，使得路徑上保留的信息素量增多，發(fā)揮導向作用，加快收斂。最后運用動態(tài)調控策略進行全局信息素更新，對全局最優(yōu)路徑上的信息素進行正向激勵或反向懲戒，從而實現(xiàn)算法多樣性與收斂性的平衡。

Fig.3 Algorithm flow chart圖3 算法流程圖

2.6 算法復雜度分析

從圖3 DCACS 的流程圖分析可看出，兩蟻群搜索過程是相互獨立的，故DCACS 的最大時間復雜度為O(m×r×1+(m1×r+m2×r)×(Nc-1))，其中m為螞蟻總數(shù)，m1、m2分別為導向蟻、合作蟻的數(shù)量，r為城市數(shù)，Nc為最大迭代次數(shù)，經(jīng)計算得到改進后算法的最大時間復雜度為O(m×r×Nc)，與原算法ACS的相同。因此本文算法沒有增大復雜度，且本文提出的DCACS 算法在收斂性與尋優(yōu)性方面較經(jīng)典算法有明顯的提高。

2.7 算法收斂性分析

在DCACS 算法中，因為信息素的蒸發(fā)作用，信息素水平的最大限制τmax是漸進受限的。為了便于計算，把DCACS 算法中的兩種信息素更新機制統(tǒng)一記 作τij(θ+1)=(1-φφ)τij(θ)+φφb，當φ=ξ，φ=σ，b=τ0時表示局部更新機制；當φ=ρ，φ=1，b=qf(sbs)時表示全局更新機制；最后計算出τij(θ)=(1-φφ)θτ0+b[1-(1-φφ)θ]，當θ→∝時，由于τ0為初始值，故τmin=τ0。

由于信息素存在上下界，確保了式（11）中任一概率pmin>0 。若螞蟻訪問下個城市j時，路徑(i,j)上的信息素量與啟發(fā)式信息乘積的結果不是最大值，則選中該邊的概率為，在ACO 算法中pmin下 界為。因此對無窮大的θ和任意小的正數(shù)ε，P*(θ)≥1-ε成立，θ表示迭代次數(shù)，P*(θ)表示最少一次得到最優(yōu)路徑的概率，根據(jù)以上可得。因此只要保證迭代次數(shù)，DCACS 算法值是收斂的且概率為1。

3 實驗仿真

為了檢驗改進后算法DCACS 的收斂性和尋優(yōu)能力等，本文使用Matlab2017a軟件進行仿真。

3.1 參數(shù)設置

3.1.1 參數(shù)說明

實驗中用到的參數(shù)有m、α、β、ρ、ξ、q0、k0，其中m為螞蟻的數(shù)量，當螞蟻數(shù)量過多時，m只螞蟻并行搜索，全局搜索能力增強，較優(yōu)路徑信息素比較平均，信息素導向作用不強，導致算法收斂速度較慢；當螞蟻數(shù)量較少時，對于大規(guī)模城市，搜索能力差，得到的解的質量不高。α為信息素的影響因子，α值越大，信息素的導向作用越明顯，但值過大會導致算法過早陷入局部最優(yōu)。β為期望啟發(fā)式的影響因子，值越大，螞蟻在選擇下個城市時選擇局部最短路徑的概率越大，導致算法多樣性和解的質量較差。ρ和ξ分別表示全局信息素、局部信息素揮發(fā)率，揮發(fā)率的大小影響著算法收斂速度。q0為偽隨機因子，其大小影響著對新路徑的探索度。q0越小，螞蟻探索新路徑的概率越大，同時收斂速度較慢；反之，q0越大，螞蟻集中搜索至今最優(yōu)路徑，雖然提高了收斂速度但是搜索能力變差，得到的解的質量不高。k0為啟動合作算子的閾值。當k0設置過小，導致路徑相似度較小時就可以跟隨導向蟻的最優(yōu)路徑，算法過早收斂，易陷入停滯狀態(tài)；當k0設置過大，收斂速度較慢。

3.1.2 參數(shù)確定

3.1.2.1 經(jīng)典參數(shù)的確定

正交實驗是研究多因素、多水平組合的一種實驗方法，利用正交表進行實驗設計，通過少量的實驗代替全面的實驗。故本文采用五因素四水平的正交實驗來確定經(jīng)典算法ACS 的參數(shù)α、β、ρ、ξ、q0的取值，各因素水平如表1。以kroA100 為實驗對象，每組進行10 次實驗，統(tǒng)計每個組合方案的平均解，制定的L16(45)正交表及測試結果見表2。根據(jù)各因素水平下的平均解的總和確定最優(yōu)方案，實驗結果分析見表3。

Table 1 Level table of each factor表1 各因素水平表

總和表示同一水平下的所有平均解之和，平均值表示各水平的均值。由表3可看出，當α=1，β=4，ρ=0.3，ξ=0.1，q0=0.8 時，平均路徑最短。

經(jīng)過多次實驗參數(shù)的調節(jié)與數(shù)據(jù)統(tǒng)計發(fā)現(xiàn)經(jīng)典算法ACS 設置為表4 中的數(shù)據(jù)時效果最好。作為對比實驗，ACS+3opt 與DCACS 算法選用與經(jīng)典算法ACS 相同的數(shù)據(jù)。

Table 2 Test scheme and test results表2 測試方案與測試結果

Table 3 Analysis of test results of each parameter表3 各參數(shù)測試結果分析

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

3.1.2.2 k0 的確定

k0的選取影響收斂速度，為了確保算法性能，本文設置一個對比實驗，k取不同值時比較收斂效果與解的精度。實驗選取不同規(guī)模的測試集eil51、ch150與a280 作為代表，分別進行15 次實驗，根據(jù)收斂速度與解的質量確定k0的值。

由圖4 可看出，當k0取值較小時（如k0=0.1），導致測試集在前期收斂性過強，算法很快就得到最短路徑。這是由于路徑相似度閾值k0取值較小時，啟動合作算子跟隨導向蟻中的最優(yōu)路徑，隨著信息素的積累，陷入停滯狀態(tài)，這時得到的最優(yōu)路徑屬于局部最優(yōu)路徑。當k0的取值過大（如k0=0.8），算法收斂性較差，得到的解的質量也不高。這是由于k0取值較大，合作蟻構建的路徑與導向蟻中的最優(yōu)路徑相似度較高時才能啟動合作算子，最優(yōu)路徑上的信息素導向性不強。圖5 為3 個規(guī)模的測試集在k0取不同值時得到的最短路徑。根據(jù)圖4、圖5的結果可看出，對于這三種規(guī)模的城市，當k0=0.4 時，得到的解最優(yōu)，收斂性最好。綜上，閾值k0設為0.4最為合適。

3.1.2.3 比例系數(shù)x 的確定

Fig.4 Convergence graph for different values of k0圖4 k0 取不同值時的收斂圖

Fig.5 Optimal path for different values of k0圖5 k0 取不同值時的最優(yōu)路徑

由式（7）、式（8）可知，導向蟻與合作蟻的數(shù)量是動態(tài)變化的，合作蟻的數(shù)量隨著迭代次數(shù)的增加而增加。最后一次迭代時導向蟻的數(shù)量為m-[xm]，合作蟻的數(shù)量為[xm]。其中導向蟻的職責是探索新路徑，合作蟻職能是加快收斂。為了更好地提升算法性能，本文設置一比例系數(shù)x來控制兩蟻群的數(shù)量變化，其中x≤1。若x設置過大，將會使合作蟻數(shù)量增長過快，使算法過早陷入局部最優(yōu)，最后得到局部最優(yōu)解。若x設置過小，合作蟻數(shù)量增長過慢，會使得算法收斂速度較慢。本文以測試集eil51 為例，x的設置情況如圖6 所示。從整體看，當x取值小于1 時，算法的尋優(yōu)結果優(yōu)于x=1 的情況。當x取值較大（如x=1），后期合作蟻增長過快，導向蟻發(fā)揮作用減弱，雖然收斂速度加快，但是陷入了局部最優(yōu)。而x設置較小時（如x=1/16），合作蟻的數(shù)量增長過慢，導向蟻數(shù)量一直多于合作蟻，導向蟻發(fā)揮主要作用，收斂速度過慢，算法得不到最優(yōu)解。x取時，能得到最優(yōu)解，但是在1 000 代左右才收斂，收斂效果有待提升。綜合考慮收斂速度與搜索能力兩項指標，當x=7/8 時，收斂速度最快，解的質量最高，故比例系數(shù)設為7/8 時最為合適。

Fig.6 Iteration with different proportional coefficients圖6 不同比例系數(shù)下迭代情況

3.2 改進策略分析

3.2.1 傳播因子多樣性分析

為了驗證引入傳播因子對算法多樣性的影響，選用規(guī)模kroB150 作為測試集進行分析。因為熵是對不確定性的一種度量方式，熵值越大，代表系統(tǒng)的不確定性越大，算法多樣性越好。故本文用熵分析ACS 算法和引入傳播因子后算法的多樣性，傳統(tǒng)ACS 算法與ACS+傳播因子（引入傳播因子的ACS 算法）多樣性如圖7 所示。為了更明確比較兩者的熵，設置斷點對比兩個算法的多樣性，結果如圖8。

由圖7 多樣性對比結果可以看出，引入傳播因子后的ACS 算法的熵的平均值在5.4 左右。ACS 算法熵的平均值在5.0 左右，說明引入傳播因子后的ACS算法有效提高了算法多樣性。圖8 為算法每間隔50代設置斷點計算的熵值，可以看出加入傳播因子后的ACS 算法熵值整體都高于ACS 算法。在500～1 000 代時，兩種算法差距明顯，這是由于剛開始迭代時各路徑信息素初值相同，初期受周圍信息素影響較小；隨著迭代次數(shù)的增多，各路徑信息素量差距變大，傳播因子發(fā)揮作用，螞蟻受周圍信息素的影響，降低局部最優(yōu)城市被選中的概率，增大其他邊探索的機會，從而提高算法多樣性。

3.2.2 合作算子收斂性分析

為了驗證合作算子對算法收斂速度的影響，本文選取小規(guī)模城市eil76、中規(guī)模城市kroA200、大規(guī)模城市l(wèi)in318作為代表進行分析。改進的算法DCACS與DCACS-1（缺少合作算子的DCACS 算法）收斂情況如圖9。

Fig.7 Comparison of kroB150 diversity results圖7 kroB150 多樣性結果對比

Fig.8 kroB150 entropy comparison圖8 kroB150 熵值對比

由圖9 可以看出，加入合作算子后，對于小規(guī)模城市eil76，加入合作算子后的算法在350 代左右就找到了最優(yōu)解，而DCACS-1 在500 代左右才得到最優(yōu)解，加入合作算子后比缺少合作算子的算法可以更快地找到最優(yōu)解。對于中大規(guī)模城市，收斂速度也明顯優(yōu)于DCACS-1。

3.2.3 動態(tài)調控策略性能分析

為了驗證動態(tài)調控策略中適應性調控算子U對算法的影響，選用kroA100 作為代表進行分析，比較DCACS 與DCACS-2（缺少適應性調控算子的DCACS）的收斂速度，結果如圖10。

由圖10 可以看出，DCACS（有適應性調控算子）算法在600 多代就已經(jīng)找到了最優(yōu)解，而DCACS-2（缺少適應性調控算子的DCACS）直到1 200 多代才找到最優(yōu)解。在尋找最優(yōu)路徑過程中DCACS 算法的收斂速度明顯優(yōu)于DCACS-2 算法。這是由于對全局最優(yōu)路徑進行信息素更新時引入了適應性調控算子，通過對路徑上的信息素進行正向激勵或反向懲戒，使得路徑上的信息素更具有指導性，進而加快算法收斂。

3.3 DCACS 個體分布情況分析

為了更細致地觀察異構雙蟻群在不同時期發(fā)揮的作用，以eil51為測試集進行測試，結果如圖11、圖12。

Fig.9 Comparison of convergence between DCACS and DCACS-1圖9 DCACS 與DCACS-1 收斂性對比

Fig.10 kroA100 iteration圖10 kroA100 迭代情況

Fig.11 Ants distribution at different times圖11 不同時期螞蟻數(shù)量分布圖

圖11 為不同迭代時期螞蟻數(shù)量分布，圖12 為在與圖11 相同迭代時期時DCACS 算法與ACS 算法的熵。熵值越大，解的多樣性越好。整體來看，當?shù)螖?shù)小于800 時，導向蟻數(shù)量多于合作蟻，導向蟻占主導地位。當?shù)螖?shù)高于800 時，合作蟻占主導地位。由圖11、圖12 可知，當?shù)螖?shù)小于200 時，導向蟻占比較高。DCACS 與ACS 的熵值相差不大，這是由于初始階段各路徑信息素相差不大，導向蟻中的傳播因子的作用還不明顯，處于初步探索階段。在200～400 代，DCACS 與ACS 的熵值都略有提高，且DCACS 的熵值整體高于ACS。這是由于這個階段導向蟻一直處于主導地位，隨著迭代次數(shù)的增加，各路徑信息素差距開始變大，傳播因子開始發(fā)揮作用，擴展了新路徑，豐富了算法的多樣性。在400～800 代之間，導向蟻的數(shù)量逐漸減小，在800 代左右兩蟻群數(shù)量相當。這階段DCACS 的熵值快速增長，在800代左右達到最大。說明算法在這階段仍處于探索階段，隨著信息素的積累在800 代左右信息素影響力度達到最大，傳播因子發(fā)揮作用明顯，使得算法多樣性達到最好。在800～1 200 代之間，合作蟻數(shù)量超過導向蟻，合作蟻開始占主導地位。DCACS 的熵值開始減小，說明解的多樣性開始減小，算法進入收斂階段。這階段ACS 的熵值保持穩(wěn)定，整體低于DCACS的熵，說明在算法中期雖然合作蟻發(fā)揮主要作用，但導向蟻仍會繼續(xù)探索，避免算法過早陷入停滯狀態(tài)。在算法中期的1 200～1 600 代到算法后期的1 600～2 000 代，這兩個階段合作蟻數(shù)量逐漸增加，DCACS算法熵值持續(xù)下降。說明合作蟻中合作算子的引入使得路徑信息素揮發(fā)量減少，加快了信息素累積，進一步加快了算法收斂。且在中后期DCACS 的熵值仍高于ACS，表示算法后期導向蟻在提高多樣性方面仍起到了一定的作用，增加了跳出局部最優(yōu)的可能。

3.4 與經(jīng)典算法對比分析

3.4.1 實驗結果分析

為了有效地驗證改進算法（DCACS）的收斂性及解的質量等性能，本文選取eil51、eil76、kroA100、ch150、kroB150、kroB200、tsp225、a280、lin318 等中大規(guī)模TSP 算例來進行分析，以這些城市為實驗對象，分別對ACS、ACS+3opt 及DCACS 進行15 次實驗，同時從最優(yōu)解、平均解、誤差率、收斂速度幾個方面進行比較。誤差率計算公式如下：

Lbest表示三種算法得到的最優(yōu)解，Lmin表示標準解。

由表5結果可以看出，對于eil51、kroA100、kroB150等中小型城市，改進后的算法得到最優(yōu)解時所需的迭代次數(shù)更少，平均解也優(yōu)于ACS 和ACS+3opt 這兩種經(jīng)典算法；對于kroA200、tsp225、a280、lin318 等大規(guī)模城市，DCACS 得到的最優(yōu)解、平均解及誤差都優(yōu)于ACS 和ACS+3opt，且誤差均在1%以內(nèi)。綜上，DCACS 算法的誤差率、收斂性都優(yōu)于經(jīng)典算法，且得到的解的質量也較好。本文算法融合協(xié)同機制及動態(tài)調控策略，不僅提升了尋優(yōu)能力，避免了算法過早陷入停滯狀態(tài)，還提高了收斂速度，因此DCACS 能夠有效平衡算法多樣性和收斂速度之間的矛盾。

Table 5 Simulation experiment data of ACS,ACS+3opt and DCACS表5 ACS、ACS+3opt和DCACS 仿真實驗數(shù)據(jù)

3.4.2 收斂性對比分析

在ACS、ACS+3opt、DCACS 三種算法中分別進行了15 次實驗，統(tǒng)計得到實驗數(shù)據(jù)。圖13 為選取的部分小、中、大規(guī)模測試集的最佳巡回路徑。圖14 為DCACS 與ACS、ACS+3opt收斂速度對比。

由圖14 可以得出，對于eil51、eil76 等小規(guī)模城市，雖然改進的DCACS 算法、ACS 算法 及ACS+3opt算法都可以找到最優(yōu)解，但是DCACS 在200 代至600代就得到最優(yōu)解，而經(jīng)典算法在1 000 代甚至1 400代左右才得到最優(yōu)解。對于中規(guī)模、大規(guī)模測試集，DCACS 算法找到的最優(yōu)解不僅優(yōu)于ACS 和ACS+3opt 算法，且DCACS 算法得到最優(yōu)解時的迭代次數(shù)更少。異構雙蟻群分工協(xié)作、信息共享不僅加快收斂，而且提高了解的質量。

3.5 與其他最新的改進蟻群算法對比

為了進一步驗證改進DCACS 算法性能，選用最新改進的蟻群算法IACA、D-ACS、CACS 與本文算法進行比對，結果如表6。其中面向旅行商問題的蟻群算法改進（IACA）來自于文獻[16]，改進的算法D-ACS來自文獻[17]，融合貓群算法的動態(tài)分組蟻群算法CACS數(shù)據(jù)來自文獻[18]。由表6可以看出，DCACS 算法得到的解的質量對于小規(guī)模城市、中規(guī)模城市和大規(guī)模城市都優(yōu)于D-ACS、IACA 和CACS 三種算法，對于大規(guī)模城市尤為明顯。本文改進后的DCACS算法與經(jīng)典的蟻群算法ACS、ACS+3opt 和某些最新改進的蟻群算法相比，解的質量和算法收斂性能都有了明顯的提升。

Table 6 Comparison of DCACS with other newly improved algorithms表6 DCACS 與其他最新改進算法比較

Fig.13 Optimal path diagram for part of test set圖13 部分測試集的最優(yōu)路徑圖

Fig.14 Convergence comparison among DCACS,ACS and ACS+3opt圖14 DCACS 與ACS、ACS+3opt收斂對比

4 結束語

本文針對蟻群算法在求解TSP 問題時存在的尋優(yōu)能力與收斂性較差的問題，提出了結合協(xié)同機制與動態(tài)調控策略的雙蟻群算法。將蟻群隨著迭代次數(shù)動態(tài)劃分為導向蟻和合作蟻：導向蟻在路徑構建過程引入傳播因子，增大其他路徑被探索的幾率；合作蟻則考慮構建的路徑與導向蟻中最優(yōu)路徑的相似度，當達到閾值時，跟隨導向蟻的最佳巡回路徑，啟動合作算子，加快收斂。最后引入動態(tài)調控策略，加入適應性調控算子，對全局最優(yōu)路徑進行正向激勵使得路徑信息素更具導向性，進一步加快算法收斂速度。對全局最優(yōu)路徑進行反向懲戒，均衡路徑信息素分布，防止陷入局部最優(yōu)。仿真結果表明，對于大規(guī)模城市，算法在解的質量及收斂性方面都有了很大的提高，算法多樣性也得到了明顯改善。以后將研究多蟻群算法合作模型，進一步提高尋優(yōu)性和收斂性。