馬世軒，游曉明，劉 升

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

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

旅行商問題（traveling salesman problem，TSP）有如下定義：假設(shè)有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。在本文中，假設(shè)計算兩個城市之間的距離的方式都使用歐氏距離，并假設(shè)所有城市坐標(biāo)都處于同一個平面之中。本文只討論對稱TSP問題，即從點i到點j的距離和從點j到點i的距離是相同的。

旅行商問題是生活中問題的抽象的重要的模型，其基本特點是易于描述，難于求解，是典型的NP 難（nondeterministic polynomial hard）問題。因此，對旅行商問題的研究具有重要意義。目前解決TSP 問題的方法主要有暴力窮舉法、貪心算法、分支定解算法、動態(tài)規(guī)劃算法、遺傳算法、蟻群算法、模擬退火算法、粒子群算法、Hopfield 神經(jīng)網(wǎng)絡(luò)算法等。近幾年不斷有新的更高效的智能優(yōu)化算法被提出：如張九龍等[1]對蝴蝶優(yōu)化算法（butterfly optimization algorithm，BOA）、飛蛾撲火算法（moth-flame optimization algorithm，MFO）、正弦余弦優(yōu)化算法（sine cosine algorithm，SCA）、蝗蟲優(yōu)化算法（grasshopper optimization algorithm，GOA）、哈里斯鷹優(yōu)化算法（Harris hawks optimizer，HHO）、麻雀搜索算法（sparrow search algorithm，SSA）進行了對比分析研究。也有相關(guān)文獻[2]和[3]等對智能算法的應(yīng)用做出了研究，研究表明蟻群算法有突出的表現(xiàn)。因此本文使用蟻群算法來研究TSP問題。

蟻群算法的提出：1991年，Dorigo[4]受到螞蟻覓食行為的啟發(fā)，提出了螞蟻系統(tǒng)（ant system，AS）并用于解決TSP 問題。AS 算法模擬自然界中螞蟻的交流方式，比如信息素的釋放與信息素的揮發(fā)。這兩種策略增強了AS 算法的正反饋性能，最優(yōu)解上會被釋放更多的信息素，同時其他解的路徑上信息素會隨著迭代次數(shù)的增加而緩慢揮發(fā)。由于螞蟻更傾向于信息素濃度高的路徑，故該路徑被選擇的概率也會增加，這種此消彼長的方式極大加快了算法收斂速度，提高算法收斂性；禁忌表的加入使螞蟻無法經(jīng)過已經(jīng)通過的城市，避免算法產(chǎn)生不必要的時間復(fù)雜度，提高算法在TSP 等NP 難問題中的求解效率[5]。1997年，Dorigo等[6]提出蟻群系統(tǒng)（ant colony system，ACS），將局部信息素更新與全局信息素更新相結(jié)合，隱性控制信息素上下限，改善算法的性能，對算法易陷入局部最優(yōu)的問題進行了改良。2000年，Stützle 等人在蟻群優(yōu)化算法（ant colony optimization，ACO）的基礎(chǔ)上提出MMAS（max-min ant system）[7]，是目前為止解決TSP和QAP（quadratic assignment problem）等組合優(yōu)化問題最好的一類ACO 算法[8]。上述傳統(tǒng)算法能有效解決小規(guī)模TSP問題，但是難以解決大規(guī)模問題。很多學(xué)者對傳統(tǒng)算法進行各種改進。

1999 年，Bullnheimer 等[9]所提出的等級螞蟻系統(tǒng)（rand based ant system，RAS）是精英策略的另一種應(yīng)用，在信息素更新環(huán)節(jié)中只使用了精英螞蟻[10]。張松燦等提出單種群自適應(yīng)異構(gòu)蟻群算法的機器人路徑規(guī)劃[11]和基于蟻群算法的移動機器人路徑規(guī)劃研究[12]。代婷婷等提出改進的蟻群算法在路徑規(guī)劃問題中的應(yīng)用[13]和蟻群算法的改進及其在最優(yōu)路徑中的應(yīng)用[14]。趙靜等[15]提出基于改進蟻群算法的移動機器人路徑規(guī)劃。顧軍華等[16]提出基于改進蟻群算法的多機器人路徑規(guī)劃研究。陳銀燕等[17]提出機器人導(dǎo)航路徑的多種群博弈蟻群規(guī)劃策略。李濤等[18]提出基于進化蟻群算法的移動機器人路徑優(yōu)化。孫宇翔等[19]提出基于精英策略的蟻群算法在AGV（automated guided vehicle）路徑優(yōu)化中的應(yīng)用。李維維等[20]提出柵格環(huán)境下機器人導(dǎo)航路徑的雙種群蟻群規(guī)劃。游曉明等[21]提出一種動態(tài)搜索策略的蟻群算法及其在機器人路徑規(guī)劃中的應(yīng)用。Karakostas 等[22]提出一種求解旅行商問題的雙自適應(yīng)廣義變量鄰域搜索算法（double-adaptive general variable neighborhood search，DA-GVNS）。朱宏偉等[5]提出基于動態(tài)反饋機制的雙種群蟻群算法的研究應(yīng)用（pearson correlation coefficient ant colony optimization，PCCACO）。陳佳等提出基于自適應(yīng)分級機制的多種群蟻群算法（EDHACO）[23]和結(jié)合信息熵的多種群博弈蟻群算法（WAS）[10]。馬飛宇等[24]提出基于異構(gòu)雙種群全局視野蟻群算法的移動機器人路徑規(guī)劃。

