潘 晗，游曉明，劉 升

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

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

1 引言

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

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

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

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

2 相關(guān)工作

2.1 ACS 蟻群算法原理

2.1.1 路徑構(gòu)建

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

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

式中，α、β分別表示信息素和啟發(fā)因子在概率計(jì)算中所占的權(quán)重。

2.1.2 信息素的更新

（1）全局信息素更新

針對當(dāng)前最好路徑上的邊進(jìn)行信息素更新，更新的規(guī)則如式（3）所示：

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

（2）局部信息素更新

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

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

2.2 MMAS 蟻群算法

為了使得算法在最短路徑附近搜索，從而逐步找到全局最優(yōu)解，算法只會對當(dāng)前循環(huán)中所產(chǎn)生的最短路徑進(jìn)行信息素的更新操作，如式（5）所示：

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

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

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

其中，pbest是MMAS 算法收斂時(shí)找到最優(yōu)解的概率（一般為0.05）。

2.3 最大最小生成樹

最大最小生成樹的概念被提出于數(shù)據(jù)結(jié)構(gòu)中，它們都是樹形結(jié)構(gòu)。后來很多專家學(xué)者對最大最小生成樹算法進(jìn)行了改進(jìn)與應(yīng)用[21-22]。

2.3.1 最大最小生成樹的定義

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

2.3.2 最大最小生成樹的構(gòu)建

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

（1）Kruskal算法主要思想

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

（2）Prim 算法主要思想

給定連通圖G和任意根節(jié)點(diǎn)r，最小生成樹從節(jié)點(diǎn)r開始，一直長大到覆蓋V中所有節(jié)點(diǎn)為止，即不斷尋找輕量級邊以實(shí)現(xiàn)最小權(quán)重和。

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

3.1 動態(tài)導(dǎo)向策略

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

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

3.1.1 最大生成樹策略

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

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

3.1.2 最小生成樹策略

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

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

3.2 鄰域交互策略

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

3.2.1 吸引因子

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

每個(gè)以i為圓心的鄰域內(nèi)路徑上由第二類螞蟻釋放的信息素的總和是一定的，當(dāng)?shù)谝活愇浵佋?i,j)城市之間的路徑上所釋放的信息素越大時(shí)，所求的吸引因子的值越大，說明第二類螞蟻就會以更高的概率選擇第一類螞蟻集中選擇過的路徑，使得第二類螞蟻選擇城市更具有導(dǎo)向性。

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

首先將吸引因子引入到狀態(tài)轉(zhuǎn)移規(guī)則中，如3.2.3 小節(jié)的敘述，在綜合考慮了第二類螞蟻?zhàn)陨硐嚓P(guān)啟發(fā)信息的同時(shí)，還結(jié)合了第一類螞蟻的信息素啟發(fā)信息，使得第二類螞蟻選擇路徑時(shí)會受到第一類螞蟻留下的信息素啟發(fā)信息的影響，且第一類螞蟻遍歷城市時(shí)所選擇的較優(yōu)路徑在對第二類螞蟻選擇路徑時(shí)有更大的影響，體現(xiàn)了第一類螞蟻的信息素啟發(fā)信息對第二類螞蟻的正反饋?zhàn)饔?，即吸引因子的正反饋?zhàn)饔?。由于正反饋的作用，使得那些較優(yōu)路徑上的信息素累積比一般路徑上要快且多，因此算法的收斂速度會加快，并且收斂精度也會提高。

其次將吸引因子引入到局部信息素更新策略中，如3.2.4 小節(jié)的敘述，讓每條路徑的信息素?fù)]發(fā)量相應(yīng)地減少，不僅起到了正反饋?zhàn)饔?，同時(shí)也抑制了多樣性，使得算法的收斂能力得到加強(qiáng)。

綜合而言，吸引因子對算法起到了正反饋?zhàn)饔?，同時(shí)加快了算法的收斂速度，提高了算法的收斂精度。

3.2.2 關(guān)聯(lián)鄰域

為了能夠高效地結(jié)合有效信息素，并且在一定程度上減少每次計(jì)算吸引因子的速度，提出了關(guān)聯(lián)鄰域的概念，經(jīng)過多次實(shí)驗(yàn)結(jié)果分析得出關(guān)聯(lián)鄰域的定義如下：

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

其中，m表示總的城市個(gè)數(shù)，lim表示第i個(gè)城市到第m個(gè)城市的距離。

由于本文所選TSP 城市數(shù)目較多且分布比較緊密，同時(shí)半徑r的選擇相對較大，半徑外的城市距離中心點(diǎn)相對較遠(yuǎn)，因此在計(jì)算吸引因子時(shí)，即使關(guān)聯(lián)鄰域計(jì)算了半徑外的城市，最終也不會選擇其作為下一個(gè)經(jīng)過的城市。故關(guān)聯(lián)鄰域能夠高效地結(jié)合有效信息素，使得減少程序的運(yùn)行時(shí)間。

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

在第一類螞蟻使用原始ACS 狀態(tài)轉(zhuǎn)移概率公式的基礎(chǔ)上，第二類螞蟻運(yùn)用了改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則，引入了吸引因子。使得第二類螞蟻不僅考慮了自身的信息素啟發(fā)信息和距離啟發(fā)信息，還結(jié)合了與第一類螞蟻所釋放信息素的有關(guān)的信息，即吸引因子。綜合了種群內(nèi)的信息和種群間的信息，使得第二類螞蟻在遍歷城市的時(shí)候更加容易尋得高質(zhì)量的解。引入吸引因子的第二類螞蟻的改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則如式（13）、式（14）所示：

