陳 達(dá)，游曉明+，劉 升

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

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

旅行商問題（traveling salesman problem，TSP）是經(jīng)典的組合優(yōu)化問題，可以簡單地描述成：旅行商從規(guī)定的幾個城市中的某一起點(diǎn)出發(fā)，并通過所有給定的城市，且每個城市只經(jīng)過一次，最后回到起點(diǎn)，從而找到一條最短閉合回路的路徑問題。目前有很多可以解決TSP 問題的算法，蟻群算法因其良好的并行性和較好的魯棒性成為了解決TSP問題最好的算法之一。

20 世紀(jì)90 年代初，意大利學(xué)者Dorigo 等人[1-2]受到螞蟻覓食行為的啟發(fā)提出了螞蟻算法（ant system，AS），但算法有著收斂速度慢、容易陷入局部最優(yōu)的缺點(diǎn)。于是在此基礎(chǔ)上，Dorigo 等人在1997 年提出了全新的蟻群算法（ant colony system，ACS）[3]，相較于AS算法，該算法大大地提高了收斂速度和求解精度。同時期，由Stutzle 等人提出了最大最小螞蟻系統(tǒng)（max-min ant system，MMAS）[4]，該算法為信息素設(shè)置了上下限閾值，避免了信息素濃度無限累加以致算法停滯，提高了算法的求解效率。以上就是經(jīng)典的蟻群算法，它們都具有效率較高的求解能力，但仍就存在易于陷入局部最優(yōu)、收斂速度慢等問題。

此后眾多的專家學(xué)者針對這些問題提出了自己的改進(jìn)，文獻(xiàn)[5-7]提出了融合遺傳-蟻群算法，一種引入代價算子的蟻群算法和一種自適應(yīng)分組的蟻群算法，分別利用了遺傳算法前期收斂速度快，引入代價算子控制搜索方向和讓蟻群自適應(yīng)分組的方式，很好地提高了算法的收斂速度，但存在著多樣性較差，求解質(zhì)量不高的問題。文獻(xiàn)[8]與文獻(xiàn)[9]分別使用了一種新的信息素二次更新機(jī)制和使用K-Means 聚類算法生成城市關(guān)聯(lián)矩陣影響螞蟻選擇城市的概率的方法，從而增加了算法的多樣性，但算法收斂速度略有不足。文獻(xiàn)[10]提出了一種新的信息素更新方式，從而在加快算法收斂速度的同時擴(kuò)大了搜索范圍；文獻(xiàn)[11]使用了擁擠度與2-opt 算子，提高蟻群算法的收斂速度和全局搜索能力，從而很好地平衡了收斂速度和多樣性之間的關(guān)系，但由實(shí)驗(yàn)結(jié)果可知，對于較大規(guī)模的城市的求解精度有待提高。

針對以上問題，提出一種引入特征遷移和匹配學(xué)習(xí)的雙蟻型蟻群算法（dual ant colony algorithm based on backtracking migration and matching learning，BMACS），通過改進(jìn)的動態(tài)分級策略，根據(jù)個體適應(yīng)度的評價，將螞蟻分為探索蟻和追蹤蟻，探索蟻適應(yīng)度好，通過較大權(quán)重的動態(tài)信息素更新增強(qiáng)自己的影響力，起到導(dǎo)向作用；追蹤蟻跟隨探索蟻，每只探索蟻通過分配規(guī)則分到若干追蹤蟻，隨后追蹤蟻在探索蟻附近搜索次優(yōu)路徑，擴(kuò)大搜索范圍。其次，提出一種局部遷移機(jī)制，通過局部特征遷移策略將探索蟻得到的解選出公共路徑，并作為局部特征通過局部信息素獎勵遷移到信息素矩陣中，進(jìn)一步加快收斂速度；通過變異學(xué)習(xí)策略，針對探索蟻的路徑使用分配的追蹤蟻進(jìn)行變異學(xué)習(xí)操作，搜索探索蟻附近路徑的探索，從而增加多樣性，產(chǎn)生的新個體與原個體進(jìn)行比較擇優(yōu)保留。最后匹配學(xué)習(xí)機(jī)制通過余弦相似度選出歷史最優(yōu)解，并與當(dāng)前最優(yōu)解進(jìn)行匹配，保留之間公共路徑的信息素，并對非公共路徑的信息素進(jìn)行平滑操作，幫助算法跳出局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，本文算法在解決TSP問題時相比原算法有一定的提高，較好平衡了算法收斂速度與多樣性之間的矛盾，并對較大規(guī)模的TSP問題求解也具有一定的提高。

