結合ABC算法動態分級的雙蟻態蟻群算法

李順東，游曉明，劉 升

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

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

1 引言

旅行商問題[1]（Traveling Salesman Problem，TSP）是經典NP-hard組合優化問題，它可以簡單地描述為：旅行商從規定的城市列表中選擇一個城市作為起點，不重復地遍歷完所有城市，最終再返回到初始位置，從而找到一條最短的閉合回路。目前解決TSP問題的算法[2-5]有很多，其中蟻群算法由于良好的并行性、正反饋性以及極強的魯棒性等特點，成為最有效的方法之一。

20世紀90年代，意大利學者Dorigo等人受自然界蟻群覓食行為的啟發創新性地提出了蟻群算法（Ant System，AS）[6]，但算法存在收斂速度慢，易陷于局部最優等問題。在此基礎上，1996年Dorigo等[7]結合Q-learning思想提出了全新機制的ACS算法。該算法沿用了兩種信息素更新方式，加快了算法收斂速度。同期，Stutzle等人[8]又提出了最大最小螞蟻系統（Max-Min Ant System，MMAS），為每條路徑上信息素濃度設定了上、下限閾值區間，避免信息素濃度無限累加而停滯，提高了算法的多樣性。此后，眾多專家學者在這兩者算法的基礎上做出了改進：文獻[9]提出了一種動態信息素策略的改進算法，通過動態改變偽隨機因子的閾值，來平衡算法的多樣性和收斂速度。文獻[10]通過融合模擬退火算法，提出了一種自適應模擬退火蟻群算法，提高了解的質量。以上改進算法，雖然在一定程度上取得了進步，但在蟻群協同分工機制方面仍然存在著不足。

針對不足，Dorigo等人曾提出過精英螞蟻系統（Elitist Ant System，EAS），通過對螞蟻分級，分別執行不同的信息素更新策略，突出了最優路徑螞蟻的精英作用，為蟻群的路徑選擇增加導向性，加快了系統的收斂速度。Bullnheimer等人[11]還提出過RAS形式的螞蟻分級系統等。實驗證明，在蟻群算法的基礎上實行分級機制，效果良好，改善了群智能優化算法本身存在的收斂性和多樣性的矛盾。此后，很多其他分級機制的算法應運而生。其中，人工蜂群算法表現較為突出。

自然界中蜂群采蜜以分工協作而聞名，不同級別的蜂種各司其職共同完成采蜜任務。根據這一特性，Karaboga等[12]提出了人工蜂群算法（Artificial Bee Colony，ABC），算法通過適應度不同將蜂群進行分級、分工協作，既凸顯了精英蜂群的引領作用，加快找到優質蜜源速度，又通過偵察蜂群隨機搜索更多優質蜜源，提高了算法解的精度。

鑒于此，本文在ACS算法基礎上，融合了人工蜂群算法分級思想，提出了一種動態分級的改進蟻群算法（ABC-ACS）。通過引入適應度分級算子，將蟻群劃分為兩種蟻態：尋優蟻和偵查蟻。尋優蟻的作用是搜索較優路徑，經過若干次迭代最終找到最優解；偵查蟻則負責開發其他路徑，搜索更多優化解。兩類螞蟻分別執行不同加權系數的動態信息素更新策略，使得較優路徑和非較優路徑之間的信息素產生一定的濃度差，既突出了尋優蟻的導向作用，又不會影響偵查蟻繼續搜索其他更優解的能力，從而不僅增加了算法導向性，加快收斂速度，又保持了算法的多樣性，避免陷入局部最優。此外，在每次迭代結束后兩類螞蟻執行優良解交換策略，提高了解的質量。最后，通過ACS全局最優路徑信息素更新策略，使算法收斂速度進一步提高。另外，為了使所得解的質量更優，算法還融合3-opt算子對其繼續優化。

2 相關工作

2.1 ACS蟻群算法

2.1.1 路徑構建

ACS算法模型中每只螞蟻從城市i到城市j之間轉移，是利用偽隨機概率公式進行選擇的，公式如下：