上述現(xiàn)代算法雖然性能有了改進，但是在解決大規(guī)模TSP 問題時，解的精度和收斂速度有待進一步提高。在近期研究中，常規(guī)蟻群算法存在運行效率低、算法停滯和易陷入局部最優(yōu)等不足，容易出現(xiàn)死鎖問題，收斂速度慢，效率較低，容易陷入局部最優(yōu)，運算時間過長，求解精度不高，難以解決大規(guī)模問題，為了提高多樣性和搜索效率和質(zhì)量，使得路徑更加平滑，針對這些問題，本文提出了動態(tài)信息素更新和路徑獎懲的蟻群算法。

本文的主要工作是針對蟻群算法容易陷入局部最優(yōu)，收斂速度慢，難以解決大規(guī)模問題的情況，在前人的研究基礎(chǔ)上，提出基于收斂系數(shù)的動態(tài)信息素更新策略和基于最優(yōu)路徑集合的獎懲策略的蟻群算法和三種局部優(yōu)化方法。依據(jù)信息熵和停滯次數(shù)的動態(tài)信息素的更新策略和基于最優(yōu)路徑集合的獎懲策略的蟻群算法，在動態(tài)信息素更新策略中，利用收斂系數(shù)來動態(tài)調(diào)節(jié)信息素，從而有效地平衡算法的多樣性和收斂性。在搜索過程中，通過持續(xù)提高收斂系數(shù)，加快了收斂速度；當(dāng)信息熵降低或者停滯次數(shù)達到一定數(shù)值時，通過降低收斂系數(shù)，從而跳出局部最優(yōu)；同時基于最優(yōu)路徑集合，對較優(yōu)路徑獎勵，對其他路徑懲罰，從而減少螞蟻每一步可選城市的數(shù)量，減少計算量，加快收斂速度。

1 相關(guān)工作

1.1 蟻群系統(tǒng)

為了解決AS 易于陷入局部最優(yōu)以及停滯的問題，Dorigo 等[6]在其基礎(chǔ)上又提出蟻群系統(tǒng)（ACS），它成為蟻群算法當(dāng)中改進效果最好的算法之一，給研究人員很大的啟迪，給整個蟻群算法帶來了深遠(yuǎn)的影響。

1.1.1 啟發(fā)式信息

設(shè)啟發(fā)式信息為η(i,j)，d(i,j)為兩個城市i和j之間的歐氏距離，則η(i,j)如式（1）所示：

1.1.2 路徑構(gòu)造函數(shù)

在AS中，結(jié)合啟發(fā)式信息，Dorigo將信息素因子與啟發(fā)式信息結(jié)合，引入到城市的選擇環(huán)節(jié)中，如式（2）所示：

式中，Pij表示城市i到城市j的轉(zhuǎn)移概率，τij代表了從城市i到城市j的信息素濃度，ηij則是城市之間的啟發(fā)式信息，allowedk是螞蟻在城市i時可供選擇的城市集（在TSP問題中，城市只可被訪問一次，allowedk為還沒有被訪問的城市）。α和β分別指代信息素和啟發(fā)式的影響程度。

在ACS中，通過式（3）進行路徑構(gòu)建：

式中，s代表將要被選擇的下一城市，S表示通過AS算法中式（2）的方式進行解的構(gòu)建，q是由算法隨機生成的數(shù)，q0是一個定常數(shù)，且q0∈[0,1],allowedk代表可選的城市集，即還沒有被經(jīng)過的城市集。

1.1.3 局部信息素更新

ACS引入局部信息素更新策略，用于制約與平衡全局信息素更新策略，增加非最 優(yōu)路徑的被選擇概率。螞蟻每走一步就會對信息素實時更新，所經(jīng)過路徑上的信息素 將依照式（4）進行改變：

式中，?表示局部信息素?fù)]發(fā)率，τ0代表初始信息素量，值為,Lnn是根據(jù)貪婪法則（每次進行下一城市選擇時，選擇最近的城市點）得到的路徑長度，而n則是當(dāng)前測試集的城市數(shù)。由此可知，在初始階段τ0是個遠(yuǎn)小于Δτij的值，它們之間至少有n倍的差距。

1.1.4 全局信息素更新

在ACS模型中只更新屬于最好路徑的各條邊的信息素濃度。

