考慮動態導向與鄰域交互的雙蟻型算法*

潘 晗，游曉明，劉 升

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

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

1 引言

旅行商問題（traveling salesman problem，TSP）是一個經典的組合優化問題，也是圖論中最著名的問題之一。該問題可以這樣描述：假如一個旅行商必須經過N個城市，無論選擇什么樣的路徑，都不能重復經過每一個城市，最終還需要回到開始出發的城市。路徑選擇的要求是使得旅行商經過N個城市的路徑之和最小。由于TSP 問題又是一個NP 完全問題，解決方法主要有遺傳算法、模擬退火法、蟻群算法、禁忌搜索算法、貪婪算法和神經網絡等。

螞蟻在行動的過程中會釋放一種特殊的信息素，由于信息素的累加，可以改變螞蟻的行動方向。根據這種信息傳遞機制，螞蟻能夠更快地往返于食物源和巢穴之間，從而更有效地運送食物。20 世紀90 年代，意大利學者Dorigo 等人通過觀察蟻群覓食的過程和不斷的研究，首先提出來一種新的群智能算法——蟻群算法，此方法被成功地應用到了求解旅行商問題和二次分配問題中。最初的蟻群算法是螞蟻系統（ant system，AS）[1]，螞蟻系統有三種基本模型，分別是蟻周模型（ant cycle）、蟻密模型（ant density）、蟻量模型（ant quantity）。但是由于螞蟻系統工作過程中間的停滯問題，易于陷入局部最優的解和較長搜索時間的問題。1997 年，Dorigo 等人在螞蟻系統的基礎之上又提出了蟻群系統（ant colony system，ACS）[2],它引入了全局更新的概念，創建路徑的過程中所使用的狀態轉移規則也優于螞蟻系統，使得ACS在解決規模較大的TSP 問題時會得到更優解。1997年，Stützle 等人在對螞蟻系統的實驗分析以及應用研究中，提出了最大-最小螞蟻系統（max-min ant system，MMAS）[3]。MMAS 在每次迭代中只允許表現最好的螞蟻更新路徑上的信息素，并且限定信息素濃度允許值的上下限，其目的是為了防止算法過早停滯，增加算法的多樣性。此后，不斷地有專家學者在上述算法的基礎上進行改進，并成功應用到各種領域[4-11]。

文獻[12]將擁擠因子運用到蟻群算法的狀態轉移和信息素更新過程中。文獻[13]使用了一種改進信息素二次更新與局部優化策略，實驗結果證明這些算法增強了全局搜索能力，多樣性更好，但是收斂速度卻有待提高。針對這一不足，文獻[14]提出了一種基于最小生成樹的改進蟻群算法，將最小生成樹的信息加入到路徑尋優中來引導螞蟻的搜索過程，從而加快收斂速度。文獻[15]提出將最小生成樹的信息加入到啟發式信息中來引導螞蟻的搜索過程。文獻[16]是根據最小生成樹上的邊修改信息素初始值來發揮生成樹在路徑尋優中的作用。但是上述算法雖然加快了收斂速度，但容易陷入局部最優使其解的精度不夠高。針對這一不足，文獻[17]將螞蟻分成若干子群，并引入了吸引因子和排斥因子，實現了一種多蟻群并行選擇策略，以加強其全局搜索能力和加快收斂速度。文獻[18]運用了正、負反饋機制，利用吸引信息素和排斥信息素來增強螞蟻之間的交流，加快了算法發現最優解的速度與能力。文獻[19]引入了隨機進化因子和進化漂變閾值，不僅加快了收斂速度也增強了跳出局部最優的概率，但是上述算法在平衡種群多樣性和算法的收斂速度上有待進一步提高。