1 蟻群算法求解TSP問題步驟

1.1 路徑構(gòu)建

在ACS算法中，螞蟻k當(dāng)前位置在i處，遵循偽隨機(jī)規(guī)則選擇自己將要訪問的城市j，其規(guī)則如式（1）：

其中，q是均勻分布在區(qū)間[0,1]上的隨機(jī)變量；q0是一個參數(shù)，其范圍是[0,1]；J是根據(jù)式（2）給出的一個變量。

其中，α為信息啟發(fā)式因子；β為期望啟發(fā)式因子；為螞蟻下一步可以直接到達(dá)并且尚未訪問過的城市的集合；ηij為啟發(fā)函數(shù)，其表達(dá)式為式（3）；τij是城市i到城市j所在邊信息素的大小。

1.2 信息素更新

局部信息素更新規(guī)則：螞蟻k從當(dāng)前城市i到下一城市j后，立即進(jìn)行更新信息素，如式（4）所示：

其中，ρ是局部信息素蒸發(fā)系數(shù)，其范圍是[0,1]；τ0是信息素初始值，這里根據(jù)實(shí)驗(yàn)結(jié)果選取τ0的值為1/nC時，算法性能較好；n是城市節(jié)點(diǎn)數(shù)，C是一個常數(shù)。

全局信息素更新規(guī)則：當(dāng)所有螞蟻都走完之后，選擇本次迭代中的當(dāng)前最短路徑進(jìn)行全局信息素更新，如式（5）所示：

其中，ξ為全局信息素蒸發(fā)系數(shù)，Lbs為全局最優(yōu)的路徑長度；為全局最優(yōu)的路徑改變的信息素，按照式（6）計算。

2 算法改進(jìn)（BMACS）

2.1 改進(jìn)的動態(tài)分級策略

傳統(tǒng)蟻群算法螞蟻的探索行為單一，且個體之間的協(xié)作溝通不足，為了解決這一問題，本節(jié)提出一種改進(jìn)的動態(tài)分級策略，通過式（7）評價每只螞蟻個體適應(yīng)度的好壞，并將螞蟻分成探索螞蟻和追蹤螞蟻，隨后將若干追蹤螞蟻通過2.1.3 小節(jié)的分配規(guī)則分給探索螞蟻，隨后探索螞蟻執(zhí)行局部特征遷移策略交流各自的優(yōu)秀解或片段，增強(qiáng)其導(dǎo)向作用，追蹤螞蟻通過變異學(xué)習(xí)策略跟隨探索螞蟻所走的路徑附近，追蹤次優(yōu)級的路徑，并通過局部信息素的自適應(yīng)更新反饋給探索螞蟻，提高探索螞蟻的局部搜索能力，若追蹤螞蟻在局部搜索的過程中找到更優(yōu)的解則替換掉該路徑，提高算法效率，兩種螞蟻的關(guān)系如圖1所示。

圖1 探索螞蟻與追蹤螞蟻交流Fig.1 Communication between exploration and tracking ants

2.1.1 適應(yīng)度評價算子

在TSP問題中，螞蟻在跑完路徑之后得到的長度相差較大，并不適合直接評判解的優(yōu)劣，故本小節(jié)提出一種適應(yīng)度評價方法，如式（7）所示：

其中，Lj是第j個個體的解，λj是個體j的適應(yīng)度，N是種群數(shù)目。由上述公式可知，適應(yīng)度越小，螞蟻個體得到的路徑長度越小，從而適應(yīng)度越好。