除了局部信息素更新外，ACS還通過全局信息素的更新方式增加最優(yōu)解被選擇的概率，如式（5）和式（6）所示：

式中，ρ為全局信息素?fù)]發(fā)率，Δτij為每次迭代信息素增量，Lgb為當(dāng)前最優(yōu)路徑長度。ACS的全局信息素更新策略，即在最優(yōu)路徑釋放信息素，使全局最優(yōu)解對以后迭代螞蟻的路徑構(gòu)建成正反饋作用，增加整個算法的收斂速度。

1.2 信息熵

1948年，Shannon在他著名的《通信的數(shù)學(xué)原理》論文中指出：“信息是用來消除隨機不確定性的東西”，并提出了“信息熵”的概念，來解決信息的度量問題。

對于任意一個隨機變量X，它的信息熵H(X)定義如下：

式中，p(x)代表隨機事件x的概率。

1.3 k-opt

k-opt局部搜索算法也稱k交換算法。k-opt的基本原理是應(yīng)用局部搜索的概念，通過對k條邊（?。┻M行交換，在初始解的鄰域中對初始解進行調(diào)整，接受得到改進的可行解。一次最多可以找到的新可行解的個數(shù)為2k。設(shè)T是一條初始路徑，該算法總是試圖找到2個有序集合X(X∈T)和Y(Y∈T)，如果在一定要求下用Y集合代替X集合，使得新的費用代價變小，則這k條邊的交換就被稱為k-opt 交換。優(yōu)化解X就叫作T的kopt優(yōu)化解。

舉例當(dāng)k=3 時，可能得到如圖1 所示的8 條k-opt的新路徑。

圖1 3-opt優(yōu)化Fig.1 3-opt optimization

2 本文算法改進

2.1 基于收斂系數(shù)的動態(tài)信息素更新策略

2.1.1 相對信息熵

設(shè)種群相對信息熵為PRIE（population relative information entropy）。

信息熵體現(xiàn)的是未知事物的信息量，基本參數(shù)是概率，且概率分布越平均，信息熵越大。在螞蟻總數(shù)量確定的情況下，越多的螞蟻得到不同解，則得解概率越平均。當(dāng)每只螞蟻都得到一個獨立解時，信息熵最大[10]。信息熵越大，則多樣性越好，反之越差。

設(shè)一批路徑的數(shù)量為M，路徑中不重復(fù)的路徑個數(shù)為Nnr,c(xi)表示不重復(fù)路徑xi在所有路徑中出現(xiàn)的次數(shù)。

每輪迭代結(jié)束后按照式（9）、（10）更新PRIE：

由于TSP問題解是環(huán)路，在計算信息熵時將環(huán)路按照同一起點重新排列后相同的路徑視為同一條路徑。

由于對稱TSP問題不在乎路徑正反順序，在計算信息熵時將正序相同和反序相同的路徑視為同一條路徑。

2.1.2 多樣性增加系數(shù)

設(shè)多樣性增加系數(shù)為CDI（coefficient of diversity increase）。

每輪迭代結(jié)束后按照式（11）、（12）更新CDI：

2.1.3 停滯次數(shù)

設(shè)停滯輪數(shù)為NS（number of stagnation）。

初始時，NS(0)=0。

每輪迭代結(jié)束后按照式（13）、（14）更新NS。

如果一輪搜索中找到新的更優(yōu)解，則：

否則：

設(shè)最大停滯次數(shù)MNS=20。

0≤NS≤MNS

2.1.4 收斂系數(shù)

設(shè)收斂系數(shù)為CC（convergence coefficient）。

初始時，CC(0)=1。

設(shè)收斂系數(shù)最小值CCmin=1

設(shè)收斂系數(shù)最大值CCmax=200

設(shè)收斂系數(shù)增長率CG=1.1。

CCmin≤CC≤CCmax

2.1.5 收斂系數(shù)和停滯次數(shù)更新規(guī)則

每輪迭代結(jié)束后按照式（15）～（19）更新CC和NS。

設(shè)Lib是當(dāng)前一輪迭代之中的最優(yōu)路徑長度，Lnn為貪心算法的路徑長度，相對信息熵因子為RIEF（Relative information entropy factor），取值為1。

如果CDI＞0，則：

如果NS＞MNS，則：

如果Lib≤Lnn，則：

否則：

2.1.6 動態(tài)信息素更新規(guī)則

設(shè)收斂系數(shù)為CC，可以通過調(diào)節(jié)CC來平衡收斂性和多樣性。CC越大，則信息素之間的差距越大，收斂越快；CC越小，則信息素越均勻，多樣性越高。

路徑(i,j)上的信息素τ(i,j)按照式（20）、（21）計算，信息素可緩存，減少重復(fù)計算，每輪迭代完成后重新計算信息素。

設(shè)Lnn為貪心算法的路徑長度，Tbh為最優(yōu)路徑的合集，Lr(k)為Tbh路徑中第k條的長度，Sr為Tbh路徑的總條數(shù)，T(k)為Tbh中第k條路徑的線段集合。