為了達到種群多樣性和算法收斂性的平衡，本文在ACS 的基礎上提出了考慮動態導向與鄰域交互的雙蟻型算法。首先在算法中結合動態導向策略，在迭代前期增加屬于最大生成樹路徑上的動態信息素，以防止概率轉移公式中城市之間的距離啟發信息占主導地位，使得算法在前期的多樣性有很大的提高；因為最小生成樹與最優路徑之間有著很大的關聯，兩者之間共同的邊高達70%～80%[20]，所以在迭代后期增加屬于最小生成樹路徑上的動態信息素，從而達到加快收斂速度的目的，并提高解的質量。同時加入MMAS 中的信息素限定規則，以避免算法陷入停滯狀態。最后結合鄰域交互策略，將螞蟻分成兩類，第二類螞蟻在狀態轉移和局部信息素更新過程中引入吸引因子，觸發了正反饋機制，進一步提高算法的收斂性。仿真結果表明，本文算法既增加了種群的多樣性，又加速了算法的收斂速度。

2 相關工作

2.1 ACS 蟻群算法原理

2.1.1 路徑構建

為了進一步解決AS 中展現出來的缺陷，提出以Ant-Q 為基礎的優化算法——ACS。在ACS 算法中，根據偽隨機比例規則，位于第k個城市的第i只螞蟻選擇下一個訪問的城市j。這個規則如式（1）：

其中，q是均勻分布在區間[0,1]中的一個隨機變量，q0（0 ≤q0≤1）是一個參數，ηij表示i、j城市之間距離的倒數，τij表示i、j城市之間信息素的總量，allowed表示不在螞蟻禁忌表中的城市集合。J是一個隨機變量，如式（2）所示：

式中，α、β分別表示信息素和啟發因子在概率計算中所占的權重。

2.1.2 信息素的更新

（1）全局信息素更新

針對當前最好路徑上的邊進行信息素更新，更新的規則如式（3）所示：

其中，Δτij=1/Lgb，Lgb代表至今最優路徑長度，Δτij表示信息素的增加量，ρ代表全局信息素蒸發速率。全局信息素的更新有助于提高算法的收斂速度。

（2）局部信息素更新

當螞蟻k從城市i經過下一個城市j之后，i、j城市之間路徑上的信息素的更新規則如式（4）所示：

其中，ρ代表局部信息素蒸發速率，τ0代表每條邊信息素的初始值。局部信息素的更新使得每條邊上的信息素相應地減少，防止算法過早陷入局部最優，增加了算法的多樣性。

2.2 MMAS 蟻群算法

為了使得算法在最短路徑附近搜索，從而逐步找到全局最優解，算法只會對當前循環中所產生的最短路徑進行信息素的更新操作，如式（5）所示：

為了防止某些邊上的信息素增長過快，而導致停滯現象的出現，MMAS 算法中任何一條邊上的信息素的大小都被限制在[τmin,τmax]的范圍內。如果當前邊上的信息素的濃度高于τmax時，就使該邊上的信息素的濃度定為τmax，τmax如下公式所示：

其中，f(sopt)是全局最優解，ρ是信息素的揮發因子。

如果當前邊上的信息素的濃度低于τmin時，就讓該邊上的信息素的濃度定為τmin，τmin如下公式所示：

其中，pbest是MMAS 算法收斂時找到最優解的概率（一般為0.05）。

2.3 最大最小生成樹

最大最小生成樹的概念被提出于數據結構中，它們都是樹形結構。后來很多專家學者對最大最小生成樹算法進行了改進與應用[21-22]。

2.3.1 最大最小生成樹的定義

在一個給定的n個頂點的完全連通圖G=(V,E)中，頂點u與頂點v的連線的邊表示為(u,v)，而w(u,v)代表此邊的權重，如果存在T為E的子集且為無循環圖，使得w(T)最小，則此T為G的最小生成樹，反之如果w(T)最大，則此T為G的最大生成樹。w(T)如式（8）所示：

2.3.2 最大最小生成樹的構建

最大最小生成樹的構造有很多著名的方法，比如克魯斯卡爾算法（Kruskal）和普里姆算法（Prim）。

（1）Kruskal算法主要思想

將V的每個節點定義為一棵樹，并定義為根節點，將E中的邊按權重從小到大依次處理。首先判斷邊的兩個節點是否屬于同一棵樹（根據根節點是否一致），若不是，則合并兩棵樹，并更新根節點；若是，則不予理會。

（2）Prim 算法主要思想

給定連通圖G和任意根節點r，最小生成樹從節點r開始，一直長大到覆蓋V中所有節點為止，即不斷尋找輕量級邊以實現最小權重和。