2.1.2 動態(tài)分級算子

動態(tài)分級規(guī)則如式（8）、式（9），由公式可知兩種螞蟻的數(shù)量并不是固定不變的，探索螞蟻和追蹤螞蟻可以按照算法的當(dāng)前狀態(tài)互相轉(zhuǎn)變。在算法的前期，探索螞蟻數(shù)量較多，這樣可以增強(qiáng)算法的導(dǎo)向能力，加快算法的收斂；在算法的中后期，追蹤螞蟻的數(shù)量變多，將會加大對次優(yōu)級路徑的探索，增加算法多樣性，使得算法不容易陷入局部最優(yōu)。

其中，λi是個體適應(yīng)度的大小，由式（7）計算得出，式（9）將根據(jù)個體λi的大小將螞蟻種群分為兩類，在0 ＜λi≤m中的為探索螞蟻，在m＜λi＜1 中的為追蹤螞蟻。由式（9）可以看出，兩種群體的數(shù)量會根據(jù)個體適應(yīng)度的大小動態(tài)變化；m是兩種螞蟻的動態(tài)閾值界點(diǎn)，由式（8）計算得出，其中λmin是當(dāng)前迭代最小的適應(yīng)度，λmax是當(dāng)前迭代最大的適應(yīng)度，是當(dāng)前迭代所有適應(yīng)度的平均值，在算法前期，個體之間適應(yīng)度的差異較大，因此m的值也較大，更多的螞蟻被選為探索螞蟻；在算法的中后期，隨著個體之間的適應(yīng)度差異減小，m也相應(yīng)變小，更多螞蟻被選為追蹤螞蟻。C是常數(shù)，由實(shí)驗(yàn)給出，以eil51 為例，每組30次實(shí)驗(yàn)，由表1可知當(dāng)C取3時算法的平均誤差最小。

表1 C 的取值對精度的影響統(tǒng)計Table 1 Statistics on influence of value of C on accuracy

2.1.3 追蹤螞蟻的分配規(guī)則

本小節(jié)將對2.1.2小節(jié)分級后的追蹤螞蟻進(jìn)行分配，每只探索螞蟻分到數(shù)量不等的追蹤螞蟻幫助其局部搜索。在算法前期，每只螞蟻得到的解的質(zhì)量不等，未進(jìn)行充分的發(fā)展，所有解都可以認(rèn)為有相同的潛力，因此在前期將追蹤螞蟻均勻地分配給每只探索螞蟻；在算法的中后期，經(jīng)過充分發(fā)展后，每只探索螞蟻的潛力將通過其各自的適應(yīng)度體現(xiàn)，在這一階段將按照探索螞蟻的適應(yīng)度成比例地分配追蹤螞蟻，適應(yīng)度好的探索螞蟻會分到更多的追蹤螞蟻從而獲得更大的搜索能力，充分發(fā)揮其潛力。如圖2所示，式（10）是每只探索螞蟻按比例得到追蹤螞蟻的公式。

圖2 追蹤蟻的分配Fig.2 Distribution process of tracking ants

2.2 局部特征遷移學(xué)習(xí)機(jī)制

2.2.1 局部特征遷移策略

螞蟻在遍歷完所有城市后會得到一個解，解是由一組城市編號組成的序列，而適應(yīng)度較好的個體一般具有一些共同的序列片段，這些序列片段可以看作每個個體之間共同的局部特征，本小節(jié)利用局部特征遷移策略提取出適應(yīng)度較好的螞蟻個體解中一些共有的局部特征，并將這些特征遷移通過局部信息素更新將這些特征映射到信息素矩陣中，隨著算法的不斷迭代，被采集特征的樣本變多，被提取局部特征更加可靠，從而使得信息素空間更加具有導(dǎo)向作用，進(jìn)一步提高算法的正向反饋能力。

（1）遷移樣本選擇

