基于信息素初始分配和動態(tài)更新的蟻群算法

陳穎杰，高茂庭

上海海事大學(xué) 信息工程學(xué)院，上海 201306

蟻群算法由意大利學(xué)者Dorigo等[1]于1991年提出，是一種啟發(fā)式的隨機(jī)搜索算法，常用于組合優(yōu)化問題求解，具有分布式計算、無中心控制、易于與其他算法融合的優(yōu)點[2]。在求解TSP問題、車輛調(diào)度問題、車輛路徑問題、分配問題、網(wǎng)絡(luò)路由問題、蛋白質(zhì)折疊問題、數(shù)據(jù)挖掘以及圖像識別等方面都有較好的效果[3-5]。

然而，蟻群算法也存在不足，限制其發(fā)展[6]。蟻群算法作為一種正反饋算法，在搜索前期，由于信息素積累缺乏，螞蟻盲目搜索，導(dǎo)致算法搜索時間較長，收斂速度緩慢；在搜索后期，隨著某些路徑信息素的不斷積累，螞蟻傾向于選擇信息素濃度高的路徑[7]，從而使算法易于進(jìn)入停滯，陷入局部最優(yōu)。

針對蟻群算法的上述局限性，許多學(xué)者對蟻群算法進(jìn)行了多方面的改進(jìn)。文獻(xiàn)[8]在信息素初始化上利用節(jié)點間距離的大小對節(jié)點間的初始信息素進(jìn)行不同分配，距離越小，分配的信息素就越多，這種初始信息素分配方式讓算法在前期避免了盲目搜索，加快了搜索速度；然而，距離較小的路徑不一定都落在全局最優(yōu)路徑上，如果給其分配信息素較多，就會導(dǎo)致算法在前期搜索中快速地陷入局部最優(yōu)。文獻(xiàn)[9]改進(jìn)信息素?fù)]發(fā)因子，用時變函數(shù)代替信息素更新公式中的不變參數(shù)，在迭代前期，揮發(fā)因子為一個較小值，達(dá)到限定迭代次數(shù)后，將它修改為較大值，從而更大可能跳出局部最優(yōu)，然而，將揮發(fā)因子改大后，路徑上的信息素會被大量揮發(fā)掉，較優(yōu)路徑上的信息素濃度不再比其他路徑上的明顯多，使得收斂速度降低。文獻(xiàn)[10]改進(jìn)信息素增量更新方法，在增量公式中加入自適應(yīng)調(diào)節(jié)因子，通過已有解來動態(tài)改變信息素增量，在保證螞蟻能夠找到最優(yōu)解的同時，加快區(qū)分較優(yōu)路徑和其他路徑，提高算法的尋優(yōu)能力和收斂速度，同時，利用回滾策略，使算法更容易跳出局部最優(yōu)，然而，信息素回滾也可能導(dǎo)致出現(xiàn)算法繼續(xù)重復(fù)之前操作而陷入局部最優(yōu)的情況。

針對算法前期收斂速度慢的問題，提出一種改進(jìn)蟻群算法，在信息素初始化階段，采用貪心策略構(gòu)造一條次優(yōu)路徑并增加該路徑上的信息素濃度，使信息素在搜索前期就能發(fā)揮指導(dǎo)性作用，讓螞蟻更快地趨向于最優(yōu)解的附近；在信息素更新階段，在文獻(xiàn)[10]的基礎(chǔ)上，修改信息素增量公式，引入對數(shù)函數(shù)，使信息素增量在前期保持較大值，而在后期也不會因為迭代次數(shù)多而變得過小，以加快算法收斂速度。針對算法易于陷入局部最優(yōu)的問題，引入遺傳算法[11]中的變異操作，對當(dāng)前最優(yōu)路徑進(jìn)行變異操作，試圖找出一條更優(yōu)的路徑，并用找到的更優(yōu)路徑自適應(yīng)調(diào)整信息素增量，讓算法具備逃出局部最優(yōu)的可能；并且重新調(diào)整揮發(fā)因子[9]，在信息素進(jìn)行回滾的同時，修改揮發(fā)因子，算法回滾次數(shù)越多，使其值越大，以逐漸加強(qiáng)算法跳出局部最優(yōu)的能力。

