協(xié)同過濾策略的異構(gòu)雙種群蟻群算法*

朱宏偉，游曉明+，劉 升

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

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

+通訊作者E-mail:305235598@qq.com

1 引言

在自然界中，螞蟻在發(fā)現(xiàn)食物后會(huì)釋放信息素用于告知其他螞蟻食物的各種信息，其他螞蟻會(huì)根據(jù)信息素的濃度等信息，選擇到達(dá)食物的最短路徑。在20世紀(jì)90年代，意大利學(xué)者Dorigo、Maniezzo等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，模擬自然界螞蟻尋食的行為，提出了螞蟻系統(tǒng)（ant system，AS）[1]，引起了專家學(xué)者的重視，并運(yùn)用于商旅問題（traveling salesman problem,TSP）。實(shí)驗(yàn)證明螞蟻系統(tǒng)取得了很好的結(jié)果。商旅問題是NP 組合優(yōu)化問題中最經(jīng)典的問題之一，旅行商需要從一個(gè)城市出發(fā)，不重復(fù)地遍歷所有的城市，再回到起點(diǎn)，形成一條閉合回路。在蟻群算法研究過程中，旅行商問題是一個(gè)很重要的檢測(cè)算法性能的基準(zhǔn)。

雖然信息素的正反饋?zhàn)饔檬顾惴ǜ哂袑?dǎo)向性，但也同時(shí)因?yàn)橐粭l路徑上信息素過大而導(dǎo)致局部最優(yōu)。1996 年，Dorigo 等人在螞蟻系統(tǒng)（AS）算法的基礎(chǔ)上提出蟻群系統(tǒng)（ant colony system，ACS）[2]算法，提出兩種信息素的更新方式，同時(shí)算法中加入局部搜索算法，減少了算法陷入局部最優(yōu)的概率。同樣，為了限制信息素過多，Stützle等人提出了最大-最小螞蟻系統(tǒng)（max-min ant system，MMAS）[3]。MMAS設(shè)置一個(gè)閾值將信息素的最大值、最小值限制在其中，同時(shí)在算法進(jìn)入停滯后，將信息素重新初始化，很好地改善了ACO（ant colony optimization）的不足。后來，專家學(xué)者在這兩者的基礎(chǔ)上不斷地改進(jìn)[4-10]，文獻(xiàn)[4]提出一種基于禁忌搜索的蟻群算法，將禁忌搜索算法的記憶能力和藐視準(zhǔn)則融合到蟻群算法中，使改進(jìn)算法具有跳出局部最優(yōu)解的能力。文獻(xiàn)[5]提出一種新的信息素更新策略，加強(qiáng)了螞蟻之間的協(xié)同作用。

實(shí)際上螞蟻是一種種群活動(dòng)生物，不同的蟻群有著不一樣的信息素調(diào)控機(jī)制，這種分工組織方式使得蟻群可以完成更加復(fù)雜的任務(wù)。因此采用多種群的蟻群算法可使多個(gè)種群進(jìn)行信息交換，加速收斂的速度[11-20]。文獻(xiàn)[11]提出將蟻群分成兩種，分別采用不同的路徑構(gòu)建方式，同時(shí)固定代數(shù)進(jìn)行最優(yōu)解和信息素的交流，提高了解的質(zhì)量。文獻(xiàn)[12]提出一種新的雙種群信息素?cái)U(kuò)散機(jī)制，減少算法陷入局部最優(yōu)的概率。以上文獻(xiàn)都是將同構(gòu)蟻群算法中的螞蟻進(jìn)行分類，進(jìn)行多種群的信息交流，而異構(gòu)多種群有更優(yōu)的路徑構(gòu)建和保持種群多樣性的能力，如文獻(xiàn)[13]。