其中，τij為城市i和城市j之間信息素濃度的大??；allowedk∈{ }n-tabuk表示螞蟻k下一步可選擇的城市；ηij(t)是啟發式函數，表示螞蟻k從城市i轉移到城市j的期望度，且表示相鄰城市i和j之間的距離；αβ分別表示信息啟發式因子和期望啟發式因子，αβ值越大，對下一條路徑的選擇影響越大。q是區間[0，1]上均勻分布的隨機變量；q0是區間[0，1]上的可調參數；當q≤q0時，螞蟻k根據偽隨機比例公式（1）選擇最優路徑；當q＞q0時，則按照s即輪盤賭公式進行路徑選擇，如式（2）所示：

本文ABC-ACS沿用了ACS的偽隨機比例規則，其先進之處在于：算法在路徑構建時，螞蟻以q0概率選擇當前可能最優的移動方式，又以1-q0概率有偏向性地探索各條邊。通過合理調整參數q0，就可以有效地調節算法對于每條新路徑選擇的優先級和探索度，從而決定算法應該集中探索當前最優區域還是其他區域，確保在局部加權信息素更新時，對不同探索度的路徑引入相應比例的權重進行更新，即較優路徑加權大，其他路徑加權小，進而保證了局部信息素動態加權更新規則的準確性。

2.1.2 信息素更新

ACS蟻群算法的更新機制分為局部信息素更新和全局信息素更新兩部分。

局部信息素更新：當每只螞蟻完成一次周游后，算法便會對其走過的路徑進行局部信息素更新。局部信息素更新是對所有螞蟻都進行更新，其作用是為了縮短最優路徑和非最優路徑之間信息素的差距，增加算法的多樣性，提高算法全局搜索能力，避免陷入局部最優。其公式如（3）所示：

式中，τ0為每條路徑上的初始信息素濃度；ρ是局部信息素揮發率。

全局信息素更新：當所有螞蟻都完成一次迭代之后，算法只對當前最優路徑上的信息素進行更新，通過算法的正反饋作用，使得最優路徑和非最優路徑上的信息素的差距逐漸拉大，為蟻群的路徑選擇增加指向性，加快了算法的收斂速度，如式（4）所示：

式中：

其中，ρ是全局信息素揮發率，Δτij是信息素增量，Lgb是當前最優路徑的長度。

2.2 3-opt搜索算子

K-opt是TSP問題中廣泛應用的啟發式搜索方法。其中，3-opt[13](K=3)是效率較高的局部優化算法。該算法主要通過對螞蟻構建的路徑進行局部優化，提高解的質量，從而得到最優解。其流程大致為：

步驟1螞蟻完成路徑構建，生成Hamilton回路T。

步驟2在回路T上隨機選取三個點切開重組，形成新的閉合回路，如圖1所示。

步驟3將新的回路和舊的回路T進行解的比較，保留其中較優解。

步驟4重復執行該算法，直到找到最優解。

圖1 3-opt路徑重組

3 改進蟻群算法

3.1 ABC算法動態分級策略

3.1.1 ABC算法分級思想

人工蜂群（ABC）算法是由土耳其學者Karaboga于2005年提出的，它是受到自然界中蜂群采蜜行為啟發的群智能優化算法，其模型主要是由：蜜源、引領蜂、跟隨蜂和偵查蜂四個要素組成。在求解TSP[14-17]時，ABC算法首先根據蜜源i(i=1,2,…,NP)的質量計算對應的適應度fiti；然后根據適應度值的大小將蜂群劃分為引領蜂、偵查蜂和跟隨蜂三種類型：引領蜂負責搜索蜜源；引領蜂歸巢分享蜜源信息，跟隨蜂按一定比例選擇是否跟隨；偵查蜂負責搜索空間內其他蜜源。

3.1.2 動態適應度分級算子