設(shè)函數(shù)C(k,i,j)表示路徑線段(i,j)是否存在于最優(yōu)路徑的合集的第k條路徑之中。設(shè)需要更新的路徑集合為Tupdate。如果收斂系數(shù)比之前增加了，則Tupdate為最優(yōu)路徑集合和此輪迭代的路徑的合集（去除重復(fù)），如果收斂系數(shù)比之前減少了，則Tupdate為全部路徑集合。收斂系數(shù)增加的次數(shù)大于減少的次數(shù)。

信息素可以用64 位浮點數(shù)表示，信息素可能太大。如果有信息素τ超過64 位浮點數(shù)最大范圍，則在構(gòu)建一條路徑時，直接返回全局最優(yōu)路徑。這是很少出現(xiàn)的邊界情況。

對于函數(shù)C(k,i,j)的性能優(yōu)化，由于每輪迭代中查詢次數(shù)（n2級別）遠(yuǎn)大于修改次數(shù)1次，故可以用緩存和哈希表進行性能優(yōu)化。在每輪迭代完成后修改哈希表，在每一輪迭代中，把查詢的時間復(fù)雜度從O(n3)降低到O(n2)，修改的時間復(fù)雜度為O(n)。

2.1.7 控制收斂系數(shù)和信息素的原則和影響分析

收斂系數(shù)增大的原則有：

（1）當(dāng)?shù)顑?yōu)路徑長度小于貪心路徑長度時，以較慢速度提高收斂系數(shù)，更多地在這一可能找到較優(yōu)路徑的區(qū)域搜索。

（2）當(dāng)?shù)顑?yōu)路徑長度大于貪心路徑長度時，以較快速度提高收斂系數(shù)，以免進行無用的搜索，離開比貪心路徑更差的區(qū)域。

收斂系數(shù)減小的原則有：

（1）當(dāng)停滯次數(shù)達到一定值時，可能進入了局部最優(yōu)的區(qū)域，需要增加多樣性，跳出這一區(qū)域，降低收斂系數(shù)。

（2）當(dāng)信息熵降低時，表明搜索的路徑更加集中了，多樣性降低了，按照信息熵的大小降低收斂系數(shù)，信息熵越低，使得收斂系數(shù)越小。

當(dāng)收斂系數(shù)不變時，影響信息素的因素有：

（1）在最優(yōu)路徑集合中的線段的信息素較大，不在最優(yōu)路徑集合中的路徑線段的信息素較小。

（2）當(dāng)前路徑越優(yōu)，則貪心路徑長度與當(dāng)前路徑長度的比值越大，則信息素越大，反之亦然。

收斂系數(shù)的變化對信息素的影響有：

（1）在最優(yōu)路徑集合中與不在最優(yōu)路徑集合中的路徑線段之間的信息素差距隨著收斂系數(shù)增大而指數(shù)級增大。

（2）貪心路徑長度與當(dāng)前路徑長度的比值的大小差距會被收斂系數(shù)按照指數(shù)級放大或縮小，收斂系數(shù)越大，這一差距就會越大。

（3）收斂系數(shù)越大，則越靠近最優(yōu)的區(qū)域的信息素的最大值會變得更大，越遠(yuǎn)離最優(yōu)區(qū)域的信息素的最小值會變得更小，使得搜索更容易靠近最優(yōu)路徑區(qū)域附近。

2.2 基于最優(yōu)路徑集合的獎懲策略

2.2.1 最優(yōu)路徑集合

設(shè)集合Topt為最優(yōu)路徑集合，保存所有路徑中的最短的Mopt條路徑。設(shè)集合Topt的大小為Mopt，取值為10。

（1）要求集合Topt不包含重復(fù)路徑。

（2）當(dāng)生成了一條新路徑時，如果集合Topt中路徑數(shù)量小于Mopt，則將這個新路徑添加到Topt中。

（3）如果這條路徑的長度比集合Topt中最差路徑更長，則不添加此路徑，否則使用此路徑替換最差路徑。

2.2.2 每一步的可選城市選擇方法

設(shè)Topt為最優(yōu)路徑合集，設(shè)每個城市的路徑鄰居城市為Topt的路徑中與當(dāng)前城市相連的城市。每一步的可選城市由它的路徑鄰居城市和其他隨機選擇的城市組成，排除已經(jīng)走過的城市。

每一步的可選城市數(shù)量最大為NCL,取值為40。

這樣就可以縮小搜索范圍，對最優(yōu)路徑集合進行獎勵，對其他路徑進行懲罰，減少螞蟻每一步可選城市的數(shù)量，減少計算量，提高收斂速度。

每個城市的路徑鄰居城市可以緩存，每輪迭代完成后重新計算。

2.3 局部優(yōu)化方法

2.3.1 k-opt