本文提出一種基于協(xié)同過濾策略的異構(gòu)雙種群蟻群算法（dual population ant colony optimization，DPACO），采用MMAS 和ACS 這兩種優(yōu)勢(shì)互補(bǔ)的異構(gòu)蟻群算法相結(jié)合的策略，既保留MMAS的多樣性，同時(shí)也保留了ACS 收斂速度快的優(yōu)勢(shì)，共同促進(jìn)算法在大規(guī)模問題上找到最優(yōu)解。引入?yún)f(xié)同過濾策略，獎(jiǎng)勵(lì)A(yù)CS 和MMAS 中螞蟻都偏愛的路徑，以加快算法的收斂速度；當(dāng)算法停滯后，根據(jù)兩個(gè)種群多樣性的動(dòng)態(tài)反饋，自適應(yīng)控制兩個(gè)種群交流的頻率，以保證蟻群算法發(fā)現(xiàn)解的廣度。算法停滯后，進(jìn)行雙種群信息素的協(xié)同交互，均化每個(gè)種群不均勻的信息素，跳出局部最優(yōu)。最后，引入神經(jīng)網(wǎng)絡(luò)中失活的概念，在路徑構(gòu)建時(shí)提出一種城市范圍失活的思想，減少了程序的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，本文提出的異構(gòu)雙種群蟻群算法比傳統(tǒng)的單種群蟻群算法和其他多種群蟻群算法在TSP 問題上有著更好的實(shí)驗(yàn)結(jié)果，并且在大規(guī)模問題上，這種優(yōu)勢(shì)更加明顯。

2 相關(guān)工作

2.1 基本蟻群算法的TSP問題

對(duì)于不同NP難問題，使用蟻群算法建立的模型設(shè)計(jì)會(huì)有所不同。本文以NP難問題中最常用的TSP問題為例說明基本蟻群算法的模型。

設(shè)螞蟻的數(shù)量為m，城市的數(shù)量為n，dij(i,j=1,2,…)代表i城市和j城市之間的距離，τij(t)代表著t時(shí)刻i城市和j城市之間的信息素的濃度大小。在ACS 和MMAS 算法中，每條邊上的起始濃度都是相同的，記為τ0。

2.2 ACS蟻群算法

2.2.1 路徑構(gòu)建

ACS中每只螞蟻從i城市到j(luò)城市的選擇公式：

其中，ηij代表的是i、j城市之間距離的倒數(shù)，即q0是一定值，q是隨機(jī)數(shù)，S代表將要被選擇的下一個(gè)城市。s是另一種輪盤賭的選擇方式。公式表明，城市之間信息素高的城市和距離相對(duì)近的城市被選擇的概率更大，當(dāng)q＜q0時(shí)，選用式（1），當(dāng)不符合上述條件，采用輪盤賭進(jìn)行路徑構(gòu)建。公式如下：

式中，allowed為螞蟻當(dāng)前可行城市集。

2.2.2 信息素更新

ACS算法中分為全局信息素更新以及局部信息素更新部分。

全局信息素更新：當(dāng)所有的螞蟻都完成一次周游以后，算法只允許每一代的最優(yōu)螞蟻釋放信息素。全局釋放信息素主要是用于增加蟻群算法的收斂速度，使螞蟻們的選擇更具有方向性。公式為：

其中，ρ是全局信息素的蒸發(fā)率，Δτij是信息素增量，Lgb是當(dāng)前最優(yōu)路徑長(zhǎng)度。

局部信息素更新：當(dāng)所有的螞蟻都完成一次周游后，算法允許每只螞蟻都對(duì)其走過的路徑進(jìn)行信息素的更新。局部信息素主要是縮小最優(yōu)路徑上與非最優(yōu)的信息素的差距，從而增加ACS 算法的多樣性。公式為：

式中，Δτij是信息素增量，τ0為每條邊上的起始濃度，ρ是局部信息素的蒸發(fā)率。

2.3 MMAS蟻群算法

2.3.1 MMAS算法信息素范圍限制

為了避免算法收斂過快、停滯，MMAS算法將各邊的信息素限制在一定范圍[τmin,τmax]，若τij≤τmin，則τij=τmin；若τij≥τmax，則τij=τmax,其中τmax和τmin的計(jì)算公式如式（6）和式（7）所示。

其中，Tgb是全局最優(yōu)路徑。

2.3.2 MMAS算法信息素更新

當(dāng)?shù)瓿梢淮鷷r(shí)，有且僅有一只螞蟻進(jìn)行信息素更新，對(duì)當(dāng)前最優(yōu)路徑或者全局最優(yōu)路徑進(jìn)行信息素更新，使最優(yōu)解得到有效的利用，算法的探索能力也會(huì)增強(qiáng)。信息素更新規(guī)則如式（8）和式（9）：