1蟻群算法的基本原理及算法流程

蟻群算法是一種模擬螞蟻覓食行為的群體智能優(yōu)化算法[12]。螞蟻在尋找食物的途中，會在經(jīng)過的路徑上留下一種用于團(tuán)隊進(jìn)行交流的信息素。路徑上信息素的多少與該路徑的長度成反比，即該路徑越長，螞蟻留下的信息素越少；反之，該路徑越短，螞蟻留下的信息素越多。螞蟻在經(jīng)過路口選擇下一條路徑時，根據(jù)可選路徑的信息素濃度，選擇信息素濃度較高的路徑。隨著大量螞蟻的不斷搜索，最優(yōu)路徑的信息素濃度會越來越高，最后，整個蟻群會發(fā)現(xiàn)一條最優(yōu)的尋食路徑。

蟻群算法最典型的應(yīng)用就是求解TSP問題，接下來以TSP問題為例來描述蟻群算法的求解流程。

假設(shè)有m只螞蟻在n座城市之間來回移動，試圖尋找一條經(jīng)過所有城市的最短路徑。初始階段，為任意兩座城市i和j之間的路徑分配相同的信息素τij(t)=τ0（τ0為常數(shù)）；同時隨機(jī)將m只螞蟻分布在n座城市里，并且為每只螞蟻設(shè)置一個禁忌向量，用來保存該螞蟻已經(jīng)走過的城市。搜索階段，螞蟻k(k=1,2,…,m)開始進(jìn)行移動，在t時刻，通過選擇概率公式求出螞蟻k從城市i前往城市j的概率，如式（1）：

式（1）中，allowedk表示螞蟻k未經(jīng)過的城市集合，即螞蟻k前往下一個城市的可選城市集合；表示t時刻城市i和城市j之間的信息素濃度；α為信息素啟發(fā)因子，表示信息素濃度的相關(guān)重要性；ηij為啟發(fā)函數(shù)，表示可見度，其值等于城市i和城市j之間距離的倒數(shù)；β為期望啟發(fā)式因子，表示期望值的相關(guān)重要性。

在所有螞蟻對全部城市進(jìn)行一次游歷后，對路徑上遺留的信息素進(jìn)行更新，信息素更新包括兩部分：信息素?fù)]發(fā)和信息素增強(qiáng)。信息素?fù)]發(fā)是指信息素會隨著時間的推移而減少一部分，其目的在于避免信息素過多而掩蓋啟發(fā)信息，同時也可以避免過快集中于局部解；信息素增強(qiáng)是指增加螞蟻經(jīng)過路徑上的信息素，其目的在于強(qiáng)化次優(yōu)路徑，讓螞蟻更趨向于最優(yōu)解的附近，加快尋找最優(yōu)路徑的速度。由此，t+n時刻對路徑(i,j)按照式（3）和式（4）進(jìn)行信息素更新。

式（3）和式（4）中，ρ為揮發(fā)因子，表示信息素的揮發(fā)程度；Δτij(t)為信息增量，表示t時刻路徑(i,j)上增加的信息素；表示t時刻螞蟻k在路徑(i,j)上留下的信息素，的計算依模型的不同而有所不同。在基本蟻群算法中，比較常用的模型是蟻周模型（Ant-Cycle模型），如式（5）：

式（5）中，Q為信息素強(qiáng)度；Dk表示螞蟻k在t時刻所走路徑的總長度。

經(jīng)過若干次的迭代，若達(dá)到最大迭代次數(shù)，則結(jié)束搜索，輸出當(dāng)前最優(yōu)解。

2 改進(jìn)蟻群算法

