動(dòng)態(tài)信息素更新和路徑獎(jiǎng)懲的蟻群算法

馬世軒，游曉明，劉 升

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

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

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

旅行商問(wèn)題是生活中問(wèn)題的抽象的重要的模型，其基本特點(diǎn)是易于描述，難于求解，是典型的NP 難（nondeterministic polynomial hard）問(wèn)題。因此，對(duì)旅行商問(wèn)題的研究具有重要意義。目前解決TSP 問(wèn)題的方法主要有暴力窮舉法、貪心算法、分支定解算法、動(dòng)態(tài)規(guī)劃算法、遺傳算法、蟻群算法、模擬退火算法、粒子群算法、Hopfield 神經(jīng)網(wǎng)絡(luò)算法等。近幾年不斷有新的更高效的智能優(yōu)化算法被提出：如張九龍等[1]對(duì)蝴蝶優(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）進(jìn)行了對(duì)比分析研究。也有相關(guān)文獻(xiàn)[2]和[3]等對(duì)智能算法的應(yīng)用做出了研究，研究表明蟻群算法有突出的表現(xiàn)。因此本文使用蟻群算法來(lái)研究TSP問(wèn)題。

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

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

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

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

1 相關(guān)工作

1.1 蟻群系統(tǒng)

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

1.1.1 啟發(fā)式信息

設(shè)啟發(fā)式信息為η(i,j)，d(i,j)為兩個(gè)城市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時(shí)可供選擇的城市集（在TSP問(wèn)題中，城市只可被訪問(wèn)一次，allowedk為還沒(méi)有被訪問(wèn)的城市）。α和β分別指代信息素和啟發(fā)式的影響程度。

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

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

1.1.3 局部信息素更新

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

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

1.1.4 全局信息素更新

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

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

式中，ρ為全局信息素?fù)]發(fā)率，Δτij為每次迭代信息素增量，Lgb為當(dāng)前最優(yōu)路徑長(zhǎng)度。ACS的全局信息素更新策略，即在最優(yōu)路徑釋放信息素，使全局最優(yōu)解對(duì)以后迭代螞蟻的路徑構(gòu)建成正反饋?zhàn)饔茫黾诱麄€(gè)算法的收斂速度。

1.2 信息熵

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

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

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

1.3 k-opt

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

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

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

2 本文算法改進(jìn)

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

2.1.1 相對(duì)信息熵

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

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

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

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

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

由于對(duì)稱TSP問(wèn)題不在乎路徑正反順序，在計(jì)算信息熵時(shí)將正序相同和反序相同的路徑視為同一條路徑。

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）。

初始時(shí)，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）。

初始時(shí)，CC(0)=1。

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

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

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

CCmin≤CC≤CCmax

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

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

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

如果CDI＞0，則：

如果NS＞MNS，則：

如果Lib≤Lnn，則：

否則：

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

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

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

設(shè)Lnn為貪心算法的路徑長(zhǎng)度，Tbh為最優(yōu)路徑的合集，Lr(k)為Tbh路徑中第k條的長(zhǎng)度，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 位浮點(diǎn)數(shù)表示，信息素可能太大。如果有信息素τ超過(guò)64 位浮點(diǎn)數(shù)最大范圍，則在構(gòu)建一條路徑時(shí)，直接返回全局最優(yōu)路徑。這是很少出現(xiàn)的邊界情況。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 局部?jī)?yōu)化方法

2.3.1 k-opt

在本文中，設(shè)NC為城市數(shù)，k的隨機(jī)選擇范圍是(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中隨機(jī)選擇k個(gè)節(jié)點(diǎn)從路徑X中刪除，對(duì)于這k個(gè)節(jié)點(diǎn)重新隨機(jī)排序后，放回路徑X中刪除的空位，構(gòu)建新路徑X。如果路徑X的代價(jià)比路徑T的代價(jià)更小，則使用路徑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 時(shí)，可能得到如圖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)消除交叉點(diǎn)的2-opt

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

因?yàn)椴檎医徊纥c(diǎn)的時(shí)間復(fù)雜度為O(n2)，所以要限制每次查找交叉點(diǎn)的線段條數(shù)最大為MCP，設(shè)MCP=40。

如圖4、圖5 所示，紅色路徑比原本的藍(lán)色路徑更短，因?yàn)槿切蝺蛇呴L(zhǎng)度之和大于第三邊長(zhǎng)度，使用圖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 局部?jī)?yōu)化方法的使用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.3 節(jié)點(diǎn)隨機(jī)選擇概率

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

初始時(shí)，RSP(0)=0。

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

2.5 算法流程

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)測(cè)試與分析

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 算法性能測(cè)試

3.2.1 本文算法中策略和局部?jī)?yōu)化方法的測(cè)試

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

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

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

表4 算法A和算法D的平均每輪迭代時(shí)間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

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

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

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

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

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

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

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

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

3.2.1.2 三種局部?jī)?yōu)化方法性能測(cè)試

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

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

表6 算法A和算法B的平均每輪迭代時(shí)間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

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

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

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

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

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

三種局部?jī)?yōu)化方法因?yàn)樵龃罅怂阉骺臻g，能夠跳出局部最優(yōu)，所以增加了多樣性，進(jìn)一步提高了解的精度。

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

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

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

表8 算法C和算法B的平均每輪迭代時(shí)間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

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

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

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

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

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

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

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

3.2.2.1 對(duì)比算法的來(lái)源

EDHACO 來(lái)自于文獻(xiàn)[23]；ACS 來(lái)自于文獻(xiàn)[6]；MMAS 來(lái)自于文獻(xiàn)[7]；WAS 來(lái)自于文獻(xiàn)[10]；PCCACO來(lái)自于文獻(xiàn)[5]；DA-GVNS來(lái)自于文獻(xiàn)[22]。

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

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

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

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

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

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

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

例如，在eil51中，本文算法與其他算法達(dá)到相同精度。在kroB100中，本文算法比經(jīng)典算法MMAS提高很大，誤差率從0.98%降低到0.1%。在kroA200 中，本文算法比ACS、MMAS經(jīng)典算法對(duì)比，解的誤差率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的精度略低一點(diǎn)，差距在0.04%左右，也比EDHACO、WAS 有更高的精度，差距在0.28%左右。說(shuō)明本文的策略對(duì)于小規(guī)模問(wèn)題有效地平衡了精度和收斂速度的矛盾。

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

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

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

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

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

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

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

從統(tǒng)計(jì)中可以看出，在排名前30%的測(cè)試結(jié)果中，最大停滯次數(shù)按照出現(xiàn)次數(shù)從大到小依次是20 出現(xiàn)4次，25出現(xiàn)3次，30出現(xiàn)2次；相對(duì)信息熵因子按照出現(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é)束語(yǔ)

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

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

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