其中，f(sbest)為當(dāng)前最優(yōu)或者全局最優(yōu)的路徑長(zhǎng)度。

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

本文采用兩種目前性能較優(yōu)的蟻群算法ACS和MMAS作為雙種群的兩種蟻群算法，ACS主要負(fù)責(zé)算法的收斂速度，MMAS主要負(fù)責(zé)蟻群算法的多樣性。

3.1 協(xié)同過濾策略

推薦算法是通過數(shù)學(xué)公式、算法等方式，推測(cè)出用戶更加偏好的東西，同時(shí)可以集中偏好相同的用戶。推薦算法又可以分成基于內(nèi)容、基于協(xié)同、基于知識(shí)、基于效應(yīng)的推薦算法。其中基于協(xié)同過濾策略的推薦算法是效果最好的。

故本文引入?yún)f(xié)同過濾策略，搜索ACS 和MMAS中最優(yōu)解螞蟻都偏愛的路徑，每隔w次迭代，對(duì)該路徑進(jìn)行信息素獎(jiǎng)勵(lì)。協(xié)同的作用使算法在路徑構(gòu)造時(shí)，最優(yōu)解螞蟻帶動(dòng)非最優(yōu)螞蟻向偏愛路徑上靠攏，使算法更具有導(dǎo)向性；過濾的作用是去除一些相對(duì)較差的路徑，加快算法的收斂速度。協(xié)同過濾策略將兩個(gè)種群從前期到后期完全聯(lián)系在一起，不再是獨(dú)立地進(jìn)行解的構(gòu)建，而是形成兩個(gè)種群相互學(xué)習(xí)、共同促進(jìn)的局面，使算法能以較少的迭代次數(shù)找到最優(yōu)解，提高算法的性能。由于兩種算法中路徑構(gòu)建的差異，在算法前期信息素濃度差距不大時(shí)，若存在偏愛路徑，說明最優(yōu)解收斂在其附近的概率很大。這里僅對(duì)ACS的路徑進(jìn)行信息素獎(jiǎng)勵(lì)。這樣做有兩點(diǎn)原因：（1）根據(jù)文獻(xiàn)[3]，MMAS 對(duì)信息素的最高值設(shè)有閾值，因此對(duì)信息素的獎(jiǎng)勵(lì)作用不敏感；（2）控制變量，僅對(duì)ACS進(jìn)行信息素的獎(jiǎng)勵(lì)，可以協(xié)調(diào)獎(jiǎng)勵(lì)所帶來的各種影響：與沒有獎(jiǎng)勵(lì)策略的MMAS算法進(jìn)行交流，既可以照顧到獎(jiǎng)勵(lì)所帶來快速收斂的特性，也可以彌補(bǔ)獎(jiǎng)勵(lì)所帶來的負(fù)面影響。兩種算法相互制約，減少算法陷入局部最優(yōu)的概率。

建立一個(gè)數(shù)學(xué)模型，通過矩陣的運(yùn)算來描述本文的協(xié)同過濾策略。在T次迭代時(shí)（T是w的整數(shù)倍），為ACS 蟻群算法在T次迭代時(shí)，所有螞蟻遍歷所有城市的位置矩陣，為MMAS蟻群算法在第T次迭代時(shí)所有螞蟻的位置矩陣，如下所示。

式中，n為城市的數(shù)量，m為螞蟻的個(gè)數(shù)。

設(shè)k和h分別為ACS和MMAS算法在第T次迭代中所找到最優(yōu)解的螞蟻，故公共偏愛路徑為：

式中，S（ACS,MMAS)表示兩個(gè)種群共有的連續(xù)相同三個(gè)元素保存下來，并設(shè)為公共偏愛路徑。

3.1.1 獎(jiǎng)勵(lì)算子

對(duì)公共偏愛路徑進(jìn)行獎(jiǎng)勵(lì)，額外的信息素獎(jiǎng)勵(lì)因子：

式中，n為城市的數(shù)量，iter為交流時(shí)的迭代次數(shù)。故對(duì)于公共偏愛路徑部分的信息素更新為：

在算法前期，一條路徑被兩個(gè)種群都選到且作為當(dāng)前最優(yōu)路徑中的一部分，即可認(rèn)為此路徑或者此路徑周圍一定存在全局最優(yōu)解的組成部分。故在算法初期，獎(jiǎng)勵(lì)的信息素較多，可以加快算法收斂速度，隨著迭代次數(shù)的增加，由式（13）可知，獎(jiǎng)勵(lì)會(huì)越來越少，從而保證算法后期的多樣性。