3 改進的蟻群算法

3.1 動態導向策略

在求解TSP 問題中，最小生成樹與最優路徑之間有著非常密切的關系。在通常情況下，最小生成樹中的70%～80%的路徑與TSP 問題的最優路徑是吻合的。將最小生成樹的信息結合到求解TSP 問題中去，且每次迭代，結合的信息素動態變化，使得在求解過程中加快算法的收斂速度，起到了動態正導向性。

TSP 問題里，螞蟻選擇下一個城市的依據有兩個因素：一個是i、j城市之間的信息素的濃度啟發信息；另一個是i城市到j城市的距離啟發信息；即i、j城市之間距離的倒數。城市之間初始信息素為一個常數，在算法首次迭代的時候，每條路徑中的信息素對螞蟻的吸引力都是相同的，而城市之間的距離啟發信息是不同的，因此在算法剛開始運行的時候，螞蟻選擇下一個城市的概率是城市之間的距離啟發信息占主導地位，即城市之間的距離越短，該路徑被選擇的概率就越大。但是這條路徑所在的解并不一定是最優解，因此容易陷入局部最優解。為了避免這一缺陷，在算法的初期會動態強化最大生成樹n-1（n為城市數）條邊的信息素，以增加算法的多樣性，起到了動態負導向性。

3.1.1 最大生成樹策略

屬于最大最小生成樹邊的路徑上所釋放的信息素稱為生成樹信息素。在算法的前期，結合最大生成樹的信息，在迭代次數n∈(0,n0]時，屬于最大生成樹中的邊的兩個城市之間的路徑上釋放相應濃度的動態信息素，額外增加信息素的量如式（9）所示：

其中，N為最大迭代次數，τ0表示邊的信息素的初始值，ρ大表示最大生成樹調整因子，以調整生成樹信息素在算法前期的影響權重。在多次實驗結果的對比下，n0取[N/2]，ρ大取2 的時候，本文實驗結果最佳。由于(N-n)/N是減函數，值域在[1/2,1)，因此τ樹大也是減函數，添加屬于最大生成樹路徑上的信息素濃度是逐代遞減的，即每次迭代在最大生成樹的n-1 條邊上動態強化的幅度是遞減的，使得相應路徑的生成樹信息素濃度總體增加的同時不會過度累積，以增加算法在前期的多樣性，并且前期多樣性越來越好，以防止算法陷入局部最優。

3.1.2 最小生成樹策略

在算法的后期，結合最小生成樹的信息，在當前迭代次數n∈(n1,N]時，屬于最小生成樹的邊的兩個城市之間的路徑上釋放相應濃度的動態信息素，額外增加的信息素的量如式（10）所示：

其中，ρ小表示最小生成樹調整因子，用來調整生成樹信息素在算法后期的影響權重。本文實驗中n1取N-[N/2]，ρ小取2。由于n/N是增函數，值域在（1/2,1]，因此τ樹小也是增函數，使得算法后期達到快速收斂的效果。

3.2 鄰域交互策略

在初始階段，將蟻群分成兩類種群，兩類種群內的螞蟻釋放自己種群內的信息素，使得兩類種群螞蟻工作時有相應的獨立性。但是，在第一類螞蟻按照自己的規則遍歷城市的基礎上，第二類螞蟻在選擇路徑和信息素更新時，會受到第一類螞蟻在鄰域內所釋放信息素的影響，即引入吸引因子，使得第二類螞蟻盡可能容易地選擇第一類螞蟻已經選擇過的最優解的部分路徑，以達到更快地尋得最佳路徑，從而提高了算法整體的收斂速度，使得兩個種群有著緊密的交互性。

3.2.1 吸引因子

在第二類螞蟻遍歷城市的過程中，引入吸引因子：

每個以i為圓心的鄰域內路徑上由第二類螞蟻釋放的信息素的總和是一定的，當第一類螞蟻在(i,j)城市之間的路徑上所釋放的信息素越大時，所求的吸引因子的值越大，說明第二類螞蟻就會以更高的概率選擇第一類螞蟻集中選擇過的路徑，使得第二類螞蟻選擇城市更具有導向性。