在本文中，設(shè)NC為城市數(shù)，k的隨機選擇范圍是(NC/2≥k≥2)，當(dāng)k越大，k被選中的概率越低。k被選中的權(quán)重為1/k。

2.3.2 k-exchange

k-exchange優(yōu)化方法是指，先克隆原路徑T得到路徑X，在路徑X中隨機選擇k個節(jié)點從路徑X中刪除，對于這k個節(jié)點重新隨機排序后，放回路徑X中刪除的空位，構(gòu)建新路徑X。如果路徑X的代價比路徑T的代價更小，則使用路徑X代替路徑T。路徑X稱為路徑T的k-exchange優(yōu)化解。

在本文中，設(shè)NC為城市數(shù)，k的選擇范圍是(NC/2≥k≥2),當(dāng)k越大，k被選中的概率越低。k被選中的權(quán)重為1/k。

舉例，當(dāng)k=2 時，可能得到如圖2、圖3所示的優(yōu)化效果，使用圖3代替圖2，路徑更短。

圖2 2-exchange優(yōu)化之前Fig.2 2-exchange before optimization

圖3 2-exchange優(yōu)化之后Fig.3 2-exchange after optimization

2.3.3 精準(zhǔn)消除交叉點的2-opt

先從路徑T的線段中每兩條線段判斷是否存在交叉點，找出這個交叉點的兩個路徑線段。如果存在交叉點，把交叉點的兩條路徑片段切斷，使用2-opt優(yōu)化生成新路徑X，如果新路徑X更短，則使用新路徑X代替舊路徑T。

因為查找交叉點的時間復(fù)雜度為O(n2)，所以要限制每次查找交叉點的線段條數(shù)最大為MCP，設(shè)MCP=40。

如圖4、圖5 所示，紅色路徑比原本的藍(lán)色路徑更短，因為三角形兩邊長度之和大于第三邊長度，使用圖5代替圖4，路徑更短。

圖4 精準(zhǔn)2-opt優(yōu)化之前Fig.4 Precise 2-opt before optimization

圖5 精準(zhǔn)2-opt優(yōu)化之后Fig.5 Precise 2-opt after optimization

2.3.4 局部優(yōu)化方法的使用

局部優(yōu)化的路徑選擇方式為全局最優(yōu)解和這輪路徑中的長度排名靠前的路徑，這些路徑的局部優(yōu)化有可能跳出局部最優(yōu)，又不會太差，進一步提高解的精度。

在每輪迭代完成后，對全局最優(yōu)解和這輪路徑中的長度排名前一半的路徑（去除重復(fù)）執(zhí)行如下優(yōu)化方法。

（1）對當(dāng)前路徑進行k-opt 局部優(yōu)化，共生成10 條路徑，使用更優(yōu)解替代當(dāng)前路徑(2≤k≤N/2)。

（2）執(zhí)行循環(huán)，使用k-exchange隨機交換k個節(jié)點，使用更優(yōu)解替代當(dāng)前路徑(2≤k≤N/2)，總共循環(huán)10次。

（3）執(zhí)行循環(huán)，如果當(dāng)前路徑還有交叉點，則使用精準(zhǔn)的2-opt局部優(yōu)化消除交叉點，如果當(dāng)前路徑?jīng)]有交叉點，隨機生成一條k-opt路徑取優(yōu)化解，總共循環(huán)10次。

2.4 路徑構(gòu)建方式

2.4.1 貪心算法構(gòu)建初始解

貪心算法的含義為每一步移動都選擇當(dāng)前代價最小的路徑。使用貪心算法構(gòu)建一條初始路徑時，嘗試隨機選擇一個起點構(gòu)建一條路徑。如果全局最優(yōu)解未初始化，則將其作為全局最優(yōu)解保存，記錄此路徑長度作為全局最短路徑長度。

設(shè)貪心算法最多創(chuàng)建Mgreedy條路徑，Mgreedy=20。

設(shè)貪心算法的每一步可選城市數(shù)最多為MCG=300 個。

2.4.2 狀態(tài)轉(zhuǎn)移概率

設(shè)螞蟻從城市i移動到城市j的概率為P(i,j),螞蟻從城市i移動到城市j的權(quán)重為w(i,j),節(jié)點隨機選擇概率為RSP（random selection probability）。

當(dāng)螞蟻在城市i，要選擇下一個城市j時，先生成隨機數(shù)p0(0＜p0＜1)。使用Allowed(k)表示當(dāng)前可選的城市集合。當(dāng)前可選的城市集合之中的城市數(shù)量為MA。然后使用輪盤法，根據(jù)P(i,j) 選出下一個城市j。螞蟻從城市i移動到城市j，如式（22）～（24）所示。

啟發(fā)式信息η(i,j)和ACS中式（1）相同。

權(quán)重可以用64位浮點數(shù)表示，使用輪盤法時，如果權(quán)重w超過64 位浮點數(shù)最大值，則直接返回權(quán)重最大的城市。這是很少出現(xiàn)的邊界情況。