3.1.2 自適應(yīng)調(diào)節(jié)交流頻率

由于信息素的正反饋?zhàn)饔?，?dāng)兩個(gè)種群信息交流過于頻繁時(shí)，過多的信息素獎(jiǎng)勵(lì)會(huì)導(dǎo)致雙種群都陷入局部最優(yōu)，故需要控制異構(gòu)蟻群算法的交流的頻率。因此，這里通過兩個(gè)種群之間的動(dòng)態(tài)反饋，自適應(yīng)調(diào)整交流的次數(shù)，從而減少算法陷入局部最優(yōu)的概率。設(shè)每隔w次迭代，交換概率PDPACO決定兩個(gè)種群是否進(jìn)行信息交流。公式如下：

式中，T為迭代次數(shù)，k為最優(yōu)解螞蟻。式（15）表示公共模式的路徑在總的路徑中比例大小。當(dāng)交換概率大于等于0.5時(shí)，則表明雙種群算法的多樣性已經(jīng)降低，故將不進(jìn)行種群之間的交流，否則進(jìn)行交流。因此，整個(gè)DPACO算法的交流頻率為：

當(dāng)交流頻率過于頻繁時(shí)，獎(jiǎng)勵(lì)作用會(huì)導(dǎo)致算法很快收斂到一條路徑上，造成算法多樣性下降，可能會(huì)使算法得不到滿意解；但是信息交流間隔過低時(shí)，會(huì)減弱兩個(gè)種群之間的促進(jìn)作用，降低種群之間的學(xué)習(xí)效率。因此，按照式（16）自適應(yīng)調(diào)整交流頻率，既可以加快算法的收斂速度，保證雙種群之間的交流與學(xué)習(xí)的機(jī)制，同時(shí)使信息素較為平穩(wěn)地增長(zhǎng)，使蟻群穩(wěn)步地向最優(yōu)解方向邁進(jìn)，減少算法陷入局部最優(yōu)的概率。

3.2 信息素的交流與均化

當(dāng)兩種算法停滯后，交換ACS 和MMAS 的信息素表，從而有效地跳出局部最優(yōu)。原因如下：

（1）MMAS有限制最大和最小信息素的特點(diǎn)，故每個(gè)城市之間信息素差距不是過于明顯，由于ACS的信息素的獎(jiǎng)勵(lì)，導(dǎo)致其中幾條邊上的信息素增長(zhǎng)速度較快，當(dāng)交換了信息素表后，ACS就可以得到MMAS較為均勻的信息素，從而增加算法的種群多樣性。

（2）利用MMAS 信息素初始化的特點(diǎn)，可以將ACS 上的邊的不均勻的信息素重新初始化，有利于算法跳出局部最優(yōu)。

在蟻群算法的中后期，信息素的濃度在路徑構(gòu)建中所在的權(quán)重不斷增大，因此本文提出的信息素交換方式不斷均化和調(diào)節(jié)兩個(gè)種群之間的信息素，使算法跳出局部最優(yōu)的能力更強(qiáng)。與典型的跳出局部最優(yōu)的方式相比（如MMAS，當(dāng)算法停滯時(shí)，將所有信息素重新初始化），本文提出種群間信息素的交換既將信息素回歸到一個(gè)合理的范圍，增加了蟻群的多樣性，同時(shí)也保留了算法在前期所積累的經(jīng)驗(yàn)，增加算法的收斂速度，而MMAS 蟻群算法的信息素重新初始化，就會(huì)否定所有的先前經(jīng)驗(yàn)。故信息素的交流和均化很好地平衡了蟻群算法的多樣性和收斂性。

3.3 城市的范圍失活