蟻群算法是一種正反饋和啟發(fā)式的進(jìn)化算法[13]。針對算法前期收斂速度慢的問題，在信息素初始化階段，通過貪心策略從初始城市出發(fā)，依次在可選城市中選取距離最短的城市作為下一個前往的城市，最后找出一條次優(yōu)的路徑，增加該路徑上的信息素，從而使蟻群在搜索前期更快地聚攏到最優(yōu)路徑的附近；并采用一種自適應(yīng)的信息素增量公式，通過已有的解來動態(tài)調(diào)整信息素增量，加快算法的收斂速度和搜索能力。針對算法易于陷入局部最優(yōu)的問題，在每次迭代完成后，通過變異操作，交換兩個隨機(jī)城市之間的所有途徑城市，嘗試尋找一條更優(yōu)的路徑，并用找到的更優(yōu)路徑自適應(yīng)調(diào)整信息素增量，使算法出現(xiàn)跳出局部最優(yōu)的機(jī)會；另外，當(dāng)算法不可避免地陷入局部最優(yōu)時，采取信息素回滾策略，把信息素值恢復(fù)為陷入局部最優(yōu)前的值，并記錄當(dāng)前回滾次數(shù)，根據(jù)回滾次數(shù)動態(tài)調(diào)整揮發(fā)因子，回滾次數(shù)越多，揮發(fā)因子越大，信息素的揮發(fā)量越大，使少部分螞蟻有機(jī)會前往其他路徑，加強(qiáng)算法跳出局部最優(yōu)的能力。改進(jìn)后的蟻群算法流程如圖1所示。

圖1 改進(jìn)蟻群算法流程Fig.1 Flow of improved ant colony algorithm

為了更詳細(xì)地介紹改進(jìn)后的蟻群算法，在下文中分別對算法流程中的信息素初始化、遺傳變異操作和信息素更新策略進(jìn)行詳細(xì)介紹。

2.1 信息素初始化

在基本蟻群算法中，每條路徑上的初始信息素濃度都進(jìn)行相同的分配[14]。從式（1）可以看出，在信息素濃度相同的情況下，螞蟻下一城市的選擇主要取決于啟發(fā)式函數(shù)的大小，另一方面，信息素需要累積到一定程度才能發(fā)揮作用，而在初期階段卻無法發(fā)揮指導(dǎo)作用。因此，在初期階段很難快速搜索出一條較優(yōu)的路徑，甚至?xí)霈F(xiàn)螞蟻朝固定方向移動，形成局部最優(yōu)[15]。為了讓螞蟻在初期能夠更快地聚攏到最優(yōu)路徑，避免盲目搜索，提出一種新的初始信息素分配方式。在初始化階段，通過貪心策略從隨機(jī)初始城市出發(fā)，依次在可選的城市集合中，選取距離最短的城市作為螞蟻前往的下一城市，直到最后搜索出一條完整次優(yōu)路徑，并且將該路徑與其他路徑進(jìn)行不同的初始信息素分配，如式（6）：

式（6）中，τ0為信息素初始值（所有路徑都分配相同值）；add為額外增加的信息素值。通過貪心策略為路徑進(jìn)行初始化后，在搜索前期，信息素也能發(fā)揮指導(dǎo)作用，提高全局尋優(yōu)能力，并加快算法的收斂速度。

2.2 變異操作

由于基本蟻群算法自身的局限性，在螞蟻搜索路徑期間，不可避免地出現(xiàn)停滯現(xiàn)象，形成局部最優(yōu)。為了實現(xiàn)解的多樣性，避免過早地收斂，陷入局部最優(yōu)的情況[16]，引入遺傳算法中的變異操作。在每次迭代完成后，對當(dāng)前迭代中的最優(yōu)路徑執(zhí)行變異操作，如果變異后的路徑比變異前的要更好，則用變異后的路徑進(jìn)行后續(xù)的信息素增量更新；反之，則繼續(xù)用變異前的路徑進(jìn)行后續(xù)的信息素增量更新。變異操作的過程如圖2所示，從路徑中隨機(jī)選取兩個不同的節(jié)點，對兩個節(jié)點之間的節(jié)點進(jìn)行交換操作，最后得到變異后的路徑。

圖2 變異過程Fig.2 Variation process

在搜索期間，很容易出現(xiàn)某次迭代最優(yōu)路徑的部分路徑是局部最優(yōu)路徑，而不是全局最優(yōu)路徑。如圖3中，城市B距離城市C較近，距離城市E較遠(yuǎn)，在搜索前期，螞蟻會優(yōu)先選擇路徑BC，隨著路徑BC上的信息素慢慢積累起來，后續(xù)螞蟻都會選擇路徑BC而不是路徑BE，從而形成局部最優(yōu)，搜索時間加長。