由于在第i個(gè)城市選擇下一個(gè)城市j時(shí)，i是固定不變的，因此(i,j)城市之間路徑上的信息素濃度決定了吸引因子的大小。式（13）、式（14）中結(jié)合了吸引因子，使得第二類螞蟻在選擇下一城市時(shí)，更偏向于第一類螞蟻選擇過的較優(yōu)路徑，體現(xiàn)出了吸引因子的正反饋?zhàn)饔谩Ｎ蜃蛹訌?qiáng)了兩個(gè)種群之間的交流，使得第二類螞蟻遍歷城市的時(shí)候更具有方向性，加快了算法的收斂速度。

3.2.4 改進(jìn)的局部信息素更新策略

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

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

3.3 算法流程圖

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

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

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

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

3.5 算法收斂能力分析

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

下文以實(shí)驗(yàn)形式對算法的綜合收斂能力進(jìn)行了分析，結(jié)果表明收斂速度和收斂精度都有所提高。綜合而言，TREEACS 算法的綜合收斂能力優(yōu)于傳統(tǒng)的蟻群算法和一些其他改進(jìn)蟻群算法。

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

為了檢驗(yàn)改進(jìn)后算法的有效性，本文使用Matlab2017a 對TSPLIB 標(biāo)準(zhǔn)庫中的十幾個(gè)不同規(guī)模的城市進(jìn)行了模擬仿真，并且與ACS、MMAS 進(jìn)行比較，為了進(jìn)一步檢驗(yàn)本文算法的性能，又與其他兩種改進(jìn)的蟻群算法進(jìn)行比較。

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

為了有效地驗(yàn)證TREEACS 的性能，本文實(shí)驗(yàn)中在TSPLIB 標(biāo)準(zhǔn)庫中選取若干城市進(jìn)行系統(tǒng)性的分析，同時(shí)還與經(jīng)典的ACS、MMAS 算法進(jìn)行綜合比較，分析改進(jìn)算法性能的優(yōu)劣。

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 仿真實(shí)驗(yàn)數(shù)據(jù)

由圖2 和表1 可知，運(yùn)用本文算法TREEACS，城市數(shù)在中小規(guī)模以下的9 個(gè)測試集中100%的城市是可以得到標(biāo)準(zhǔn)最優(yōu)解的，城市數(shù)在大規(guī)模的測試集中，50%以上的城市誤差率在0.1%左右，并且無論是中小規(guī)?；虼笠?guī)模城市的最優(yōu)解，平均解和誤差率都明顯優(yōu)于ACS 和MMAS 算法。TREEACS 在結(jié)合最大生成樹的基礎(chǔ)上，還加入了MMAS 的信息素限定策略，不但使得算法的多樣性加強(qiáng)，還使得算法易于跳出局部最優(yōu)，從而找到更優(yōu)解。

4.2 TREEACS 最優(yōu)解與收斂性對比

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

Fig.3 Experimental comparison of TREEACS with ACS and MMAS圖3 TREEACS 與ACS、MMAS 實(shí)驗(yàn)對比

4.3 最大最小生成樹策略

4.3.1 最大生成樹多樣性對比

為了驗(yàn)證最大生成樹策略對于算法多樣性帶來的優(yōu)勢，本文分別選取小規(guī)模測試集eil51、中規(guī)模測試集kroB150、大規(guī)模測試集pr264 來進(jìn)行標(biāo)準(zhǔn)差斷點(diǎn)分析。圖4 表明，TREEACS 算法在三個(gè)測試集中的標(biāo)準(zhǔn)差斷點(diǎn)值都要比S-TREEACS（缺少最大生成樹策略的TREEACS）算法的標(biāo)準(zhǔn)差斷點(diǎn)值要大。這充分說明了加入最大生成樹策略明顯加強(qiáng)了算法的多樣性。

4.3.2 最小生成樹收斂性對比

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

4.4 吸引因子收斂性對比

為了驗(yàn)證吸引因子策略對于算法收斂性帶來的優(yōu)勢，本文分別選取小規(guī)模測試集eil51、中規(guī)模測試集kroB100、大規(guī)模測試集kroA200 來進(jìn)行分析。圖6 表明，TREEACS 算法的收斂速度明顯比NAFTREEACS（缺少吸引因子策略的TREEACS）算法的要快，且TREEACS 算法的收斂精度也明顯比NAFTREEACS 算法的要好。因?yàn)猷徲蚪换ゲ呗灾械奈蜃訉λ惴ㄆ鸬搅苏答佔(zhàn)饔?，使得不僅可以加快算法收斂速度，而且能夠提高收斂精度。

Fig.4 Comparison of standard deviation breakpoints between TREEACS and S-TREEACS圖4 TREEACS 與S-TREEACS 標(biāo)準(zhǔn)差斷點(diǎn)對比圖

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 與其他改進(jìn)算法的對比

4.5 與改進(jìn)蟻群算法及其他算法對比

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

根據(jù)表2 的實(shí)驗(yàn)結(jié)果可知，本文算法TREEACS無論是在中小規(guī)模還是大規(guī)模的TSP 問題中，解的精度明顯優(yōu)于改進(jìn)蟻群算法及其他算法。

5 結(jié)束語

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

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