失活的思想最先被提出在神經(jīng)網(wǎng)絡(luò)中。隨機(jī)失活的目的是減少神經(jīng)網(wǎng)絡(luò)由于節(jié)點(diǎn)過多而產(chǎn)生的大量計(jì)算，以及造成網(wǎng)絡(luò)的過擬合作用。過擬合與陷入局部最優(yōu)的概念相類似，故本文將失活的思想引入蟻群算法中。針對(duì)城市規(guī)模大造成的計(jì)算過多、較慢的問題，本文提出一種城市范圍失活的方法，與可訪問城市表（Allowed）相結(jié)合，使得算法每次迭代中每只螞蟻的計(jì)算城市的數(shù)目都會(huì)大量減少。如圖1，中心點(diǎn)為螞蟻正處于的城市，以這個(gè)城市的中心畫一個(gè)半徑為r的圓，會(huì)將Allowed城市表中的城市分成兩種：一種在圓的范圍中，一種在圓的范圍外。將圓范圍外的城市失活，即不再計(jì)算它們的轉(zhuǎn)移概率，這樣很大程度上減少了每次計(jì)算的城市的數(shù)目。由于本文所選TSP城市數(shù)目較多而緊密，同時(shí)給出半徑相對(duì)較大，蟻群在路徑構(gòu)建時(shí)，即使計(jì)算了半徑外的節(jié)點(diǎn)，最終也不會(huì)選擇其作為下一城市，故城市范圍失活的方法不會(huì)影響算法的構(gòu)造解的精度，卻可以極大地減少程序的運(yùn)行時(shí)間。半徑r的大小的選擇：

式中，i為螞蟻當(dāng)前所在的城市，din表示第i和第n城市之間的距離。當(dāng)使用r1半徑大小的圓與Allowed城市表相結(jié)合而沒有可選點(diǎn)時(shí)，使用r2的半徑大小。

Fig.1 Current city and other cities圖1 當(dāng)前城市與其他城市

3.4 算法流程

DPACO algorithm for TSP

3.5 時(shí)間復(fù)雜度

從上述算法流程的分析可以看出，兩個(gè)種群是并行實(shí)現(xiàn)的，因此DPACO 的時(shí)間復(fù)雜度為O((m1×(n-1)+m2×(n-1))×R)，式中m1為MMAS 算法中螞蟻的數(shù)量，m2為ACS 算法中螞蟻的數(shù)量，R為最大迭代次數(shù)。設(shè)所有螞蟻的總數(shù)為m，故DPACO的最大時(shí)間復(fù)雜度為O(m×n×R)，MMAS 的最大時(shí)間復(fù)雜度為O(m×n×R)，ACS最大時(shí)間復(fù)雜度為O(m×n×R)。由此看出，本文提出的DPACO蟻群算法沒有改變算法的最大復(fù)雜度。

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

本實(shí)驗(yàn)在Matlab R2014a 的環(huán)境下仿真運(yùn)行，為了檢測(cè)改進(jìn)算法的有效性，以及顯示本文算法在解決中大規(guī)模TSP 問題上的優(yōu)勢(shì)，選取Eil76、ch130、KroB150、KroA200、KroB200、lin318 等中大規(guī)模TSP算例來進(jìn)行算法的驗(yàn)證。與經(jīng)典單種群ACS、MMAS算法以及其他多種群蟻群算法進(jìn)行數(shù)據(jù)對(duì)比，每種算法都進(jìn)行15 次仿真實(shí)驗(yàn)，不同的測(cè)試集螞蟻的數(shù)量、啟發(fā)式的值等會(huì)有所調(diào)整。DPACO 在各個(gè)測(cè)試集中的參數(shù)設(shè)置如表1所示。

4.1 節(jié)展示了DPACO、ACS、MMAS 3 種蟻群算法的性能分析和對(duì)比，以及獎(jiǎng)勵(lì)算子對(duì)信息素分布的影響。實(shí)驗(yàn)表明DPACO 無論是收斂速度還是最優(yōu)解都優(yōu)于其他兩種算法，在前期DPACO可以快速地收斂，算法后期可以跳出局部最優(yōu)，提高解的質(zhì)量。

4.2 節(jié)展示了DPACO 算法與其他多種群蟻群算法之間的對(duì)比實(shí)驗(yàn)，算法實(shí)驗(yàn)數(shù)據(jù)皆來自于其相應(yīng)論文，實(shí)驗(yàn)表明，本文提出的改進(jìn)算法的最優(yōu)解要優(yōu)于其他3種雙種群蟻群算法。

4.3 節(jié)展示了城市范圍失活方法對(duì)仿真實(shí)驗(yàn)的時(shí)間的影響。實(shí)驗(yàn)表明城市范圍失活方法可以大量減少程序的運(yùn)行時(shí)間。同時(shí)增加了對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文所選的失活半徑具有較好的特性。