圖3 局部最優(yōu)路徑的一段Fig.3 A segment of local optimal path

如果加入變異操作后，算法就有機(jī)會找到圖4所示的全局最優(yōu)路徑（部分），從而使蟻群慢慢地從圖3的路徑聚攏到圖4的路徑，跳出局部最優(yōu)的狀態(tài)。

圖4 全局最優(yōu)路徑的一段Fig.4 A segment of global optimal path

2.3 信息素動態(tài)更新

為了更好地加快收斂速度，縮短收斂時間，對信息素增量公式進(jìn)行改進(jìn)，加入自適應(yīng)調(diào)節(jié)因子，利用已有的解來動態(tài)調(diào)節(jié)信息素增量，如式（7）：

式（7）中，b為一個可變參數(shù)，用來調(diào)節(jié)初始信息素增量的大小；N為當(dāng)前的迭代次數(shù)；Dbest為當(dāng)前最優(yōu)路徑長度，執(zhí)行變異操作后，如果變異后的路徑長度比當(dāng)前最優(yōu)路徑短，則Dbest為變異后的路徑長度，否則，Dbest為當(dāng)次迭代的最優(yōu)路徑長度。在新的信息素增量公式中加入迭代次數(shù)N參數(shù)，通過N來自適應(yīng)調(diào)節(jié)信息素增量。

從圖5可以看出，相比于文獻(xiàn)[10]采用的倒數(shù)函數(shù)y=1/x，在x較小時，對數(shù)函數(shù)y=1/lgx的值相對要大得多，因此，式（7）中采用對數(shù)函數(shù)，能在迭代次數(shù)N較小時，信息素增量保持在更大的值，從而使蟻群更快地聚攏到最優(yōu)解的附近，加快初期算法的收斂速度；還不會因為迭代次數(shù)的增多，而快速減小信息素增量，使得在搜索后期，也能保持在較快的收斂速度；同時，為了避免在搜索前期，信息素增量過大而導(dǎo)致算法過早收斂，陷入局部最優(yōu)的情況，式（7）中還加入?yún)?shù)b，通過修改參數(shù)b的大小來調(diào)整初始信息素增量的大小。在式（7）還加入反余切函數(shù)，通過對比當(dāng)前已尋路徑和上一次迭代過程中的最優(yōu)解或者通過變異得到的更優(yōu)解之間的距離差來對信息素增量做出調(diào)整。反余切函數(shù)是一個有臨界值的函數(shù)，當(dāng)已尋路徑和最優(yōu)解相差太大時，也能通過臨界值控制結(jié)果的最大值和最小值，不會出現(xiàn)信息素過大或者過小的現(xiàn)象。

圖5 自適應(yīng)變化曲線對比Fig.5 Comparison of adaptive change curves

由于蟻群算法的正反饋特性，采用式（7）的信息素增量公式，能加快算法的收斂速度，在搜索的前期，有利于算法搜索到較好的解，但隨著迭代的增加，某些路徑上的信息素積累過多，導(dǎo)致算法易于進(jìn)入停滯[9]，陷入局部最優(yōu)。為了使算法在陷入局部最優(yōu)的時候，具備跳出局部最優(yōu)的能力，改進(jìn)算法還采用信息素回滾和動態(tài)調(diào)整信息素?fù)]發(fā)因子的策略。

信息素回滾是當(dāng)算法陷入局部最優(yōu)時，將路徑上的信息素值改回到陷入局部最優(yōu)前的值，從而讓算法具備跳出局部最優(yōu)的能力。設(shè)閾值R，如果連續(xù)R次迭代得到的最優(yōu)結(jié)果沒有發(fā)生變化，說明算法大概率陷入局部最優(yōu)的情況，此時將路徑上的信息素值回滾到R次迭代前的信息素值，并且回滾次數(shù)c加1。

信息素的更新是為了能夠更好地利用蟻群算法的正反饋功能，同時又避免由于正反饋可能導(dǎo)致的停滯現(xiàn)象，提高算法的尋優(yōu)搜索能力。為了避免次優(yōu)路徑上的信息素積累過快，更好地避免陷入局部最優(yōu)，在對原路徑上信息素?fù)]發(fā)的基礎(chǔ)上，對螞蟻留下的信息素增量也進(jìn)行一部分的揮發(fā)，將公式（3）改成公式（8）：