蟻群算法自提出以來就存在著收斂速度慢、易陷入局部最優、協同機制不夠完善等問題，而目前單種群單形態蟻群算法無法實現收斂速度和多樣性之間的平衡，因此本文借鑒了人工蜂群算法分級的思想，引入動態適應度分級算子，將蟻群劃分為尋優蟻和偵查蟻兩種蟻態并行搜索。其中尋優蟻負責較優路徑的搜索，通過較高加權系數的信息素更新規則，突出較優路徑上的信息素強度，增強其導向性，提高算法的收斂速度；而偵查蟻則負責開發較優路徑以外的其他路徑，尋找更多優質解，保證了算法的多樣性，增強其跳出局部最優的能力，提高了解的質量。因此，通過動態分級蟻群進行并行搜索，實現了多樣性與收斂速度之間的平衡。

定義動態適應度分級算子如公式（6）、（7）所示：

式中，fiti表示每只螞蟻對應的適應度值(0＜fiti≤1)，如公式（6）所示，其值由lengthmin和lengthi的比值所決定，lengthmin表示當前迭代中的最短路徑；lengthi表示每只螞蟻迭代一次的路徑長度；根據所計算的適應度fiti值的不同，將整個蟻群劃分為兩類，如公式（7）所示，M為偵查蟻與尋優蟻的分級閾值界點(0＜M＜1)：當0＜fiti≤M時，為偵查蟻；當M＜fiti≤1時，則為尋優蟻。M值并非任意選取，其大小直接影響算法整體的求解精度。因為M值過大時，偵查蟻的數量則會增多，從而導致大量的無用搜索，影響算法的收斂速度；而當M值過小時，尋優蟻的數量過多又會導致某些較優路徑上的信息素過度累積而陷入局部最優，影響算法的多樣性以及解的質量。本文通過大量的實驗對比，驗證了當M=0.7時，算法的性能表現最佳，求解精度最優。

3.2 改進的動態信息素更新策略

為了更好地平衡蟻群算法多樣性和收斂速度之間的矛盾，本文在ACS局部信息素更新策略的基礎上，引入了加權[18]系數和適應度值，使得不同級別的螞蟻執行不同加權系數的動態信息素更新策略，如公式（8）～（10）所示：

式中：

其中，λ1λ2為加權系數；fiti為對應螞蟻計算的適應度值。

需要說明的是，原ACS算法的局部信息素更新策略對于每只螞蟻都是相同的，整個算法只依靠全局更新策略來增強較優路徑上的信息素濃度，不能很好地突出其導向作用，從而在較短的時間內找到最優解，因此，本文融合了EAS的精英思想對局部信息素更新公式進行加權改進：

（1）當M＜fiti≤1時，為尋優蟻，其局部信息素更新公式為式（8）、（9）。

（2）當0＜fiti≤M時，為偵查蟻，其局部信息素更新公式為式（8）、（10）。

其中，λ1為尋優蟻群的局部信息素加權系數，λ2為偵查蟻群局部信息素加權系數，并定義λ1＞λ2，目的是為了區分兩類蟻群搜索路徑上的信息素濃度，突出較優路徑的精英導向作用，從而縮短算法找到最優解的周期。通常λ1只能略大于λ2，因為λ1與λ2之間相差過大都會導致算法過早停滯而陷入局部最優，影響算法求解的精度。因此，本文在進行大量實驗對比之后，驗證了當λ1=4、λ2=2時效果最好，故取之為兩類螞蟻局部信息素更新改進策略的加權系數。

此外，改進的局部信息素更新策略還引入了螞蟻的適應度值fiti，目的是為了讓每只螞蟻能夠根據自身適應度值的大小動態地進行局部信息素更新，因為適應度值大的螞蟻，搜索的路徑相對較優，通過改進的局部信息素更新策略便會獲得更高濃度的信息素更新，導向作用也隨之增強。

整體而言，在原ACS算法的基礎上，動態改進局部信息素更新策略，既保持了每條路徑上都有信息素增加的特性，又使其濃度和影響力根據自身適應度的不同動態變化，從而形成路徑間的濃度差，即適應度高的較優路徑增加的信息素高，適應度低的次之。當算法陷入局部最優時，偵查蟻依然具備搜索其他更優路徑的能力，保證了算法的多樣性，提高全局尋優的能力，從而有效地幫助算法跳出局部最優；進一步，通過較優路徑的精英導向作用加快了收斂速度，從而使全局尋優能力與局部尋優能力之間達到平衡。此外，算法的全局更新依然沿用ACS算法的更新策略，即在所有螞蟻完成一次迭代之后，只更新當前最優路徑上的信息素，如式（4）所示，目的是為了進一步突出最優路徑的導向作用，從而加快收斂速度。