4.4 節(jié)展示了DPACO 所找到的最優(yōu)解以及與ACS、MMAS的迭代對(duì)比圖。

Table 1 Parameters setting in each test set of DPACO表1 DPACO在各個(gè)測(cè)試集中的參數(shù)設(shè)置

4.1 不同TSP問題求解與比較

為了對(duì)比MMAS、ACS 和DPACO 的算法性能，本文選取Eil76、ch130、KroB150、KroA200、KroB200、lin318等中大規(guī)模TSP算例來進(jìn)行分析，同時(shí)從最優(yōu)解、平均解、誤差率J、收斂速度等幾個(gè)方向進(jìn)行實(shí)驗(yàn)分析，如表2 所示。使用式（20）衡量每種ACO 與測(cè)試集最優(yōu)解之間的差距，即誤差率，公式如下：

式中,LACO為3 種ACO 算法所找到的最優(yōu)解,Lmin為測(cè)試集的最優(yōu)解。

從表2 結(jié)果可以看出，DPACO 在所有規(guī)模測(cè)試集中，無論是最優(yōu)解、平均解，還是誤差率等方面都優(yōu)于ACS 和MMAS。同時(shí)從最終迭代數(shù)分析，DPACO在中小規(guī)模測(cè)試集上由于兩個(gè)種群信息的交換以及其獎(jiǎng)勵(lì)策略，其收斂速度相對(duì)于其他ACO 算法速度最快；對(duì)于大規(guī)模測(cè)試集問題，由于最優(yōu)解較難尋找，所有蟻群算法皆易陷入局部最優(yōu)，本文提出的DPACO算法在沒有找到最優(yōu)解時(shí)，兩個(gè)種群就會(huì)一直進(jìn)行信息交流，算法在前期很快收斂到最優(yōu)解附近。同時(shí)，在算法陷入局部最優(yōu)后，由于控制雙種群交流頻率和信息素的交換，使得DPACO中兩個(gè)種群的信息素的值都被限制，增加了跳出局部最優(yōu)的概率，故算法總可以找到最優(yōu)解。

Table 2 Performance comparison of DPACO,MMAS,ACS in different test sets表2 DPACO、MMAS、ACS在不同測(cè)試集的性能對(duì)比

3.1 節(jié)提出僅對(duì)ACS信息素更新部分進(jìn)行獎(jiǎng)勵(lì)，下面舉例分析獎(jiǎng)勵(lì)算子對(duì)信息素濃度的影響。圖2和圖3為在KroA200測(cè)試集中，雙種群中每個(gè)種群在算法停滯前信息素濃度與城市之間的關(guān)系。X軸和Y軸代表城市，Z軸代表信息素濃度。從圖2可以看出，MMAS 蟻群算法中每個(gè)城市之間信息素濃度差距不大，僅對(duì)ACS 的偏愛路徑進(jìn)行獎(jiǎng)勵(lì)，是由于MMAS限制了信息素濃度的最大最小值，故對(duì)MMAS進(jìn)行信息素獎(jiǎng)勵(lì)效果一般。

Fig.2 MMAS pheromone圖2 MMAS信息素濃度

Fig.3 ACS pheromone with reward圖3 帶有獎(jiǎng)勵(lì)的ACS信息素濃度

圖3 為ACS 的信息素濃度，由于獎(jiǎng)勵(lì)的作用，導(dǎo)致幾個(gè)城市之間信息素濃度增加較為明顯。在蟻群算法前期，信息素的權(quán)重對(duì)路徑構(gòu)建產(chǎn)生的影響相對(duì)較小，若兩個(gè)種群卻產(chǎn)生了偏愛路徑，故該路徑有很高的概率為全局最優(yōu)解組成部分，獎(jiǎng)勵(lì)該路徑增強(qiáng)了算法在前期的收斂速度，使算法快速收斂到最優(yōu)解附近。

同時(shí)本文在3.2 節(jié)提出，當(dāng)算法停滯時(shí)，交換雙種群信息素濃度表，以達(dá)到跳出局部最優(yōu)的目的。從圖2 和圖3 可以看出，交換后，ACS 會(huì)得到MMAS的相對(duì)均勻的信息素濃度表，同時(shí)MMAS 也會(huì)將ACS的信息素濃度重置，并且均勻化。