式（8）中，對ρ的取值作改進(jìn)，使其不再是一個常數(shù)，而是隨著回滾次數(shù)c的增加而增加。通過增加ρ的值，揮發(fā)掉更多次優(yōu)路徑的信息素，來達(dá)到螞蟻能前往其他路徑的目的，跳出局部最優(yōu)。同時，為了避免最后信息素全部揮發(fā)掉，設(shè)閾值ρmax，在每次發(fā)生信息素回滾時，利用式（9）修改揮發(fā)因子ρ的值。

式（9）中，ρ0為揮發(fā)因子的初值；ρa(bǔ)dd為每次回滾揮發(fā)因子的增加量。

2.4 改進(jìn)后蟻群算法的詳細(xì)流程

通過貪心策略實現(xiàn)初始信息素重新分配，然后對每次迭代后的最優(yōu)解進(jìn)行變異操作，最后對路徑進(jìn)行全局信息素動態(tài)更新，嘗試跳出局部最優(yōu)，提高算法的尋優(yōu)能力和收斂速度，基于信息素初始分配和動態(tài)更新的蟻群算法步驟如下：

步驟1根據(jù)TSP問題定義數(shù)組，為最大迭代次數(shù)N和限定值R賦初值，并初始化螞蟻數(shù)m、城市數(shù)n、信息素初始值τ0和參數(shù)α、β、ρ0、Q等。

步驟2通過貪心策略搜索出次優(yōu)路徑，并對該路徑上的信息素進(jìn)行初始分配，即τ0+add。

步驟3為每只螞蟻隨機(jī)選擇一個起始城市，并從該起始城市開始搜索。

步驟4根據(jù)式（1）和式（2），為螞蟻k計算下一個到達(dá)城市j的概率，利用輪盤賭算法，依次選出螞蟻k的下一個城市，最后求得一條完整的路徑。

步驟5計算并比較各個螞蟻所走路徑的長度，找出當(dāng)前最優(yōu)路徑，記最優(yōu)路徑的長度為D1。

步驟6對當(dāng)前最優(yōu)路徑進(jìn)行變異操作，計算變異路徑的長度D2。

步驟7比較當(dāng)前最優(yōu)路徑長度D1和變異路徑長度D2，依據(jù)兩者中的更短長度Dbest按式（7）和式（8）對路徑上的信息素進(jìn)行全局更新。

步驟8若連續(xù)R次迭代的最優(yōu)路徑結(jié)果沒有發(fā)生變化，則將路徑上信息素值回滾到R次迭代前的值，回滾次數(shù)c加1，并根據(jù)式（9）修改揮發(fā)因子的值。

步驟9若當(dāng)前迭代次數(shù)未達(dá)到預(yù)設(shè)最大迭代次數(shù)N，則迭代次數(shù)加1，清空搜索禁忌表，并跳轉(zhuǎn)到步驟3，否則，輸出最優(yōu)路徑，算法結(jié)束。

3 仿真實驗及分析

為了驗證和分析本文算法的有效性，分別使用標(biāo)準(zhǔn)測試函數(shù)和TSPLIB測試庫中的實例[17]進(jìn)行仿真實驗。將本文算法分別與遺傳算法、粒子群算法，以及其他改進(jìn)蟻群算法進(jìn)行比較。

考慮到實驗可能存在的隨機(jī)性，為避免由此造成的誤差，每個算法都運(yùn)行25次，取多次結(jié)果的平均值作為最終實驗結(jié)果進(jìn)行對比。

3.1 標(biāo)準(zhǔn)測試函數(shù)仿真測試

選取8個典型的標(biāo)準(zhǔn)測試函數(shù)對算法進(jìn)行仿真測試，其中，Sphere、Schwefel、De Jong、Schaffer為單峰函數(shù)，用來測試算法的收斂速度并檢驗算法的局部搜索能力；Alpine、Ackley、Griewank、Rastrigrin函數(shù)是多峰函數(shù)，用來測試算法的全局搜索能力，從而檢驗算法的綜合能力[18]。將本文算法與遺傳算法、粒子群算法進(jìn)行比較，仿真測試中，維度為10，迭代次數(shù)為1 000，平均25次運(yùn)行結(jié)果，求得最優(yōu)值的最小值和平均值如表1所示。