由于吸引因子記錄了第一類螞蟻在路徑上釋放的相關信息素的信息，在第二類螞蟻遍歷城市時，引入吸引因子，使得第二類螞蟻在路徑選擇的時候會考慮到第一類螞蟻遍歷城市時的有關信息。

首先將吸引因子引入到狀態轉移規則中，如3.2.3 小節的敘述，在綜合考慮了第二類螞蟻自身相關啟發信息的同時，還結合了第一類螞蟻的信息素啟發信息，使得第二類螞蟻選擇路徑時會受到第一類螞蟻留下的信息素啟發信息的影響，且第一類螞蟻遍歷城市時所選擇的較優路徑在對第二類螞蟻選擇路徑時有更大的影響，體現了第一類螞蟻的信息素啟發信息對第二類螞蟻的正反饋作用，即吸引因子的正反饋作用。由于正反饋的作用，使得那些較優路徑上的信息素累積比一般路徑上要快且多，因此算法的收斂速度會加快，并且收斂精度也會提高。

其次將吸引因子引入到局部信息素更新策略中，如3.2.4 小節的敘述，讓每條路徑的信息素揮發量相應地減少，不僅起到了正反饋作用，同時也抑制了多樣性，使得算法的收斂能力得到加強。

綜合而言，吸引因子對算法起到了正反饋作用，同時加快了算法的收斂速度，提高了算法的收斂精度。

3.2.2 關聯鄰域

為了能夠高效地結合有效信息素，并且在一定程度上減少每次計算吸引因子的速度，提出了關聯鄰域的概念，經過多次實驗結果分析得出關聯鄰域的定義如下：

以城市i為圓心，以半徑r畫一個圓，此圓就稱為i城市的關聯鄰域[23]。半徑r的大小如式（12）所示：

其中，m表示總的城市個數，lim表示第i個城市到第m個城市的距離。

由于本文所選TSP 城市數目較多且分布比較緊密，同時半徑r的選擇相對較大，半徑外的城市距離中心點相對較遠，因此在計算吸引因子時，即使關聯鄰域計算了半徑外的城市，最終也不會選擇其作為下一個經過的城市。故關聯鄰域能夠高效地結合有效信息素，使得減少程序的運行時間。

3.2.3 改進的狀態轉移規則

在第一類螞蟻使用原始ACS 狀態轉移概率公式的基礎上，第二類螞蟻運用了改進的狀態轉移規則，引入了吸引因子。使得第二類螞蟻不僅考慮了自身的信息素啟發信息和距離啟發信息，還結合了與第一類螞蟻所釋放信息素的有關的信息，即吸引因子。綜合了種群內的信息和種群間的信息，使得第二類螞蟻在遍歷城市的時候更加容易尋得高質量的解。引入吸引因子的第二類螞蟻的改進狀態轉移規則如式（13）、式（14）所示：

由于在第i個城市選擇下一個城市j時，i是固定不變的，因此(i,j)城市之間路徑上的信息素濃度決定了吸引因子的大小。式（13）、式（14）中結合了吸引因子，使得第二類螞蟻在選擇下一城市時，更偏向于第一類螞蟻選擇過的較優路徑，體現出了吸引因子的正反饋作用。吸引因子加強了兩個種群之間的交流，使得第二類螞蟻遍歷城市的時候更具有方向性，加快了算法的收斂速度。

3.2.4 改進的局部信息素更新策略

在ACS 算法中，每條邊信息素τij都有一個隱含的限定范圍條件，即τ0≤τij≤1/Cbs。當吸引因子加入到局部信息素更新策略中時，由于τ0≤τij，0 ≤αij≤1，因此每條邊進行局部更新的時候，其信息素減少的趨勢更加緩慢，引入吸引因子的局部信息素更新策略如式（15）所示：

式（15）等價于τij(t+1)=τij(t)+αij ρ(τ0-τij(t))，由于局部信息素更新是減少路徑上的信息素，增加算法的多樣性，引入吸引因子，再進行局部信息素更新后，路徑上減少的信息素濃度的幅度降低，即路徑上保留的信息素濃度比沒有引入吸引因子的算法的路徑上要多。這樣在一定程度上抑制了多樣性，使得吸引因子的正反饋作用更能體現出來，加快了算法的收斂速度。