4.2 與其他多種群蟻群算法的對(duì)比

本文改進(jìn)算法還與其他異構(gòu)多種群蟻群算法進(jìn)行比較。其中文獻(xiàn)[13]提出一種多交流策略的雙種群算法（heuristic communication heterogeneous dual population ant colony optimization，HHACO）；文獻(xiàn)[14]提出基于優(yōu)勝劣汰規(guī)則的異類多種群蟻群算法（heterogeneous multiple ant colony algorithm based on survival of fittest rules，HMACSF）；文獻(xiàn)[15]提出基于相似度的自適應(yīng)異類多種群蟻群（adaptive heterogeneous multiple ant colonies algorithm based on similarity，AHMACAS）。表3中的數(shù)據(jù)皆來自于上述文獻(xiàn)。實(shí)驗(yàn)結(jié)果顯示，在Eil51和Eil76測(cè)試集上，本文DPACO算法的精度要優(yōu)于其他3種算法；在KroA100測(cè)試集上雖然4種算法都找到了測(cè)試集最優(yōu)解，但是本文算法的收斂速度要更快。

Table 3 Comparison of DPACO with other algorithms表3 DPACO與其他多種群的對(duì)比

根據(jù)4.1節(jié)和4.2節(jié)的實(shí)驗(yàn)結(jié)果，可以得出DPACO算法優(yōu)于其他蟻群算法。與單種群相比，提升了解的質(zhì)量，增加了算法的多樣性，使算法收斂速度更快；跟多種群相比，DPACO算法提高了解的精度。

4.3 城市失活策略

4.3.1 城市范圍失活的時(shí)間對(duì)比

本文提出的城市范圍失活方法，在大規(guī)模問題上可以非常明顯地減少整個(gè)程序的運(yùn)行時(shí)間，即程序完成迭代次數(shù)所花費(fèi)的總時(shí)間。本文設(shè)置一個(gè)對(duì)比實(shí)驗(yàn)，對(duì)于DPACO 蟻群算法，使用城市范圍失活的方法，這里稱為DPACO-1；不使用失活的方法，稱為DPACO-2。表4 為DPACO-1 和DPACO-2 運(yùn)行到最大迭代次數(shù)在不同測(cè)試集的時(shí)間差。

Table 4 Time comparison表4 時(shí)間對(duì)比

由表4 可知，隨著測(cè)試集中城市數(shù)量的增加，運(yùn)行時(shí)間是增加的；在同一測(cè)試集中，由于范圍失活算法所帶來的計(jì)算城市數(shù)目的減少，DPACO-1的運(yùn)行時(shí)間要明顯少于DPACO-2。設(shè)時(shí)間比t′=tDPACO-1/tDPACO-2，通過表4中數(shù)據(jù)計(jì)算，發(fā)現(xiàn)在大多數(shù)測(cè)試集中時(shí)間比一直在[0.67,0.71]之間浮動(dòng)，且隨著城市數(shù)目增加，時(shí)間比呈現(xiàn)略微增長(zhǎng)趨勢(shì)。這些測(cè)試集中的城市分布較均勻，但是在d198 和lin318 測(cè)試集中，時(shí)間比t卻增加明顯，這與測(cè)試集規(guī)模大小、城市之間密集程度有關(guān)。這兩個(gè)測(cè)試集城市分布十分密集，范圍失活的城市數(shù)量比較有限，故造成時(shí)間比增加。圖4為不同測(cè)試集的時(shí)間比對(duì)比圖。

Fig.4 Time ratio trend for different test sets圖4 不同測(cè)試集的時(shí)間比趨勢(shì)

4.3.2 不同的失活判定標(biāo)準(zhǔn)的影響

為了驗(yàn)證不同的判定標(biāo)準(zhǔn)對(duì)時(shí)間比和最優(yōu)解的影響，本文設(shè)置了幾組不同的判定標(biāo)準(zhǔn)與本文標(biāo)準(zhǔn)r1（式（18））進(jìn)行對(duì)比。同時(shí)當(dāng)范圍內(nèi)沒有城市可以選時(shí)，都選擇r2的半徑大小（式（19））。對(duì)比實(shí)驗(yàn)半徑如下：