為了讓優(yōu)秀的個體提高其影響力，本小節(jié)將選取每次迭代中適應(yīng)度較好的解作為特征提取樣本，而探索蟻具有較好的適應(yīng)度，因此本文選擇探索蟻?zhàn)鳛檫w移樣本。所選取的特征遷移到每只探索蟻各自被分配到的追蹤蟻的解中進(jìn)行解的重組從而得到新解。

（2）特征提取

如圖3所示，每只螞蟻個體的解是由城市序列組成的數(shù)組，每次選取的特征是螞蟻?zhàn)哌^城市編號的排列，在當(dāng)前迭代下，選取的局部特征是當(dāng)前探索蟻個體所有解的交集，如式（11）所示。

圖3 公共路徑選取Fig.3 Common feature selection

其中，v(t)是當(dāng)前探索蟻個體所有解的交集；A1到是當(dāng)前探索蟻的路徑，是由城市編號組成的一組序列，當(dāng)前螞蟻?zhàn)哌^相同的路徑超過三個節(jié)點(diǎn)即可被稱為公共路徑。

（3）局部特征遷移

如圖4 所示，將探索蟻的公共路徑選擇之后，算法通過局部信息素的更新對這些公共路徑進(jìn)行獎勵，從而完成對局部特征的遷移，之后通過信息素矩陣的影響，加快算法的收斂速度。式（12）是針對公共路徑信息素的濃度。

圖4 特征遷移Fig.4 Feature migration process

其中，是公共路徑邊的信息素；n是城市的節(jié)點(diǎn)數(shù)；Lmin是當(dāng)前最優(yōu)路徑的長度。

2.2.2 變異學(xué)習(xí)策略

算法完成特征遷移后提高了收斂速度，但也增大了陷入局部最優(yōu)的可能性，為了平衡特征遷移機(jī)制，本小節(jié)提出一種變異學(xué)習(xí)機(jī)制，幫助追蹤蟻在探索蟻路徑的次優(yōu)路徑進(jìn)行局部搜索。如圖5所示，在追蹤蟻完成分配后，追蹤蟻平均分布在探索蟻的路徑上，隨后針對每一段路徑進(jìn)行變異學(xué)習(xí)，完成對探索蟻次優(yōu)路徑的探索，從而提高算法的多樣性。若新個體比原有個體適應(yīng)度好，則代替舊個體進(jìn)行局部信息素更新。

圖5 變異學(xué)習(xí)Fig.5 Mutation learning process

變異學(xué)習(xí)規(guī)則對于符合要求的解在某個維度d(1 ≤d≤n)上面生成一個介于0 到1 之間的隨機(jī)數(shù)，該隨機(jī)數(shù)即為此解X的子序列X[d,d+l]突變的概率，其中d為1到n之間的一個隨機(jī)數(shù)，l是由TSP城市的規(guī)模決定的，且l在[0,n-d]之間，對于選好之后X的子序列，將其序列進(jìn)行翻轉(zhuǎn)學(xué)習(xí)。在變異學(xué)習(xí)完成后，產(chǎn)生的新個體計算適應(yīng)度并與原有個體比較，保留適應(yīng)度較好的個體，提高算法效率。

2.2.3 信息素更新規(guī)則

（1）局部信息素更新

BMACS算法局部信息素更新如式（13）～（15）所示：

式（13）中λi是當(dāng)前螞蟻的適應(yīng)度，λmax是當(dāng)前迭代適應(yīng)度的最大值；式（14）中Lgb是當(dāng)前迭代最優(yōu)路徑的長度；式（15）中τa-l是被選中的片段更新的信息素，且只在該片段進(jìn)行更新，La-l是當(dāng)前螞蟻找到的路徑長度；ρ是局部信息素蒸發(fā)系數(shù)。

（2）全局信息素更新

BMACS 全局信息素更新如式（5）、式（6）所示，在完成最優(yōu)解的更新之后，將對自適應(yīng)回溯策略的公共區(qū)域獎勵信息素，獎勵的大小如式（6）所示將按照當(dāng)前迭代的最優(yōu)解進(jìn)行獎勵。

2.3 匹配學(xué)習(xí)機(jī)制