3.3 算法流程圖

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

圖1 是本文算法的基本框架。首先引入的吸引因子會使第二類螞蟻根據第一類螞蟻釋放的信息素更快地尋得最優解，不僅提高了解的質量，也加快了收斂速度。然后在算法的前期結合最大生成樹策略，提高了算法的多樣性，而在后期結合最小生成樹策略，加快了算法收斂速度，從而平衡了算法的多樣性和收斂性。

3.4 時間復雜度

從上述算法流程圖的分析可以得出，本文算法TREEACS（double-type ant colony algorithm considering dynamic guidance and neighborhood interaction）的時間復雜度為O((n0×k1×m+n0×k2×m)+((N-n0)×k1×m+(N-n0)×k2×m))，式中N為最大迭代次數，n0為，k1為第一類螞蟻的數量，k2為第二類螞蟻的數量，m是城市數。因此TREEACS的最大時間復雜度為O(N×k×m)，ACS的最大時間復雜度為O(N×k×m)，MMAS的最大時間復雜度為O(N×k×m)，由此可見，本文算法相比ACS、MMAS 沒有改變最大時間復雜度。

3.5 算法收斂能力分析

為了加快算法的收斂速度，提高算法的收斂精度，TREEACS 算法首先結合了動態導向策略中的最小生成樹策略，由于最小生成樹中的70%～80%的路徑與TSP 問題的最優路徑是吻合的，因此在算法的后期，每次迭代動態增加屬于最小生成樹相應路徑上的信息素濃度，起到了正導向性，使得算法的收斂能力得到提高。其次TREEACS算法還結合了鄰域交互策略，使得第二類螞蟻在遍歷城市的時候，不僅考慮了自身的距離啟發式信息和信息素啟發式信息，還結合了吸引因子，即第一類螞蟻所釋放的相關信息素信息，讓第二類螞蟻以更高的概率選擇那些被第一類螞蟻走過的較優的路徑，不僅對算法起到了正反饋作用，又進一步提高了算法的收斂速度和收斂精度。

下文以實驗形式對算法的綜合收斂能力進行了分析，結果表明收斂速度和收斂精度都有所提高。綜合而言，TREEACS 算法的綜合收斂能力優于傳統的蟻群算法和一些其他改進蟻群算法。

4 實驗仿真

為了檢驗改進后算法的有效性，本文使用Matlab2017a 對TSPLIB 標準庫中的十幾個不同規模的城市進行了模擬仿真，并且與ACS、MMAS 進行比較，為了進一步檢驗本文算法的性能，又與其他兩種改進的蟻群算法進行比較。

4.1 實驗結果分析

為了有效地驗證TREEACS 的性能，本文實驗中在TSPLIB 標準庫中選取若干城市進行系統性的分析，同時還與經典的ACS、MMAS 算法進行綜合比較，分析改進算法性能的優劣。

Fig.2 Comparison of error rates of ACS,MMAS and TREEACS圖2 ACS、MMAS 和TREEACS 誤差率對比圖

Table 1 Simulation experiment data of ACS,MMAS and TREEACS表1 ACS、MMAS 和TREEACS 仿真實驗數據

由圖2 和表1 可知，運用本文算法TREEACS，城市數在中小規模以下的9 個測試集中100%的城市是可以得到標準最優解的，城市數在大規模的測試集中，50%以上的城市誤差率在0.1%左右，并且無論是中小規模或大規模城市的最優解，平均解和誤差率都明顯優于ACS 和MMAS 算法。TREEACS 在結合最大生成樹的基礎上，還加入了MMAS 的信息素限定策略，不但使得算法的多樣性加強，還使得算法易于跳出局部最優，從而找到更優解。

4.2 TREEACS 最優解與收斂性對比

圖3 表明，運用TREEACS 算法，中小規模的測試集中尤為明顯，不僅收斂速度比ACS 和MMAS 更快，而且還能精準地找到標準最優解；在大規模的測試集中，收斂速度依然優于ACS 和MMAS，雖然沒有找到標準最優解，但是得到最優解的精度比ACS 和MMAS 都有很大的提高。由于TREEACS 算法結合了最小生成樹策略和吸引因子，使得算法在收斂速度方面有了很大的提升。