這些判定標(biāo)準(zhǔn)中，半徑大小為r3＜r4＜r1＜r5，不同的r在不同測(cè)試集中對(duì)時(shí)間比的影響如圖5所示。

Fig.5 Influence of different judgments on time ratio of test set圖5 不同判定標(biāo)準(zhǔn)對(duì)測(cè)試集時(shí)間比影響

由圖5可以看出，不同的判定標(biāo)準(zhǔn)在各種測(cè)試集中時(shí)間比為t3＜t4＜t1＜t5。當(dāng)半徑不斷縮小時(shí)，失活的城市會(huì)越來越多，會(huì)減少大量計(jì)算，導(dǎo)致時(shí)間比進(jìn)一步減少，即程序運(yùn)行時(shí)間變短。相反，當(dāng)半徑變大時(shí)，時(shí)間比會(huì)相應(yīng)增加。故在縮短程序運(yùn)行時(shí)間方面，以r3和r4的半徑大小會(huì)使程序運(yùn)行時(shí)間更短。但是當(dāng)以r3和r4的半徑值時(shí)，會(huì)使算法找到最優(yōu)解有所下降，這是由于當(dāng)失活半徑過小時(shí)，部分測(cè)試集中城市分布較為松散，如berlin52、d198等，會(huì)造成最優(yōu)城市的丟失。而r1和更大半徑r5把最優(yōu)城市以及其周邊城市都包在其中，故蟻群所找到最優(yōu)解幾乎沒有多大差別。表5 為部分測(cè)試集中4 種失活半徑所找到的最優(yōu)解。

Table 5 Influence of different radii on optimal solution表5 不同半徑大小對(duì)最優(yōu)解影響

4.4 DPACO最優(yōu)解與收斂速度對(duì)比

圖6～圖15 為DPACO 的最優(yōu)解，以及與ACS 和MMAS 的收斂速度對(duì)比。由圖6～圖15 可以看出，DPACO在前期保留了比ACS更快的收斂速度，使解快速收斂到最優(yōu)解附近；同時(shí)在后期算法停滯時(shí)，本文算法由于采用信息素交換和控制交流的頻率等策略，易跳出局部最優(yōu)，提高解的精度，從而實(shí)驗(yàn)結(jié)果比單種群ACS和MMAS更好。

Fig.6 Eil51 test set圖6 Eil51測(cè)試集

Fig.7 berlin52 test set圖7 berlin52測(cè)試集

Fig.8 Eil76 test set圖8 Eil76測(cè)試集

Fig.9 KroA100 test set圖9 KroA100測(cè)試集

Fig.10 ch130 test set圖10 ch130測(cè)試集

Fig.11 KroB150 test set圖11 KroB150測(cè)試集

5 結(jié)束語

本文提出了一種使用ACS 和MMAS 作為兩個(gè)種群，引入?yún)f(xié)同過濾的思想，獎(jiǎng)勵(lì)雙種群中螞蟻都偏愛的路徑，提高了解的質(zhì)量，同時(shí)自適應(yīng)調(diào)整雙種群的交流頻率，減少算法陷入局部最優(yōu)的概率。算法的后期，當(dāng)雙種群算法停滯后，雙種群信息素協(xié)同交流，應(yīng)用MMAS信息素初始化和設(shè)定的閾值等特點(diǎn)，極大增強(qiáng)了算法跳出局部最優(yōu)的能力。在路徑構(gòu)造階段每個(gè)種群都使用城市范圍失活的方法，使整個(gè)程序的運(yùn)行時(shí)間大大減少。雖然本文算法在所有規(guī)模測(cè)試集中，解的質(zhì)量提升較多，且中小規(guī)模測(cè)試集中收斂速度提升明顯，但對(duì)于大規(guī)模TSP問題上，算法后期收斂速度較慢，為此下一步繼續(xù)優(yōu)化多種群蟻群算法的獎(jiǎng)勵(lì)算子，以加快算法在大規(guī)模問題上的收斂速度。

Fig.12 KroA200 test set圖12 KroA200測(cè)試集

Fig.13 KroB200 test set圖13 KroB200測(cè)試集

Fig.14 d198 test set圖14 d198測(cè)試集

Fig.15 lin318 test set圖15 lin318測(cè)試集