傳統(tǒng)的蟻群算法容易陷入局部最優(yōu)，一般而言，當(dāng)蟻群算法的信息素矩陣在某一條路徑上的路徑的信息素濃度過高時會減少對其他路徑的探索，從而陷入局部最優(yōu)；根據(jù)這一特點(diǎn)，當(dāng)算法陷入局部最優(yōu)時，通過對信息素矩陣重組，改變信息素的分布就能增加算法跳出局部最優(yōu)的可能性。重組信息素的方法有很多，其中最簡單的是初始化信息素，但這種方法的缺點(diǎn)是不能記錄螞蟻尋解的經(jīng)驗(yàn)，降低了算法的搜索效率；本節(jié)中，為了盡量保留螞蟻的經(jīng)驗(yàn)，提出一種匹配學(xué)習(xí)機(jī)制，在該機(jī)制中，算法將會記錄每次迭代的最優(yōu)解，并通過相似度評價選擇歷史最優(yōu)解，并與當(dāng)前最優(yōu)解進(jìn)行匹配學(xué)習(xí)，保留公共路徑信息素的同時，平滑非公共路徑的信息素，最大程度上保留螞蟻的優(yōu)秀經(jīng)驗(yàn)。

2.3.1 余弦相似度

余弦相似度是通過向量的余弦值判斷個體之間差異的度量，本文中，用余弦相似度來度量當(dāng)前最優(yōu)解與歷史最優(yōu)解之間的相似度，從而選擇一個相似度最高的歷史最優(yōu)解進(jìn)行匹配學(xué)習(xí)。本文選擇信息熵和公共路徑節(jié)點(diǎn)與總結(jié)點(diǎn)的比值作為當(dāng)前最優(yōu)解的兩個特征組成解的向量，如式（16）所示：

其中，T是余弦相似度；x和y分別是歷史最優(yōu)解和當(dāng)代最優(yōu)解的二維向量，此二維向量(E,V)由信息熵E和公共路徑節(jié)點(diǎn)與總結(jié)點(diǎn)的比值V組成，分別由式（17）、式（18）得到。

其中，E(x)是種群的信息熵；L(x)是螞蟻x解的倒數(shù)；V是公共路徑與城市節(jié)點(diǎn)的比值；n是城市節(jié)點(diǎn)數(shù)；v是公共路徑，由式（11）得到。

2.3.2 信息素重組

通過余弦相似度匹配到學(xué)習(xí)的歷史最優(yōu)解后，保留當(dāng)前最優(yōu)解與歷史最優(yōu)解之間的信息素，而后對非公共路徑節(jié)點(diǎn)的信息素進(jìn)行信息素的平滑操作，平滑的大小如式（19）所示：

其中，Ph是非公共路徑的信息素；Phmin是信息素中的最小值；Phmax是信息素中的最大值；通過信息素中最大值和最小值的平均值對非公共路徑的信息素進(jìn)行平滑。

2.4 BMACS算法偽代碼展示

算法1解決TSP問題的BMACS算法

2.5 BMACS算法與其他算法復(fù)雜度對比分析