從表1可以看出，無論是單峰還是多峰函數(shù)，本文算法求得最優(yōu)值的最小值都比遺傳算法、粒子群算法求得最優(yōu)值的最小值小，說明本文算法在求解精度上比遺傳算法、粒子群算法更強(qiáng)；同時可以看出，本文算法求得最優(yōu)值的平均值都優(yōu)于遺傳算法、粒子群算法，即本文算法比遺傳算法、粒子群算法尋優(yōu)效果都有很明顯的提高，得到的最優(yōu)值離實際最優(yōu)值更加接近，說明改進(jìn)蟻群算法較遺傳算法、粒子群算法展現(xiàn)出更強(qiáng)的全局和局部搜索能力，具有更佳的性能。

表1 標(biāo)準(zhǔn)測試函數(shù)實驗結(jié)果（最小值/平均值）Table 1 Experimental results on standard testing function（minimum/average）

3.2 TSPLIB測試庫實驗

為了檢驗算法的有效性和泛化性，從TSPLIB測試庫中選取較小規(guī)模（Eil51、Att48）、中等規(guī)模（Eil76）和較大規(guī)模（Eil101、Rat99）共五個實例進(jìn)行對比實驗。將本文算法與基本蟻群算法、僅加入信息素初始分配和新信息素增量公式改進(jìn)策略的蟻群算法（簡稱為改進(jìn)算法一）、僅加入變異操作和信息素動態(tài)更新的蟻群算法（簡稱為改進(jìn)算法二）、文獻(xiàn)[8]算法、文獻(xiàn)[10]算法進(jìn)行比較。通過對比，本文算法與基本蟻群算法、改進(jìn)算法一、改進(jìn)算法二的結(jié)果，分析本文算法每步改進(jìn)策略在算法中發(fā)揮的作用；再通過對比本文算法與基本蟻群算法、文獻(xiàn)[8]算法、文獻(xiàn)[10]算法結(jié)果，分析本文算法相較于其他改進(jìn)算法的優(yōu)劣性。在進(jìn)行對比實驗前，通過多次預(yù)實驗，確定較優(yōu)的參數(shù)值如下：

多次仿真實驗的最短路徑的最優(yōu)值與平均值，以及迭代次數(shù)的平均值結(jié)果如表2所示。

首先，對比本文算法與基本蟻群算法、改進(jìn)算法一、改進(jìn)算法二的結(jié)果，分析本文算法每步改進(jìn)策略發(fā)揮的作用。對比表2中最短路徑最優(yōu)值和平均值可以看出，三種改進(jìn)算法求得的結(jié)果比基本蟻群算法的結(jié)果明顯都更接近實際最優(yōu)值，且改進(jìn)算法二與本文算法的結(jié)果相近，均優(yōu)于改進(jìn)算法一的結(jié)果，說明改進(jìn)算法二采用的變異操作和信息素動態(tài)更新策略是提高全局尋優(yōu)能力和跳出局部最優(yōu)能力的重要手段。對比表2中求得最短路徑的平均迭代次數(shù)可以看出，從小到大依次是：本文算法、改進(jìn)算法一、改進(jìn)算法二和基本蟻群算法，且四者結(jié)果都有明顯的差別，說明信息素初始分配和新信息素增量公式改進(jìn)策略、變異操作和信息素動態(tài)更新策略都能提高收斂速度，但信息素初始分配和新信息素增量公式改進(jìn)策略發(fā)揮主要作用。

表2 TSPLIB測試庫上六種算法的實驗結(jié)果（最優(yōu)長度/平均長度/次數(shù)）Table 2 Experimental results of six algorithms on TSPLIB datasets（optimal length/average length/times）