2.4.3 節(jié)點隨機選擇概率

設(shè)節(jié)點隨機選擇概率為RSP，多樣性增加系數(shù)為CDI。

初始時，RSP(0)=0。

每輪搜索結(jié)束后按照式（25）更新節(jié)點隨機選擇概率RSP。

2.5 算法流程

（1）輸入城市的坐標(biāo)。

（2）初始化參數(shù)和最優(yōu)路徑集合。

（3）用貪心算法生成出Mgreedy條路徑，計算出最短路徑長度，初始化信息素，按照式（20）初始化每個城市的路徑鄰居城市。

（4）搜索輪數(shù)←0。循環(huán)執(zhí)行步驟（5）到（7）。當(dāng)搜索輪數(shù)到達最大迭代循環(huán)次數(shù)時，停止循環(huán)，輸出最優(yōu)路徑及其長度，算法結(jié)束。

（5）設(shè)有Na只螞蟻，每只螞蟻使用狀態(tài)轉(zhuǎn)移概率構(gòu)建路徑或者按照概率進行節(jié)點隨機選擇構(gòu)建出一條路徑，如式（24）。

（6）在所有螞蟻都構(gòu)建路徑完成后，搜索輪數(shù)增加1，對全局最優(yōu)解和這輪路徑中的長度排名前一半的路徑（去除重復(fù)）執(zhí)行三種局部優(yōu)化方法。

（7）計算信息熵，按照式（10）計算多樣性增加系數(shù)，按照式（12）計算節(jié)點隨機選擇的概率，按照式（25）更新收斂系數(shù)，更新停滯次數(shù)，按照式（15）～（19）更新信息素，按照式（20）更新每個城市的路徑鄰居城市和最優(yōu)路徑集合。

2.6 時間復(fù)雜度分析

設(shè)城市數(shù)為n，迭代次數(shù)為k，螞蟻數(shù)為m，時間復(fù)雜度如表1所示。

表1 時間復(fù)雜度Table 1 Time complexity

3 仿真實驗測試與分析

3.1 參數(shù)設(shè)置

本文算法的默認(rèn)參數(shù)如表2所示。

表2 本文算法的默認(rèn)參數(shù)Table 2 Default parameters of algorithm in this paper

ACS的參數(shù)設(shè)置如表3所示。

表3 ACS算法的默認(rèn)參數(shù)Table 3 Default parameters of ACS algorithm

3.2 算法性能測試

3.2.1 本文算法中策略和局部優(yōu)化方法的測試

3.2.1.1 基于收斂系數(shù)的動態(tài)信息素更新策略性能測試

在ACS+三種局部優(yōu)化方法基礎(chǔ)上，保持其他策略和參數(shù)相同，在信息素方面，使用基于收斂系數(shù)的動態(tài)信息素更新策略與原本的ACS算法進行對比測試。

設(shè)算法A 為經(jīng)典ACS，算法D 為ACS+基于收斂系數(shù)的動態(tài)信息素更新策略。設(shè)經(jīng)典ACS算法花費的時間為1個單位。不同算法的平均每輪迭代時間如表4所示。不同算法總迭代次數(shù)相同的最優(yōu)解和誤差率如表5所示。

表4 算法A和算法D的平均每輪迭代時間Table 4 Average iteration time per round for Algorithm A and Algorithm D

表5 算法A和算法D的最優(yōu)解和誤差率Table 5 Optimal solutions and error rates for Algorithm A and Algorithm D

不同算法在測試算例Rand300中的相對信息熵、每輪平均路徑長度和最優(yōu)路徑長度的變化曲線如圖6、圖7和圖8所示。

從圖6、圖7、圖8可以看出，得益于動態(tài)信息素更新策略，當(dāng)信息熵降低時，導(dǎo)致平均路徑長度和最優(yōu)路徑長度都減小，接近最優(yōu)解；之后信息熵自動增加，導(dǎo)致平均解和局部最優(yōu)解相應(yīng)地變大，有助于跳出局部最優(yōu)，從而可以自適應(yīng)平衡多樣性和收斂性。

圖6 動態(tài)信息素更新與ACS的相對信息熵對比Fig.6 Comparison of relative information entropy between dynamic pheromone update and ACS

圖7 動態(tài)信息素更新與ACS的迭代平均路徑長度對比Fig.7 Comparison of iterative average path length between dynamic pheromone update and ACS

圖8 動態(tài)信息素更新與ACS的最優(yōu)路徑長度對比Fig.8 Comparison of optimal path length between dynamic pheromone update and ACS

結(jié)果分析，使用了基于收斂系數(shù)的動態(tài)信息素更新策略之后，對于有些地圖，比ACS 略差一點；對于有些地圖，誤差率大幅減少，大幅加快了收斂速度，提高了解的精度，規(guī)模越大效果越好。