表2展示了不同智能算法的復(fù)雜度[12]，本文算法BMACS分別與離散蝙蝠算法（discrete bat algorithm，DBA）、自適應(yīng)模擬退火蟻群算法（adaptive simulated annealing ant colony algorithm，SA-MMAS）、煙花算法（fireworks algorithm，F(xiàn)WA）、混沌煙花算法(chaotic fireworks algorithm，CFWA）和ACS 算法進(jìn)行對比分析，結(jié)果表明，BMACS 算法的復(fù)雜度與其他智能算法的復(fù)雜度相同，并未增加算法的時間復(fù)雜度。

表2 不同算法復(fù)雜度對比Table 2 Comparison of complexity of different algorithms

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

為了驗(yàn)證BMACS的算法性能，本文選取TSPLIP中14 個TSP 實(shí)例樣本對算法進(jìn)行測試，每個實(shí)例進(jìn)行30 次實(shí)驗(yàn)，迭代2 000 次。本文實(shí)驗(yàn)測試環(huán)境為Windows 10 操作系統(tǒng)，利用MATLAB2019a 進(jìn)行仿真，并與傳統(tǒng)算法與其他的智能算法進(jìn)行對比。

3.1 算法參數(shù)的確定

本節(jié)針對BMACS 算法的5 個參數(shù)使用正交實(shí)驗(yàn)確定最佳的參數(shù)組合，如表3所示。使用城市實(shí)例eil76，建立五因素四水平的正交實(shí)驗(yàn)，如表4 所示。每組的參數(shù)分別做20次實(shí)驗(yàn)并做平均，如表5所示。BMACS 的最佳參數(shù)組合是：α=2，β=4，ρ=0.2，ξ=0.2，q0=0.9。

表3 BMACS的實(shí)驗(yàn)因素和水平Table 3 Experimental factors and levels of BMACS

表4 正交實(shí)驗(yàn)方案及BMACS實(shí)驗(yàn)結(jié)果Table 4 Orthogonal test scheme and test results of BMACS

表5 BMACS測試結(jié)果分析Table 5 Analysis of test results of BMACS

3.2 BMACS算法的對比分析

本節(jié)使用14 個TSP 實(shí)例，將BMACS 算法與ACS 算法和ACS-3opt 算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果如表6所示。誤差率的計算公式如式（20）所示：

由表6可知，BMACS算法在14個實(shí)例中在平均解、最優(yōu)解、誤差率等各項(xiàng)指標(biāo)的對比中均優(yōu)于ACS-3opt、ACS 算法；在eil51、eil76 和rat99 這些小規(guī)模的城市中3 個算法均能夠找到最優(yōu)解，但BMACS 算法找到最優(yōu)解的收斂迭代次數(shù)要小于ACS-3opt、ACS算法，這表明BMACS 算法有更快的收斂速度；在kroA100、kroB100、ch130、kroA150、kroB150、kroA200、kroB200、tsp225 這些中等規(guī)模的城市中，BMACS 算法在kroA100、kroB100中找到了最優(yōu)解，在其他的實(shí)例中誤差也均小于0.5%，這表明算法在中規(guī)模的城市中與另外兩個經(jīng)典的算法相比較求解精度也較高；在大規(guī)模的城市中，求解a280 的誤差率在0.31%，在lin318、fl417 這兩個實(shí)例的求解誤差率也均在1%左右，這表明在大規(guī)模的城市中，BMACS算法也有著較高的求解精度。

由表6 的對比可知，經(jīng)過特征遷移機(jī)制的影響，BMACS 算法很好地平衡了收斂速度和多樣性之間的關(guān)系，使得算法在中小規(guī)模實(shí)例中的求解性能均優(yōu)于ACS-3opt、ACS算法，在大規(guī)模的城市實(shí)例中雖然沒有找到最優(yōu)解，但求解的誤差也較小，這說明BMACS 算法的局部特征遷移學(xué)習(xí)策略也發(fā)揮著較好的效果。圖6 所示的是BMACS 算法找到最優(yōu)解城市的路徑。

表6 ACS、ACS+3opt、BMACS在不同測試集的性能對比Table 6 Performance comparison of ACS、ACS+3opt、BMACS in different test sets

圖6 最優(yōu)路徑圖Fig.6 Optimum path maps

3.2.1 BMACS算法多樣性和收斂性分析

為了更好地驗(yàn)證BMACS算法性能，本小節(jié)將算法與ACS 和ACS-3opt 在收斂性和多樣性兩方面進(jìn)行對比。本小節(jié)選取實(shí)例rat99、kroB150、kroA200做出各自的多樣性圖和收斂圖，結(jié)果如圖7～圖9所示。

圖7～圖9中的（a）、（b）是BMACS和ACS-3opt的多樣性圖，隨著城市數(shù)量的增多，兩種算法的標(biāo)準(zhǔn)差波動差距隨之變大，這說明算法的多樣性也更為豐富，這是通過動態(tài)分級策略中的追蹤蟻與變異學(xué)習(xí)機(jī)制的影響使得種群的多樣性得到改善。由各圖的（c）可以知道三種算法在收斂性上的表現(xiàn)，由收斂圖可以很明顯看到，BMACS在各種中大規(guī)模的城市中均能夠快速收斂并且求解精度也高于ACS-3opt、ACS 算法。這是由于在算法的前期，通過局部特征遷移策略將優(yōu)秀個體的解與其他個體充分交流，讓其他個體吸收較好的片段，使得其快速收斂；在算法運(yùn)行的中后期，算法極易陷入局部最優(yōu)，匹配學(xué)習(xí)機(jī)制使得當(dāng)前最優(yōu)解通過相似度匹配歷史最合適的最優(yōu)解，保留公共路徑的信息素，平滑非公共路徑的信息素，增加了算法后期的多樣性，使得算法在后期更容易跳出局部最優(yōu)。

圖7 rat99測試集的對比Fig.7 Comparison of rat99 test set

圖8 kroA150測試集的對比Fig.8 Comparison of kroA150 test set

圖9 kroA200測試集的對比Fig.9 Comparison of kroA200 test set

3.2.2 BMACS算法與其他算法的對比分析

本小節(jié)將BMACS算法分別與隨機(jī)插入煙花算法（random insertion of fireworks algorithm，RBIFWA）[12]、自適應(yīng)升溫模擬退火算法（adaptive temperature rise simulated annealing algorithm，SGSAA）[13]、基于SAC模型改進(jìn)的遺傳算法（improved genetic algorithm for solving TSP problem based on SAC model，GA-SAC）[14]、基于信息素初始分配和動態(tài)更新的蟻群算法（ant colony algorithm based on initial pheromone assignment and dynamic update，IADUACO）[15]、蟻群算法與3-OPT相結(jié)合的算法（ant colony algorithm combined with 3-OPT，PACO-3OPT）[16]、基于信息熵的動態(tài)異構(gòu)蟻群算法（dynamic heterogeneous ant colony algorithm based on information entropy，EDHACO）[17]、基于皮爾遜相關(guān)系數(shù)的多種群蟻群算法（multiple swarm ant colony algorithm based on Pearson correlation coefficient，PCCACO）[18]、蜘蛛猴優(yōu)化算法（spider monkey optimization algorithm，DSMO）[19]與水波優(yōu)化算法（water wave optimization algorithm，WWO）[20]進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明相比其他算法，BMACS算法的精度更高，實(shí)驗(yàn)結(jié)果如表7所示。

表7 BMACS算法與其他算法的對比Table 7 Comparison between BMACS algorithm and other algorithms

3.3 算法機(jī)制的有效性分析

3.3.1 BMACS個體分布及其影響

為了研究兩種個體在不同時期的影響力，本小節(jié)使用城市例子rat99列出了兩種個體在不同時期的分布圖表。圖10中的兩段折線圖分別是探索蟻與追蹤蟻在不同迭代次數(shù)下的分布。

圖10 個體分布圖Fig.10 Individual distribution map

由圖10 可知，由于動態(tài)分級策略，探索蟻、追蹤蟻的數(shù)量隨著迭代次數(shù)的變化而動態(tài)改變，探索蟻及其影響力隨著迭代次數(shù)的增大而減小，追蹤蟻及其影響力隨著迭代次數(shù)的增大而增大。

在算法前期，圖中200代左右，探索蟻數(shù)量多，對其他個體產(chǎn)生的影響大，通過信息素更新產(chǎn)生了導(dǎo)向作用，使得算法能夠在前期很快收斂到某個較好的路徑。同時，追蹤蟻發(fā)揮作用，搜索探索蟻周圍的次優(yōu)級路徑。平衡精英個體，增加前期的多樣性，避免算法陷入局部最優(yōu)。

在算法中期，圖中1 000代、1 400代左右，追蹤蟻數(shù)量增多，加大了對探索蟻周圍的搜索，增加了算法的多樣性。

在算法后期，圖中的1 800代、2 000代，追蹤蟻產(chǎn)生的影響最大，此時信息素已經(jīng)積累到了精度較高的路徑。通過追蹤蟻的搜索，并通過局部信息素更新，算法增加其他路徑片段區(qū)域內(nèi)的信息素濃度，避免算法陷入局部最優(yōu)。

3.3.2 特征遷移策略的有效性分析

局部特征遷移策略作用于對螞蟻種群中的比較優(yōu)秀的個體，本文選取探索蟻?zhàn)鳛榫植刻卣鬟w移的作用對象，加快算法的收斂速度。為了驗(yàn)證其有效性，選取kroA100 做了三組實(shí)驗(yàn)，驗(yàn)證其在單獨(dú)作用時迭代速度比經(jīng)典的ACS算法快。由表8所知，在局部遷移機(jī)制單獨(dú)作用下的算法與原算法相比精度與迭代速度均有所提高。隨著迭代次數(shù)的增加，算法的精度越高，對于最優(yōu)解的路徑依賴就越強(qiáng)，個體之間的差異性越小，因此局部特征遷移策略增強(qiáng)了傳統(tǒng)蟻群算法的正向反饋。