然后，再對比分析本文算法與其他改進(jìn)算法的優(yōu)劣。對比表2中最短路徑最優(yōu)值和平均值可以看出，隨著TSP問題規(guī)模逐漸變大，所有算法求得最短路徑的最優(yōu)值與最優(yōu)解的差別也逐漸變大，說明隨著TSP問題規(guī)模的增大，算法的求解精度降低；本文算法在不同規(guī)模下求得最短路徑的最優(yōu)值和平均值都稍優(yōu)于基本蟻群算法、文獻(xiàn)[8]算法和文獻(xiàn)[10]算法求得的結(jié)果，而且本文算法求得最短路徑的最優(yōu)值雖然受到規(guī)模大小的影響，但是仍然保持較好的精度，說明本文算法所采用的變異操作和信息素動態(tài)更新策略讓算法在陷入局部最優(yōu)的時候更容易跳出局部最優(yōu)，從而在全局搜索能力和最優(yōu)解的精度方面有一定的提升。對比表2中求得最短路徑所需的平均迭代次數(shù)可以看出，TSP問題規(guī)模的大小對算法的迭代次數(shù)影響較大，一般情況下，規(guī)模越大，算法求得最短路徑所需的迭代次數(shù)越多；本文算法在不同規(guī)模下求得最短路徑所需迭代次數(shù)遠(yuǎn)遠(yuǎn)小于基本蟻群算法、文獻(xiàn)[8]算法和文獻(xiàn)[10]算法，特別是大規(guī)模的情況下，本文算法求得最短路徑所需的迭代次數(shù)仍然保持在一個較小值，說明本文算法對信息素進(jìn)行初始分配和新信息素增量公式改進(jìn)策略使算法在確保求得最短路徑較優(yōu)的前提下，收斂速度得到大大提升。本文算法與基本蟻群算法、文獻(xiàn)[8]算法、文獻(xiàn)[10]算法在求解Eil51實例時的收斂過程對比如圖6所示。

從圖6可以很直觀地看出，本文算法在搜索初期比三種對比算法更快地找到次優(yōu)解，具有較好的尋優(yōu)能力和收斂速度；同時，在陷入局部最優(yōu)的時候，本文算法也比對比算法更快地跳出局部最優(yōu)；最后求得的最短路徑也比其他三種算法更優(yōu)，因此，本文算法在求得最短路徑的精度、收斂速度和跳出局部最優(yōu)能力上都優(yōu)于三種對比算法。

圖6 收斂過程對比Fig.6 Comparison of convergence process

實驗還記錄了本文算法與對比算法在多種迭代次數(shù)所需運(yùn)行時間，結(jié)果如表3所示。

表3 四種算法的運(yùn)行時間Table 3 Running time of four algorithms

雖然在全局搜索能力和收斂方面都比基本蟻群算法要更好，但是從表3可以看出，文獻(xiàn)[8]算法和文獻(xiàn)[10]算法的運(yùn)行時間比基本蟻群算法要長得多，而本文算法與基本蟻群算法基本相當(dāng)，稍長一點，本文算法在運(yùn)行時間性能上明顯比文獻(xiàn)[8]算法和文獻(xiàn)[10]算法好得多。

綜上所述，相比于基本蟻群算法、文獻(xiàn)[8]算法與文獻(xiàn)[10]算法，本文算法在求得最短路徑的最優(yōu)值和平均值上都有小幅的提升，而在求得最短路徑所需的平均迭代次數(shù)上，本文算法遠(yuǎn)優(yōu)于三種對比算法。而在時間性能上，本文算法運(yùn)行時間僅稍長于基本蟻群算法，遠(yuǎn)優(yōu)于文獻(xiàn)[8]算法和文獻(xiàn)[10]算法。

4 結(jié)論

本文對蟻群算法進(jìn)行改進(jìn)，利用貪心策略搜索出次優(yōu)路徑，并對該路徑信息素進(jìn)行初始分配；同時，引入遺傳變異操作，對每次迭代后的最優(yōu)路徑進(jìn)行變異操作，試圖找到更優(yōu)的路徑，利用更優(yōu)路徑對信息素增量進(jìn)行動態(tài)更新；當(dāng)算法陷入局部最優(yōu)時，采用信息素回滾和信息素?fù)]發(fā)因子動態(tài)更新的方式，使大部分螞蟻更快地靠攏最優(yōu)路徑的同時，讓少部分螞蟻跳出次優(yōu)路徑，擴(kuò)大了搜索范圍，尋找更優(yōu)路徑。