例如，在Pr107 中，誤差率從1.9%降低到1.1%；在Pr226中，誤差率從2.8%降低到1.9%；在Rand300中，誤差率從11.6%降低到7.5%。

因為動態(tài)的信息素能夠自適應(yīng)地調(diào)節(jié)多樣性或者收斂性，所以規(guī)模越大，效果越明顯，可以平衡解的精度和收斂速度的矛盾。

3.2.1.2 三種局部優(yōu)化方法性能測試

在ACS算法基礎(chǔ)上，保持其他策略和參數(shù)相同，使用與不使用三種局部優(yōu)化方法進行對比測試。

設(shè)算法A 為經(jīng)典ACS，算法B 為ACS+三種局部優(yōu)化方法。設(shè)經(jīng)典ACS 算法花費的時間為1 個單位。不同算法的平均每輪迭代時間如表6 所示。不同算法總時間相同的最優(yōu)解和誤差率如表7 所示。

表6 算法A和算法B的平均每輪迭代時間Table 6 Average iteration time per round for Algorithm A and Algorithm B

表7 算法A和算法B的最優(yōu)解和誤差率Table 7 Optimal solutions and error rates for Algorithm A and Algorithm B

不同算法在測試算例Pr226中的最優(yōu)路徑平面圖和最優(yōu)路徑長度的變化曲線如圖9、圖10和圖11所示。

圖9 Pr226中ACS的最優(yōu)路徑平面圖（城市數(shù)：226，路徑長度：94 349）Fig.9 Optimal path plan of ACS in Pr226

圖11 三種局部優(yōu)化方法與ACS的最優(yōu)路徑長度對比Fig.11 Comparison of optimal path length between three local optimization methods and ACS

結(jié)果分析，使用了三種局部優(yōu)化方法之后，誤差率大幅減少，大幅加快了收斂速度，提高了解的精度。

例如，在Pr107 中，使用了此策略后誤差率從5.0%降低到1.7%；在Pr226 中，使用了此策略后誤差率從17.0%降低到8.9%；在Lin318 中，使用了此策略后誤差率從32%降低到11%。

三種局部優(yōu)化方法因為增大了搜索空間，能夠跳出局部最優(yōu)，所以增加了多樣性，進一步提高了解的精度。

3.2.1.3 基于最優(yōu)路徑集合的獎懲策略性能測試

在ACS+三種局部優(yōu)化方法的基礎(chǔ)上，保持其他策略和參數(shù)相同，在可選城市方面，使用基于最優(yōu)路徑集合的獎懲策略與原本的ACS算法進行對比測試。

設(shè)算法B 為ACS+三種局部優(yōu)化方法，算法C 為ACS+三種局部優(yōu)化方法+最優(yōu)路徑集合獎懲策略。設(shè)ACS+三種局部優(yōu)化方法花費的時間為1個單位。不同算法的平均每輪迭代時間如表8 所示。不同算法總時間相同的最優(yōu)解和誤差率如表9所示。

表8 算法C和算法B的平均每輪迭代時間Table 8 Average iteration time per round for Algorithm C and Algorithm B

表9 算法C和算法B的最優(yōu)解和誤差率Table 9 Optimal solutions and error rates for Algorithm C and Algorithm B

不同算法在測試算例A280 中的相對信息熵、迭代平均路徑長度和最優(yōu)路徑長度的變化曲線如圖12 和圖13所示。

圖12 有和無最優(yōu)路徑集合獎懲策略的平均路徑長度對比Fig.12 Comparison of average path length with and without optimal path sets reward and punishment strategies

圖13 有和無最優(yōu)路徑集合獎懲策略的最優(yōu)路徑長度對比Fig.13 Comparison of optimal path length with and without optimal path sets reward and punishment strategies

結(jié)果分析，使用了基于最優(yōu)路徑集合的獎懲策略之后，誤差率大幅減少，大幅加快了收斂速度，提高了解的精度。規(guī)模越大，節(jié)省的計算量越大。

例如，在kroA100 中，使用了此策略后誤差率從10.1%降低到5.9%；在kroA150中，使用了此策略后誤差率從14.1%降低到12.0%；在A280 中，使用了此策略后誤差率從23.8%降低到13.2%。

此策略因為縮小了搜索的范圍，更接近最優(yōu)解附近搜索，所以加快了收斂速度。

3.2.2 與傳統(tǒng)算法和當(dāng)今最新算法對比測試

3.2.2.1 對比算法的來源

EDHACO 來自于文獻[23]；ACS 來自于文獻[6]；MMAS 來自于文獻[7]；WAS 來自于文獻[10]；PCCACO來自于文獻[5]；DA-GVNS來自于文獻[22]。

3.2.2.2 對比算法的默認(rèn)參數(shù)

PCCACO、EDHACO、WAS、DA-GVNS 的參數(shù)與原文獻相同。ACS和MMAS的參數(shù)如表10所示。

表10 ACS和MMAS的參數(shù)設(shè)置Table 10 Parameter settings for ACS and MMAS