3.3 優良解的交換策略

當iter=1時，算法利用ACS的路徑構建公式和信息素更新公式完成第一次迭代，并計算相應的適應度值來將蟻群進行劃分：當0＜fiti≤M時，為偵查蟻；當M＜fiti≤1時，則為尋優蟻。

從第二代開始(iters≥2)，算法首先會對上一代劃分的兩類螞蟻進行路徑構建，然后再通過不同加權系數的局部信息素公式進行信息素更新，且在每一次迭代之后，都要判斷兩類螞蟻是否需要進行優良解的交換，主要思路為：若偵查蟻構建的路徑集合中存在‖ length ‖＜‖ length ‖，則對兩類螞蟻執行優良解的交換：

交換后的兩類螞蟻身份職能互換，即原來較優的偵查蟻轉變為新的尋優蟻，而被替換掉的尋優蟻則淪為偵查蟻，執行偵查蟻的職能。在完成優良解交換之后，系統開始進行下一輪迭代；若一次迭代中不存在偵查蟻優于尋優蟻的解情況，算法則不進行優良解交換，直接進入下一輪迭代。優良解交換策略的大致過程如圖2所示。

圖2 優良解交換

通過優良解的交換策略，可以使每一代尋優蟻解的集合不斷更新，始終保持較優路徑集合的質量更優；偵查蟻不受尋優蟻導向作用的影響，繼續搜索當前較優路徑以外的其他路徑，保證了算法的多樣性，增強了算法全局尋優能力。當偵查蟻尋得更優解時，則與當前較優路徑集合進行優良解交換，從而幫助算法跳出局部最優，提高了解的精度。優良解的交換設定是從第二代開始，直到尋優蟻解的集合不再發生變化或者達到最大迭代數為止。

3.4 ABC-ACS算法流程

本文所提出的結合ABC算法動態分級的雙蟻態蟻群算法的算法流程可以簡單地描述如下。

步驟1參數初始化。

步驟2 NC=1，將m只螞蟻分別分配n個城市。

步驟3螞蟻k根據式（1）和輪盤賭的方式（2）進行下一城市的轉移。

步驟4所有螞蟻完成第一次迭代，根據公式（6）、（7）計算相應的適應度值，并將蟻群分級為尋優蟻和偵查蟻，NC=NC+1。

步驟5完成第NC次迭代，算法根據式（1）完成兩類螞蟻路徑的構建。

步驟6然后，根據式（8）～（10）分別對尋優蟻和偵查蟻執行局部信息素更新。

步驟7當所有螞蟻完成迭代，兩類螞蟻進行優良解交換，若達到交換條件，則根據式（11）進行交換；否則，不進行交換。

步驟8根據式（4）進行全局信息素更新。

步驟9當NC≤NCmax時，NC=NC+1，跳轉到步驟5；否則，轉到步驟10。

步驟10輸出最優解。

算法的整體框架如圖3所示。

算法流程：

ABC-ACS Algorithm for TSP

1.Procedure ABC-ACS（）

2.Begin：

3.Initialize the pheromone and parameters

4.Calculate the distance between cities

5.#Algorithm：ACS

6.for iter=1 do

7.for i←1 to m do#m as ant'snumber

8.for j←2 to n do#n as cities'number

9.Construct ant solutions

10.Compute fitness&Classify ants

11.end-for

12.end for

13.end-for

14.Update pheromones

15.#Algorithm：ABC-ACS

16.for iter←2 to NC do

17.for i←1 to m do#m as ant'snumber

18.for j←2 to n do#n as cities'number

19.Construct ant solutions

20.Update dynamic local pheromones

21.if(‖ length ‖＜‖ length ‖)do

22.Exchange excellent solutions

23.end if