Fig.3 Experimental comparison of TREEACS with ACS and MMAS圖3 TREEACS 與ACS、MMAS 實驗對比

4.3 最大最小生成樹策略

4.3.1 最大生成樹多樣性對比

為了驗證最大生成樹策略對于算法多樣性帶來的優勢，本文分別選取小規模測試集eil51、中規模測試集kroB150、大規模測試集pr264 來進行標準差斷點分析。圖4 表明，TREEACS 算法在三個測試集中的標準差斷點值都要比S-TREEACS（缺少最大生成樹策略的TREEACS）算法的標準差斷點值要大。這充分說明了加入最大生成樹策略明顯加強了算法的多樣性。

4.3.2 最小生成樹收斂性對比

圖5表明，TREEACS算法在1 000代之后引入最小生成樹策略的時候，收斂速度明顯比L-TREEACS（缺少最小生成樹策略的TREEACS）算法要快，而且TREEACS 算法會在剛進入1 000 代不久就會跳出局部最優，找到更精確的解，但L-TREEACS 算法則要在迭代末期才能再次跳出局部最優。這也說明了加入最小生成樹策略能使算法更快地收斂。

4.4 吸引因子收斂性對比

為了驗證吸引因子策略對于算法收斂性帶來的優勢，本文分別選取小規模測試集eil51、中規模測試集kroB100、大規模測試集kroA200 來進行分析。圖6 表明，TREEACS 算法的收斂速度明顯比NAFTREEACS（缺少吸引因子策略的TREEACS）算法的要快，且TREEACS 算法的收斂精度也明顯比NAFTREEACS 算法的要好。因為鄰域交互策略中的吸引因子對算法起到了正反饋作用，使得不僅可以加快算法收斂速度，而且能夠提高收斂精度。

Fig.4 Comparison of standard deviation breakpoints between TREEACS and S-TREEACS圖4 TREEACS 與S-TREEACS 標準差斷點對比圖

Fig.5 Comparison of convergence of TREEACS and L-TREEACS圖5 TREEACS 與L-TREEACS 收斂性對比圖

Fig.6 Convergence comparison between TREEACS and NAF-TREEACS圖6 TREEACS 與NAF-TREEACS 收斂性對比圖

Table 2 Comparison of TREEACS with other improved algorithms表2 TREEACS 與其他改進算法的對比

4.5 與改進蟻群算法及其他算法對比

本文算法與改進蟻群算法及其他算法進行比較，其中D-ACS（ant colony algorithm for heuristic dynamic pheromone update strategy）改進蟻群算法的數據取自文獻[24]，改進蟻群算法的數據取自文獻[25]，OMACO（object-oriented multi-role ant colony optimization）改進蟻群算法的數據取自文獻[26]，IMRGHPSO（improved random greedy PSO based on Hamming distance）改進粒子群算法的數據取自文獻[27]，1OGA（1-phase optimal GA）改進遺傳算法取自文獻[28]。

根據表2 的實驗結果可知，本文算法TREEACS無論是在中小規模還是大規模的TSP 問題中，解的精度明顯優于改進蟻群算法及其他算法。

5 結束語

由于TSP 問題中存在易陷入局部最優和導向性不足的問題，本文首先引入了動態導向策略，前期在最大生成樹策略的影響下，通過增加相應路徑上的動態信息素，以使算法達到更好的多樣性，并且增加的額外生成樹信息素的量是逐代遞減的，以防止相應路徑信息素累積較快。后期在最小生成樹策略的影響下，同樣是添加相應路徑上的動態信息素，增加的生成樹信息素的量是逐代遞增的，使得算法的收斂性大大提高。再結合MMAS 的上下限機制，使得每條邊上的信息素濃度不會積累得過多而使算法早熟。同時算法結合鄰域交互策略，引入吸引因子，發揮了正反饋機制，進一步加強了算法的導向性。

實驗結果證明，本文算法在中大規模的TSP 問題求解的精度上有很大的提高，多樣性和收斂性也有明顯的改善。今后將進一步研究多種群蟻群算法的模型，從而更好地提高算法的性能。