3.2.2.3 在測試算例中的測試結(jié)果對比

測試結(jié)果對比如表11所示。由復(fù)雜度分析可以看出，本文算法沒有增加時間復(fù)雜度。

表11 本文算法與其他算法的測試結(jié)果對比Table 11 Comparison of test results of this paper algorithm and other algorithms

結(jié)果分析，本文算法比ACS、MMAS經(jīng)典算法提高了解的精度，加快了收斂速度。

例如，在eil51中，本文算法與其他算法達到相同精度。在kroB100中，本文算法比經(jīng)典算法MMAS提高很大，誤差率從0.98%降低到0.1%。在kroA200 中，本文算法比ACS、MMAS經(jīng)典算法對比，解的誤差率0.7%優(yōu)于1.7%和1.3%。在tsp225中，本文算法誤差率0.5%，比ACS、MMAS 經(jīng)典算法的誤差率1.5%、2.7%，提高了很大的精度。在Pr264中，本文算法解的誤差率0.3%優(yōu)于ACS的誤差率1.2%。

本文算法與近期的優(yōu)秀算法相比精度很接近。例如，在kroB100中，本文算法比DA-GVNS的精度略低一點，差距在0.04%左右，也比EDHACO、WAS 有更高的精度，差距在0.28%左右。說明本文的策略對于小規(guī)模問題有效地平衡了精度和收斂速度的矛盾。

在kroA200 中，本文算法解的誤差率0.7%，與DAGVNS、EDHACO、WAS 相比精度提高一些，差距在0.7%到0.3%左右，比PCCACO的精度略低一點，差距在0.7%左右。在tsp225 中，本文算法達到與PCCACO 幾乎相同的誤差率0.5%。在Pr264 中，本文算法誤差率0.3%，與DA-GVNS 誤差率1.5%對比，本文算法誤差率優(yōu)于DA-GVNS。說明本文的策略對于中規(guī)模問題有效地平衡了精度和收斂速度的矛盾。

在Lin318 中，本文算法解的誤差率3.1%，與DAGVNS 對比很接近，相比差距在0.4%左右。在pcd442中，本文算法解的誤差率4.8%，與DA-GVNS 對比很接近，相比差距在0.4%左右。說明本文的策略對于大規(guī)模問題有效地平衡了解的精度和收斂速度的矛盾。

綜上所述，在不同規(guī)模的問題中，本文算法都能夠有效地解決TSP問題。

3.3 最大停滯次數(shù)和相對信息熵因子的正交實驗

最大停滯次數(shù)和相對信息熵因子會影響到收斂系數(shù)的降低。為了測試不同參數(shù)對于算法性能的影響，對這兩個參數(shù)進行正交實驗。

選擇測試算例Pr264；最大停滯次數(shù)設(shè)定為4 個值15、20、25、30；相對信息熵因子設(shè)定為4 個值0.7、1.0、1.2、1.5；在相同的迭代次數(shù)300 代，其他參數(shù)相同情況下，總共16 組條件，各測試2 次取值，共32 次測試的最優(yōu)解和誤差率統(tǒng)計如表12所示，按照誤差率排序。

表12 最大停滯次數(shù)和相對信息熵因子的正交實驗Table 12 Orthogonal experiment of maximum stagnation number and relative information entropy factor

從統(tǒng)計中可以看出，在排名前30%的測試結(jié)果中，最大停滯次數(shù)按照出現(xiàn)次數(shù)從大到小依次是20 出現(xiàn)4次，25出現(xiàn)3次，30出現(xiàn)2次；相對信息熵因子按照出現(xiàn)次數(shù)從大到小依次是1.5 出現(xiàn)4 次，1.0 出現(xiàn)3 次，1.2 出現(xiàn)2次。因此最大停滯次數(shù)的最合適區(qū)間為20到30；信息熵因子的最合適區(qū)間為1.0 到1.5。這證明了本文算法的參數(shù)設(shè)置是合理的。

4 結(jié)束語

針對常規(guī)蟻群算法容易陷入局部最優(yōu)，收斂速度慢，難以解決大規(guī)模問題的情況，本文在前人的研究基礎(chǔ)上，提出基于收斂系數(shù)的動態(tài)信息素更新策略和基于最優(yōu)路徑集合的獎懲策略的蟻群算法和三種局部優(yōu)化方法。

經(jīng)過實驗測試，本文算法中，基于收斂系數(shù)的動態(tài)信息素更新策略和三種局部優(yōu)化方法能夠有效地平衡算法的多樣性和收斂性，加快收斂速度，跳出局部最優(yōu)；基于最優(yōu)路徑集合的獎懲策略能夠減少計算量，縮小搜索范圍，加快收斂速度，能夠有效解決TSP問題，具有較高的求解效率。

以后的改進方向是使用多種群或者聚類策略，來進一步提高解決大規(guī)模問題的精度和收斂速度。