24.end for

25.end for

26.end for

27.Update pheromones

3.5 算法復雜度分析

由算法流程分析可知ABC-ACS算法的復雜度為O(1×m×(n-1)+(NC-1)×m×(n-1))，具體可分為兩個部分：其中，第一代算法沿用的是ACS算法進行路徑構建、求解，其復雜度為O(1×m×(n-1))；而從第二代開始，根據第一代所產生解的適應度將種群分為兩個蟻態繼續進行迭代，其算法復雜度為O((NC-1)×m×(n-1))。所以，改進后算法的總體復雜度為O(NC×m×n)，而ACS算法的復雜度為O(NC×m×n)，可見本文算法的復雜度并未發生改變。

3.6 算法收斂性分析

3.6.1 經典ACO算法收斂性分析定理[8]一旦找到最優解s*，則公式（12）成立：

對于經典蟻群算法而言，只存在全局信息素更新機制，其更新公式為τij(t+1)=(1-ρ)τij(t)+Δτij(t)。假設一次迭代之后任意一條邊(i,j)上的信息素的最大增量為qf(s*)，則根據更新公式可知，第一次迭代中信息素最大值是(1-ρ)τ0+qf(s*)，第二次迭代中最大值是(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此類推，第θ次迭代中最大值。由于信息素具有揮發作用，信息素水平只能漸近于最大值水平，故。所以，一旦找到最優解，所有邊上的信息素值都會收斂于τmax。此外，Dorigo等定義過每條邊都存在相同的初始信息素τ0，其值為大于0的極小常數，因此，τmin＞0。所以，對于任意一條邊而言，其信息素上下限為[τmin,τmax]。

根據式（2）蟻群算法的路徑構建公式可知，任意一個可行解都有其選擇概率p，且其下界pmin如公式（13）所示：

其中，Nc為成分集合C的勢；τmin為信息素值的下界。

需要說明的是，可行選擇概率p取到下界(p=pmin)時，即出現最優可行解增加的信息素濃度最低為τmin，而其他Nc-1個非最優可行解的信息素皆為最大值τmax的最差情況，那么求得任意的一般性解s′，包括任意最優解s*∈S*的概率，其中，n＜+∞是序列的最大長度，這足夠讓一只螞蟻找到一個最優解，P*(θ)有如下下限：

3.6.2 ABC-ACS算法收斂性分析

ABC-ACS算法與經典蟻群算法的不同點主要體現在幾個方面：第一，ABC-ACS沿用了偽隨機比例規則，使得算法在路徑選擇和局部信息素加權更新時更具偏向性和準確性；第二，ABC-ACS中并不是所有邊上的信息素都會蒸發，只有屬于至今最優解的邊才會蒸發信息素；第三，ABC-ACS中每只螞蟻在構造解時都會使用局部信息素更新規則，在螞蟻經過一條邊(i,j)之后立即更新素；第四，對局部信息素更新規則進行動態加權改進；第五，采用了優良解交換策略。

ABC-ACS算法具有局部、全局兩種更新機制，更新公式可以記為τij(t+1)=(1-ρ)τij(t)+ρb這種形式，在全局更新中，b=qf(sbs)；在局部更新中，b=τ0。當算法迭代θ次之后，信息素的最大值為，當θ→∞時，信息素的最大值漸近于。其次，τ0為信息素下限值。

根據公式（1）偽隨機比例規則可知，如果邊(i,j)的信息素值不是最大的，那么選中(i,j)的概率就是算法進行隨機選擇的概率(1-q0)與在隨機選擇中選擇邊(i,j)的概率的乘積。因為信息素取值存在上下限，所以任意一個可行解選擇都有概率p＞0，且存在下界pmin，其公式如式（13）所示。因此，構造任意可行解的概率都大于0，任意一條邊(i,j)選中的概率下界為(1-q0)pmin。根據公式（14）可得，ABC-ACS的下限公式為(θ)=1-(1-(1-q0))θ，則當迭代次數θ足夠大時，

4 實驗對比與結果分析

為了檢驗ABC-ACS算法的性能，本章選取了標準TSBLIP庫中19個經典的TSP實例進行仿真，每個實例進行10次實驗，并將其結果與傳統算法，最新改進算法以及其他算法作對比。

4.1 與經典算法對比

4.1.1 與經典算法性能對比分析

對比分析了算法的性能，驗證了本文算法求解質量更高，對比結果及算法搜索到的最優路徑迭代圖如表1和圖4所示。從表1可以看出，ABC-ACS在各種規模的TSP實例中，無論是最優解、平均解還是誤差率等方面都優于ACS和MMAS。其中，在Oliver30～pr107等小規模的TSP問題中，ABC-ACS都能以最快的速度找到標準最優解，算法尋優能力和收斂速度較ACS和MMAS均明顯提升；而隨著城市規模擴大，雖然ABC-ACS算法迭代數較大，但解的質量顯著提高：中規模TSP測試集的誤差均小于0.1%，其中，在ch130的測試上，算法所得解為6 113，而標準最優解為6 110，誤差率僅為0.05%；在KroB150的測試中，更是達到了標準最優解。而對于pr226～rand300等大規模TSP問題的測試中，誤差也都小于1%。這是因為對蟻群進行動態分級，并且執行優良解交換策略的結果，既保證了算法的多樣性，提高了算法的全局搜索能力，避免了陷入全局最優，又優化了解的質量。因此，同樣規模的測試集，ACS、MMAS花較少的迭代數但卻陷入早熟、停滯狀態，而ABC-ACS算法依然具有很好的多樣性和全局搜索能力可以繼續搜尋更優的解，充分說明了ABC-ACS算法的性能良好，且求解精度更高。

4.1.2 與經典算法收斂速度對比分析

為了更加充分比較ABC-ACS與經典算法的性能，本文又選取了eil51等不同規模的8個TSP實例對其收斂速度進行對比，結果如圖5所示。

由圖5所示，ABC-ACS在解決eil51等小規模TSP問題時，都能以最快的速度找到最優解，這是由于尋優蟻精英導向作用的影響，大大縮減了前期蟻群的搜索周期，提高了算法搜索效率；在求解KroA150等中規模的TSP問題時，雖然迭代數有所增大，但整體還是快于ACS、MMAS，且解的質量更高，標準最優解為26 524，ABC-ACS所得解為26 550，誤差率僅為0.1%。而對于求解KroA200等大規模TSP測試時，前期收斂速度依然很快，且后期種群多樣性依然好，這是由于ABC-ACS算法融合了人工蜂群分級的思想，對蟻群進行了動態分級，增加了算法搜索的多樣性，避免陷入局部最優。由于每一代搜索完成之后，算法都會執行優良解交換策略，故與ACS、MMAS相比，ABC-ACS算法后期收斂速度稍慢，但求解精度更高。

4.1.3 算法多樣性對比分析

為了進一步驗證改進算法的多樣性，本文以KroA100測試集為例，設置代碼執行斷點，統計算法執行到200、500、1 000、1 500以及2 000代時個體多樣性的變化情況，并與ACS算法作對比分析，結果如圖6所示，橫坐標為迭代次數，縱坐標為標準差值（用以衡量算法每次迭代的多樣性）。

通過圖6多樣性圖對比可以看出：ABC-ACS算法整體多樣性要優于ACS算法，且設置斷點執行代碼對比不同迭代數時兩個算法的個體多樣性情況，可以發現ABC-ACS依然更優。

其中，500～1 000代ABC-ACS多樣性下降趨勢明顯，這是由于算法改進了局部信息素更新規則，動態加權系數的引入，使得較優路徑上信息素增加的濃度要高于非較優路徑，從而突出了尋優蟻的導向作用，導致選擇較優路徑的螞蟻數大幅增多，加快了算法的收斂速度，因此多樣性下降幅度很大；而1 000～1 500代，多樣性又有所上升，這是因為偵查蟻不受尋優蟻導向作用的影響，而去搜索非較優路徑以發現更多優化解，并且通過優良解交換策略將發現的更優解與尋優蟻進行交流互換，從而幫助算法跳出局部最優，故多樣性得以增加；算法執行到后期1 500～2 000代，多樣性雖然有所下降，但依然高于ACS算法。所以，總體而言，改進后的ABCACS算法較ACS算法保持了良好的多樣性，并且通過動態加權的局部信息素更新規則，加快了算法的收斂速度。此外，兩類螞蟻各司其職、優良解交換，增強了算法全局尋優的能力，提高了解的質量（ABC-ACS找到的最優解是21 282，為標準最優解；ACS找到的最優解為21 292，存在誤差）。

表1 ABC-ACS、ACS、MMAS在不同TSP測試集的性能對比

圖4 最優路徑

4.2 與最新蟻群改進算法對比分析

為了更好地說明ABC-ACS算法求解精度高，本文又選取了劉中強等[9]提出的D-ACS和袁汪凰等[10]提出的SA-MMAS兩種最新的蟻群改進算法與eil51等不同規模的TSP問題進行性能對比，結果如表2所示。

明顯可以看出：ABC-ACS在求解選取的各個規模TSP問題時幾乎都能尋得最優解，其中KroA150和KroA200雖然沒達到最優解，但誤差都控制在很小的范圍之內，且各方面表現皆優于D-ACS和SA-MMAS。

圖5 收斂速度對比

表2 ABC-ACS、D-ACS、SA-MMAS性能對比

4.3 與其他優化算法對比分析

為了進一步驗證ABC-ACS算法的可行性以及性能的高效，本文還將其與最新粒子群改進算法IMRGHPSO[3]、蜂群改進算法Proposed ABC[15]進行對比，其結果如表3所示。

通過結果對比可以直觀地看出：ABC-ACS求解旅行商問題精度更高、性能更好，各個規模的表現皆優于最新的粒子群改進算法IMRGHPSO和蜂群改進算法Improved ABC，足以說明其可行性以及求解問題的性能高效。

綜合以上所有數據對比及分析表明：ABC-ACS算法既增加了導向性，提高了搜索效率，縮短了收斂周期；又增加了多樣性，提高了全局搜索能力，能夠跳出局部最優，發現更多優化解；再加上優良解交換策略的影響，使得算法求解精度更高。其中，結合表1和圖5可以看出，在解決中小規模TSP問題時，ABC-ACS均能以最快的速度找到最優解；而在解決少數的大規模TSP問題時，在沒有找到標準最優解的情況下，由于其良好的多樣性，不會很快收斂而陷入局部最優，與經典ACS、MMAS算法相比求解質量更好。結合表2可以看出，ABC-ACS不僅跟傳統的蟻群算法相比有優勢，對比最新的蟻群改進算法其性能優勢仍然明顯。而結合表3可以進一步直觀地看出，ABC-ACS與其他最新的智能優化改進算法相比其表現還是更優。所以整體來看，改進后的ABC-ACS算法在解決TSP問題時既具備較快的收斂速度，又有較好的多樣性。而且，無論是對比經典的蟻群算法，還是對比最新的蟻群改進算法，又或是其他最新的改進優化算法，ABC-ACS算法皆表現得更優，性能更好，實用性很強。

表3 ABC-ACS、Improved ABC、IMRGHPSO性能對比

圖6 多樣性對比

5 結束語

本文提出動態分級的改良蟻群算法，結合人工蜂群算法分級的思想，將蟻群劃分為偵查蟻和尋優蟻兩個蟻態進行分工合作解決TSP問題。其中，尋優蟻增加導向性，提高收斂速度；偵查蟻增加多樣性，避免陷入局部最優。然后，通過優良解的交換，對所求解的質量進行優化。最后，應用ACS全局信息素更新策略，突出全局最優路徑的精英導向作用，使算法很快找到最優解。經過多次不同規模的TSP實驗，以及與經典蟻群算法、最新改進算法還有其他最新優化算法全方位對比得出：本文算法是可行有效的，在解決TSP問題時收斂速度明顯提高，而大規模TSP問題質量更優。下一步將深入研究蟻群算法多種群之間的交流，進一步優化大規模TSP問題解的質量和收斂速度。