結(jié)合協(xié)同機(jī)制與動(dòng)態(tài)調(diào)控策略的雙蟻群算法

孟靜雯，游曉明+，劉 升

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

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

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

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

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

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

1 前期工作

1.1 蟻群系統(tǒng)

1.1.1 路徑選擇

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

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

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

1.1.2 全局信息素更新

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

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

1.1.3 局部信息素更新

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

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

1.2 3-opt算子

3-opt[12]是局部?jī)?yōu)化的一種常用方法，通過(guò)對(duì)全局最優(yōu)解進(jìn)行優(yōu)化得到更優(yōu)解。優(yōu)化過(guò)程通常分為以下幾步：（1）選取待優(yōu)化路徑上的任意三條邊；（2）斷開(kāi)后嘗試與原先不同的連接方式；（3）計(jì)算重新連接后的長(zhǎng)度并與原路徑長(zhǎng)度對(duì)比，若重新連接后的路徑更短，則選用優(yōu)化后的連接方式。反之，保留原路徑；重復(fù)（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)生一定強(qiáng)度的氣味，散發(fā)后被其他蝴蝶感知到，蝴蝶通過(guò)感知空氣中的氣味向著氣味濃度大的方向移動(dòng)，以此來(lái)確定食物中心或者伴侶的方向。這就是蝴蝶如何與其他蝴蝶和社會(huì)知識(shí)網(wǎng)絡(luò)分享自己的個(gè)人信息。香味大小F計(jì)算公式如式（6）：

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

2 改進(jìn)的蟻群算法

2.1 種群的劃分

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

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

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

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

2.2 協(xié)同機(jī)制

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

2.2.1 傳播因子及傳播域

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

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

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

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

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

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

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

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

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

2.2.2 改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則

導(dǎo)向蟻中的螞蟻在選擇下一個(gè)城市時(shí)除了受ηij、τij這兩個(gè)參數(shù)的影響外，還要考慮傳播因子f產(chǎn)生的影響?？紤]到周?chē)畔⑺氐挠绊懸雮鞑ヒ蜃樱沟脤?dǎo)向蟻在進(jìn)行路徑選擇時(shí)增大較優(yōu)路徑周?chē)鞘斜贿x擇的概率，擴(kuò)大搜索范圍。改進(jìn)后的路徑選擇規(guī)則如式（11）：

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

2.2.3 路徑相似度

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

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

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

當(dāng)路徑相似度達(dá)到閾值時(shí)，合作蟻進(jìn)行局部信息素更新時(shí)引入合作算子σ，如式（16）、式（17）：

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

2.3 動(dòng)態(tài)調(diào)控策略

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

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

2.4 算法性能分析

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

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

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

2.5 算法流程圖

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

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

2.6 算法復(fù)雜度分析

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

2.7 算法收斂性分析

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

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

3 實(shí)驗(yàn)仿真

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

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

3.1.1 參數(shù)說(shuō)明

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

3.1.2 參數(shù)確定

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

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

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

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

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

Table 2 Test scheme and test results表2 測(cè)試方案與測(cè)試結(jié)果

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

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

3.1.2.2 k0 的確定

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

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

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

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

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

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

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

3.2 改進(jìn)策略分析

3.2.1 傳播因子多樣性分析

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

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

3.2.2 合作算子收斂性分析

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

Fig.7 Comparison of kroB150 diversity results圖7 kroB150 多樣性結(jié)果對(duì)比

Fig.8 kroB150 entropy comparison圖8 kroB150 熵值對(duì)比

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

3.2.3 動(dòng)態(tài)調(diào)控策略性能分析

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

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

3.3 DCACS 個(gè)體分布情況分析

為了更細(xì)致地觀察異構(gòu)雙蟻群在不同時(shí)期發(fā)揮的作用，以eil51為測(cè)試集進(jìn)行測(cè)試，結(jié)果如圖11、圖12。

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

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

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

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

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

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

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

Lbest表示三種算法得到的最優(yōu)解，Lmin表示標(biāo)準(zhǔn)解。

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

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

3.4.2 收斂性對(duì)比分析

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

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

3.5 與其他最新的改進(jìn)蟻群算法對(duì)比

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

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

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

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

4 結(jié)束語(yǔ)

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