表8 性能對比Table 8 Performance comparison

3.3.3 變異學(xué)習(xí)策略的有效性分析

變異學(xué)習(xí)策略的作用對象是追蹤蟻，變異對象由隨機(jī)數(shù)與各自的適應(yīng)度對比大小選出，被篩選出的螞蟻會進(jìn)行多維度的變異操作形成一個全新的個體，增加算法的多樣性。選取eil51 對不同迭代次數(shù)下單獨(dú)作用的變異學(xué)習(xí)與原算法對比多樣性，結(jié)果如圖11所示。

圖11 eil51實(shí)例上變異學(xué)習(xí)與原算法對比Fig.11 Comparison between variant learning and original algorithm on eil51

3.3.4 匹配學(xué)習(xí)機(jī)制的有效性分析

匹配學(xué)習(xí)機(jī)制可以使得算法在陷入局部最優(yōu)時增加算法多樣性，保持最優(yōu)個體的優(yōu)勢，從而幫助其提高跳出局部最優(yōu)的可能性，因此在解決較大規(guī)模的TSP問題時自適應(yīng)回溯機(jī)制可以幫助ACS算法提高尋解精度。本小節(jié)用lin318、fl417這兩個大規(guī)模的實(shí)例各自做30 次實(shí)驗(yàn)，對加了自適應(yīng)回溯機(jī)制的ACS 算法與經(jīng)典ACS 算法進(jìn)行對比，驗(yàn)證其有效性。由表9所知，匹配學(xué)習(xí)機(jī)制幫助ACS算法找到了更好的解，從而驗(yàn)證了機(jī)制可以增加算法跳出局部最優(yōu)的可能性。

表9 匹配學(xué)習(xí)機(jī)制的對比分析Table 9 Contrastive analysis of matching learning mechanism

4 結(jié)束語

針對傳統(tǒng)蟻群算法收斂速度慢、易于陷入局部最優(yōu)等缺點(diǎn)，本文提出了一種引入特征遷移與匹配學(xué)習(xí)的雙蟻型蟻群算法。首先，通過動態(tài)分級將螞蟻分為探索蟻和追蹤蟻，提高了螞蟻之間的協(xié)作能力；其次，通過特征遷移策略提高了算法的收斂速度，通過變異學(xué)習(xí)策略提高算法的多樣性；最后，提出匹配學(xué)習(xí)機(jī)制幫助算法跳出局部最優(yōu)。

實(shí)驗(yàn)仿真結(jié)果表明，相較于經(jīng)典的蟻群算法，本文算法加快了收斂速度，提高了多樣性。在解決中小規(guī)模的TSP問題時，本文算法能夠很快地找到最優(yōu)解；在解決大規(guī)模TSP問題中，本文算法雖然沒有快速收斂到最優(yōu)解，但依舊能保證解的多樣性，在求解精度上，誤差也較低。下一步的研究方向是利用聚類思想來解決大規(guī)模的TSP問題。