許凱波, 魯海燕，程畢蕓，黃 洋

(江南大學 理學院，江蘇 無錫 214122)

求解TSP的改進信息素二次更新與局部優(yōu)化蟻群算法

許凱波, 魯海燕*，程畢蕓，黃 洋

(江南大學 理學院，江蘇 無錫 214122)

(*通信作者電子郵箱luhaiyan@jiangnan.edu.cn)

針對蟻群(ACO)算法收斂速度慢、容易陷入局部最優(yōu)的缺陷，提出了一種改進信息素二次更新局部優(yōu)化蟻群算法(IPDULACO)。該算法對蟻群搜索到的當前全局最優(yōu)解中路徑貢獻度大于給定的路徑貢獻閾值的子路徑信息素進行二次更新，以提高構成潛在最優(yōu)解的子路徑被選擇的概率，從而加快算法的收斂。然后，在搜索過程中，當蟻群陷入局部最優(yōu)時，使用隨機插入法對局部最優(yōu)解中城市的排序進行調整，以增強算法跳出局部最優(yōu)解的能力。將改進算法應用于若干經典的旅行售貨商問題(TSP)進行仿真實驗，實驗結果表明，對于小規(guī)模的TSP, IPDULACO可以在較少的迭代次數內獲得已知最優(yōu)解；對于較大規(guī)模的TSP, IPDULACO可以在較少的迭代次數內獲得更精確的解。因此，IPDULACO具有更強的搜索全局最優(yōu)解的能力和更快的收斂速度，可以高效求解TSP。

旅行售貨商問題；蟻群算法；信息素二次更新；局部優(yōu)化

0 引言

旅行售貨商問題(Traveling Salesman Problem, TSP)是經典的組合優(yōu)化問題[1]，現實生活中的許多問題都可以歸結為TSP，如郵路問題、裝配線上的螺母問題和產品的生產安排問題等。因此，TSP的有效求解在降低運輸成本、提高生產效率等方面具有重要意義。由于TSP是NP難(Non-deterministic Polynomial hard, NP-hard)問題[2]，隨著問題規(guī)模的擴大，問題解的數量呈指數式增長，目前尚無求解該問題的有效算法。一般地，求解TSP的算法大體可以分為兩類：精確算法和啟發(fā)式算法。對于小規(guī)模的TSP，用精確算法即可獲得最優(yōu)解；對于中大規(guī)模的TSP，精確算法由于求解時間和空間消耗過大而完全不可行，一般用啟發(fā)式算法來求解。精確算法主要有分枝定界法[3]、線性規(guī)劃法[4]和動態(tài)規(guī)劃法[5]等。啟發(fā)式算法包括：最鄰近算法[6]、貪婪算法[7]、遺傳算法(Genetic Algorithm, GA)[8]、模擬退火(Simulated Annealing, SA)[9]算法、禁忌搜索(Tabu Search, TS)[10]算法、粒子群(Particle Swarm Optimization, PSO)[11]算法、蟻群(Ant Colony Optimization, ACO)[12]算法等。

蟻群算法[13-14]是根據螞蟻群體在覓食過程中所體現出的智能行為提出的。該算法具有正反饋、分布式、并行式、自組織等優(yōu)點，經過眾多學者的不斷探索研究，蟻群算法已經被成功地用于解決許多實際問題，譬如數據挖掘、參數辨識、圖像處理、圖形著色、分析化學、TSP等。但是，蟻群算法也存在迭代次數多、收斂速度慢以及容易陷入局部最優(yōu)等缺陷。針對以上缺陷，國內外學者也提出了很多的改進策略。比如：Dorigo等[12]提出了螞蟻系統(tǒng)，該算法使用最優(yōu)選擇與隨機選擇結合的路徑選擇方式，以及局部更新和全局更新的信息素更新策略，來提高算法的全局搜索能力，但最優(yōu)解的精度有待提高；Stutzle等[15]提出了最大最小蟻群系統(tǒng)(Max-Min Ant System, MMAS)，通過對路徑上的信息素進行上下界的限制避免算法陷入局部最優(yōu)；鄭松等[16]提出了動態(tài)調整選擇策略的改進蟻群算法，通過適當刺激螞蟻嘗試具有較弱信息素的解，以提高所得解的全局性，但迭代次數較多，收斂速度較慢；吳華鋒等[17]提出了基于自然選擇策略的蟻群算法求解TSP，通過隨機進化因子的隨機性增強算法跳出局部最優(yōu)解的概率，以及信息素二次更新規(guī)則加快算法的收斂。本文將對文獻[17]提出的信息素二次更新規(guī)則作進一步研究，分析其存在的不足，提出一種改進的信息素二次更新策略，進一步提高算法的收斂速度；此外，在算法中引入一種局部優(yōu)化策略，當最優(yōu)解連續(xù)若干次迭代后沒有改善時，使用隨機插入法對局部最優(yōu)解中城市的排序進行調整，以增強算法跳出局部最優(yōu)解的能力。結合以上兩種改進策略提出一種求解TSP的改進信息素二次更新局部優(yōu)化蟻群算法(Ant Colony Optimization algorithm based on Improved Pheromones Double Updating and Local optimization, IPDULACO)。通過對TSP的仿真實驗，驗證了改進算法的有效性。

1 研究基礎

首先給定一個賦權圖G(V,E)，其中V={1,2,…,n}為頂點(城市)的集合，E={(i,j,dij)|i,j∈n,dij∈R+}為賦權邊(兩個城市之間的距離)的集合，假設：

(1)

則經典TSP的數學模型[18]為：

(2)

(3)

其中：|S|為圖S的頂點數。式(1)和式(3)限定經過所有頂點一次且僅一次，式(2)為TSP的目標函數，即求一條距離最短的哈密頓回路。

2 改進的蟻群算法

2.1 基本ACO算法

2.1.1 蟻群算法基本思想

螞蟻在尋找食物時，綜合考慮路徑長度和路徑上信息素兩個方面進行路徑選擇(螞蟻會在其走過的路徑釋放信息素，其他螞蟻能夠感知這種信息素并優(yōu)先選擇信息素濃度較高的路徑)。開始時，路徑上的信息素濃度較低，螞蟻主要根據路徑長度進行選擇，而且會以較大的概率選擇較短的路徑。隨著時間的推移，各路徑上的信息素逐漸積累增多；且越短的路徑，走過的螞蟻越多，路徑上殘留的信息素越多，選擇走該路徑的螞蟻也越多，如此形成一個正反饋。最終，螞蟻找到一條從巢穴到食物源的最優(yōu)路徑。

2.1.2 求解TSP的蟻群算法

(4)

其中：α為信息素重要程度因子；β為啟發(fā)函數重要程度因子；cityk(k=1,2,…,m)為螞蟻k已經訪問過的城市集合，其隨時間動態(tài)更新。經過n個時刻，所有螞蟻都尋找到一條回路，一次循環(huán)結束。同時，螞蟻釋放在各個城市間連接路徑上的信息素也在逐漸消失，因此，當所有螞蟻完成一次循環(huán)后，按式(5)和式(6)調整各個城市間連接路徑上的信息素濃度：

(5)

(6)

2.2 改進的蟻群算法求解TSP

2.2.1 信息素更新策略

在基本蟻群算法中，螞蟻在選擇路徑時主要取決于節(jié)點間的距離，即距離越短，該路徑被選擇的概率越大，距離越長，該路徑被選擇的概率越小。因為全局最優(yōu)路徑中的某些子路徑(子路徑為任意兩城市連接構成的路徑)可能較長，所以該子路徑被選擇的概率較小，導致螞蟻錯過構成潛在全局最優(yōu)解的子路徑。為了彌補這個缺陷，文獻[17]提出路徑貢獻度(ContributionDegreeofSub-Path,CDSP)的概念，定義為每次迭代蟻群找到的最優(yōu)解中，子路徑與本次迭代最優(yōu)路徑的比值，如式(7)所示。并提出一種信息素更新策略：當按式(5)和式(6)完成路徑信息素的首次更新后，對每次迭代最優(yōu)路徑上的各子路徑按式(7)所示進行路徑貢獻度判斷，按式(8)和式(9)所示再次更新信息素，即增加路徑貢獻度大于給定的路徑貢獻閾值的子路徑上的信息素，從而提高該子路徑被選擇的概率。

CSCDij=D(i,j)/Lb(t)

(7)

(8)

(9)

CSCDij=D(i,j)/Lgb(t)

(10)

其中：Lb(t)是第t次迭代后蟻群找到的此次迭代的最優(yōu)解；τij(t+1)是第t次迭代后路徑(i,j)上的信息素總量。

文獻[17]提出的信息素更新策略確實可以提高構成潛在全局最優(yōu)解的子路徑被選擇的概率。但是考慮到每次迭代得到的最優(yōu)解基本不相同，每次信息素二次更新的子路徑也基本不同，導致構成潛在全局最優(yōu)解的子路徑信息素增量不明顯，被選擇的概率也沒有有效提高。但是，相比每次迭代的最優(yōu)解，每次迭代的當前全局最優(yōu)解在每次迭代后不相同的概率較小，通常每經過一定次數的迭代后改變一次，這樣在一定的迭代次數內，信息素二次更新的子路徑一樣，信息素增量明顯，更有利于提高構成潛在全局最優(yōu)解的子路徑被選擇的概率。而且，當前全局最優(yōu)解所含子路徑構成最優(yōu)解的可能性更大，所以更應該對該條路徑中滿足條件的子路徑進行信息素的二次更新，而不是每次迭代得到的最優(yōu)路徑。

基于以上分析，本文提出一種改進的信息素更新策略。首先，和基本蟻群算法一樣，在每次迭代后，按式(5)和式(6)所示更新各個城市間連接路徑上的信息素。然后，按式(10)對每次迭代后的當前全局最優(yōu)路徑中的子路徑進行路徑貢獻度判斷，而不是對每次迭代的最優(yōu)路徑，并對路徑貢獻度大于給定的路徑貢獻閾值的子路徑按式(8)～(9)所示進行信息素的再次更新，其中Lgb(t)指t次迭代后蟻群搜索到的當前全局最優(yōu)解，q0是路徑貢獻度閾值，通過實驗驗證，取q0=0.01時算法性能最優(yōu)。

改進的信息素更新策略可以提高構成潛在最優(yōu)解的子路徑被選擇的概率，加快算法的收斂；同時，為了提高算法跳出局部最優(yōu)的能力，在算法中加入一種局部優(yōu)化策略，以提高搜索的隨機性和多樣性。

2.2.2 局部優(yōu)化策略

基本蟻群算法的信息素更新方式具有正反饋性。正反饋有利于算法的快速收斂，但優(yōu)化后期較優(yōu)路徑上的信息素積累會較多，影響種群的多樣性，算法容易陷入局部最優(yōu)而停滯，最終導致求解質量的下降。因此，本文在算法中引入一種局部優(yōu)化策略：每當算法陷入局部最優(yōu)時，使用隨機插入法對該局部最優(yōu)解中城市的排序進行調整，以提高種群的多樣性，增強算法跳出局部最優(yōu)的能力。局部優(yōu)化策略的具體方法如下：

設局部最優(yōu)解(即當前全局最優(yōu)解)為a1,a2,a3,a4,…,ai,ai+1,…,an-1,an,a1，其中ai為城市編號。對其進行局部優(yōu)化：隨機產生子路徑集合((a1,a3),(ai,an))，這里以兩條子路徑(a1,a3)和(ai,an)為例，本文在仿真實驗中設置子路徑數等于城市個數。接著按子路徑在集合中的順序，在局部最優(yōu)解中依次連接。先找到城市a1和城市a3的位置，將城市a3插入到城市a1后面，此時城市排列變?yōu)閍1,a3,a2,a4,…,ai,ai+1,…,an-1,an,a1；再找到城市ai和城市an的位置，將城市an插入到城市ai的后面，最終得到城市排列(a1,a3,a2,a4,…,ai,an,ai+1,…,an-1,a1)。計算此時的適應度，判斷解的質量是否提高，若解的質量提高，則更新全局最優(yōu)解；否則不更新。繼續(xù)隨機產生子路徑集合，按子路徑在集合中的順序在當前全局最優(yōu)解上依次連接，如此迭代多次，本文在仿真實驗中設置迭代30次。

2.2.3 改進ACO算法流程

本文改進ACO算法求解旅行商問題的簡要流程如圖1所示，基本步驟如下：

步驟1 算法開始，設置算法所需的參數，如螞蟻數量，算法迭代次數N，算法最大迭代次數Nmax等。

步驟2 將螞蟻隨機放在不同的城市上，作為起始點。

步驟3 每只螞蟻構建解空間，計算適應度值。

步驟4 按照式(5)和式(6)對各個城市間連接路徑上的信息素進行實時更新。

步驟5 按照式(10)計算路徑貢獻度，按照式(8)判斷確定路徑貢獻度大于路徑貢獻閾值的子路徑并計算信息素二次增量，按照式(9)再次更新滿足條件的子路徑上的信息素。

步驟6 判斷算法是否陷入局部最優(yōu)，判斷方法：比較本次迭代得到的全局最優(yōu)解與上一次迭代得到的全局最優(yōu)解，觀察最優(yōu)解是否得到改善，如果連續(xù)5次最優(yōu)解都沒有得到改善，則判定算法陷入局部最優(yōu)，執(zhí)行局部優(yōu)化策略；否則進入步驟7。

步驟7 判斷是否達到迭代的最大次數。若達到，則程序停止，輸出最優(yōu)解；若未達到，返回步驟2。

圖1 本文改進算法流程

3 仿真實驗與結果分析

為了驗證改進算法的性能，本文選取了TSPLIB測試庫中的部分案例(數據更新到2013年7月，網址為：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95)，使用Matlab編程，在CPU為i5- 430M、RAM為2GB的計算機上進行測試實驗，并對不同算法的求解結果進行分析和比較，實驗結果驗證了本文改進算法的有效性。實驗中選取了蟻群算法常用的一種參數取值的組合：m=n，α=1，β=5，ρ=0.1，Q=20，Nmax=100。

表1給出了五種算法分別在Oliver30、Eil51、Eil101和Ts225上進行20次獨立實驗的結果。其中，五種算法分別為：基本蟻群算法，基于文獻[17]信息素二次更新策略的蟻群(ACObasedonPheromonesDoubleUpdating,PDUACO)算法，基于改進信息素二次更新策略的蟻群(ACObasedonImprovedPheromonesDoubleUpdating,IPDUACO)算法、基于局部優(yōu)化策略的蟻群(ACObasedonLocalOptimization,LACO)算法以及本文提出的算法(IPDULACO)。

從表1可以看出，基于文獻[17]信息素二次更新策略的蟻群算法(PDUACO)和基于改進信息素二次更新策略的蟻群算法(IPDUACO)都獲得了Oliver30實例的已知最優(yōu)解，但在其他3個實例上，基于改進信息素二次更新策略的蟻群算法(IPDUACO)求得的最優(yōu)解更接近已知最優(yōu)解，其中在Eil51實例上相比PDUACO提高了2.22%，且所有實例獲得的平均值也更好，說明改進信息素二次更新策略使算法的性能得到了提高。此外，在4個TSP實例上，基于局部優(yōu)化策略的蟻群算法(LACO)獲得的最優(yōu)解和平均值都優(yōu)于基本蟻群算法，說明加入局部優(yōu)化策略后算法的全局尋優(yōu)能力得到了提高。同時加入兩種改進策略的基本蟻群算法(即本文提出的改進算法IPDULACO)在4個TSP實例上求得的最優(yōu)解的精度得到了進一步提高，其在Eil51實例上與已知最優(yōu)解的偏差(偏差表示所得最優(yōu)解與已知最優(yōu)解之間的偏離程度)縮小到0.8%，可見本文所提的兩種改進策略的有效性。

表1 不同算法求解結果比較

圖2給出了ACO、PDUACO、IPDUACO和IPDULACO四種算法優(yōu)化Oliver30問題的收斂曲線。從圖2中可以看出：本文改進算法(IPDULACO)在18代收斂到最優(yōu)解，基于改進信息素二次更新策略的蟻群算法(IPDUACO)也在50代收斂到最優(yōu)解，而基于文獻[17]信息素二次更新策略的蟻群算法(PDUACO)在65代才收斂，且收斂到的最優(yōu)解為426.60(Oliver30已知最優(yōu)解為423.74)。ACO算法雖然在10代收斂，但收斂到的最優(yōu)解質量最差。由此可見，在收斂到已知最優(yōu)解的前提下，本文改進算法的收斂速度更快。

圖2 四種算法求解Oliver30的收斂曲線

圖3給出了ACO和IPDULACO優(yōu)化Ts225問題的收斂曲線，ACO在95代收斂，而本文改進算法(IPDULACO)在82代即收斂，再次說明了本文改進算法具有更快的收斂速度，且收斂到的最優(yōu)值為130 955.48，精度也更高(ACO收斂到的最優(yōu)值為131 434.97)。

圖3 ACO和IPDULACO求解Ts225收斂曲線

為了進一步驗證本文改進算法(IPDULACO)的性能，首先將IPDULACO的實驗結果與求解TSP的4種改進ACO算法的實驗結果進行了縱向比較，然后又與求解TSP的2種粒子群算法和遺傳算法進行了縱向比較。表2給出了蟻群(ACO)算法[19]、蟻群算法驅動的遺傳算法(AntColonyGeneticAlgorithm,ACGA)[19]、基于啟發(fā)式遺傳信息的蟻群遺傳算法(HeuristicGeneticInformationbasedAntColonyGeneticAlgorithm,HGIACGA)[19]、新型蟻群算法(NewACO,NACO)[20]和本文改進算法(IPDULACO)在三組TSP分別運行10次的平均求解性能，其中偏差表示所得最優(yōu)解與已知最優(yōu)解之間的偏離程度。表2中ACO、ACGA、HGIACGA、NACO算法的結果來自文獻[20]。從表2可以看出，IPDULACO的求解性能優(yōu)于其他4種算法，偏差最小，說明IPDULACO具有較強跳出局部最優(yōu)的能力，而且平均值也最低，表明IPDULACO也具有較好的穩(wěn)定性。

表2 ACO、ACGA、HGIACGA、NACO和IPDULACO性能對比

表3給出了IPDULACO、離散粒子群(DiscretePSO,DPSO)算法[21]、自適應離散粒子群(Self-AdaptiveDPSO,SADPSO)算法[21]、遺傳算法(GA)在3組TSP上的實驗結果。其中DPSO、SADPSO算法的結果來自文獻[21]，GA的參數設置為：最大迭代次數Maxgen=n，交叉概率Pc=0.9，變異概率Pm=0.05。除了在Burma14問題上，本文改進算法的平均值高于SADPSO外，其他兩個問題本文改進算法獲得的最優(yōu)值和平均值都優(yōu)于所對比的3種算法。圖4為本文改進算法求得Eil51問題的最優(yōu)路徑圖。

表3 DPSO、SADPSO、GA和IPDULACO性能對比

圖4 IPDULACO求得Eil51最優(yōu)路徑

在與現有的幾種算法縱向比較后，又將本文改進算法與其他幾種常見的TSP求解算法進行了橫向比較，結果如表4所示。其中包括：改進貪婪算法(IMprovedGReedyAlgorithm,IMGRA)[22]、自適應離散粒子群算法(Self-AdaptiveDiscreteParticleSwarm,SADPSO)[21]、文獻[16]提出的動態(tài)調整選擇策略的改進蟻群算法(AntColonyAlgorithmwithDynamicTransition, 簡記為A16)和文獻[23]提出的基于粒子群參數優(yōu)化的改進蟻群算法(ImprovedAntColonyOptimizationAlgorithmbasedonParticleSwarmOptimization, 簡記為A23)。

表4 不同算法求解Eil51性能比較

從表4可以看出：5種算法求解Eil51問題，IPDULACO獲得的最優(yōu)解最接近已知最優(yōu)解，平均值除了比SADPSO略高外，比其他2種算法都低(IMGRA求解的平均值除外)，進一步說明了IPDULACO具有較強的全局搜索能力。

再用本文改進算法(IPDULACO)求解文獻[24]中的TSP，并和文獻[24]改進蟻群算法(ImprovedAntColonyOptimizationAlgorithm, 簡記為A24)求得的最優(yōu)解進行比較。14個城市的坐標分別為A(8，2)、B(0，4)、C(-1，6)、D(2，-1)、E(4，2)、F(6，0.5)、G(3，0)、H(10，3.7)、I(2.5，1.8)、J(-5，1)、K(7，0)、L(9，4)、M(11，3)、N(13，2)。實驗中取蟻群算法常用的一種參數取值的組合：m=n，α=1，β=5，ρ=0.1，Q=20，Nmax=100。圖5為兩種算法所得最優(yōu)路徑對比。

圖5 不同算法所得最優(yōu)路徑對比

圖5(a)為文獻[24]提出的改進蟻群算法求得的最優(yōu)路徑，最優(yōu)路徑為：A→I→B→C→J→D→G→E→F→K→N→M→H→L→A，最優(yōu)路徑長度為45.784 4；圖5(b)為IPDULACO求得的最優(yōu)路徑，最優(yōu)路徑為：A→F→G→I→B→C→J→D→E→K→N→M→H→L→A，最優(yōu)路徑長度為45.562 0，顯然IPDULACO的求解性能更優(yōu)，提高了0.222 4，進一步說明IPDULACO具有較強的跳出局部最優(yōu)的能力。

4 結語

本文針對蟻群算法收斂速度慢、容易陷入局部最優(yōu)解的缺陷，提出一種改進信息素二次更新局部優(yōu)化蟻群算法(IPDULACO)。對每次迭代后當前全局最優(yōu)路徑中路徑貢獻度大于給定的路徑貢獻閾值的子路徑進行信息素的二次更新，增大構成潛在最優(yōu)解的子路徑被選擇的概率，提高算法的收斂速度；同時，在算法中引入一種局部優(yōu)化策略來提高算法跳出局部最優(yōu)解的能力。在TSP上的仿真實驗也表明，改進的蟻群算法可以在迭代次數較少的情況下獲得小規(guī)模TSP的已知最優(yōu)解；對于較大規(guī)模TSP,改進算法可以在迭代次數較少的情況下獲得更精確的解。如何選取路徑貢獻度閾值以提高算法的魯棒性，以及如何提高求解大規(guī)模TSP實例最優(yōu)解的精度還需在今后作進一步研究。

)

[1]WILLIAMJC.迷茫的旅行商:一個無處不在的計算機算法問題[M].隨春寧,譯.北京:人民郵電出版社,2013:178-183.(WILLIAMJC.InPursuitoftheTravelingSalesman:MathematicsattheLimitsofComputation[M].SUICN,translated.Beijing:Posts&TelecomPress, 2013: 178-183.)

[2]GAREYMR,JOHNSONDS.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].NewYork:W.H.FreemanandCompany, 1979: 56-59.

[3]PADBERGMW,RINALDIG.Optimizationofa532-citysymmetricgenetictravelingsalesmanproblemsbybranchandcut[J].OperationResearchLetters, 1987, 6(1): 1-7.

[4]HELDM,KARPRM.Adynamicprogrammingapproachtosequencingproblems[J].JournaloftheSocietyforIndustrialandAppliedMathematics, 1962, 10(1): 196-210.

[5]APPLEGATED,BIXBYR,CHVATALV,etal.FindingcutsintheTSP(apreliminaryreport),TR95- 05 [R].Piscataway,NJ:CenterforDiscreteMathematics&TheoreticalComputerScience, 1995.

[6]JüNGERM,REINELTG,RINALDIG.Thetravelingsalesmanproblems[J].HandbooksinOperationsResearch&ManagementScience, 1995, 7(5): 225-230.

[7]BENTLEYJL.Fastalgorithmsforgeometrictravelingsalesmanproblem[J].ORSAJournalonComputing, 1992, 4(4): 387-411.

[8]AHMEDZH.Geneticalgorithmforthetravelingsalesmanproblemusingsequentialconstructivecrossoveroperator[J].InternationalJournalofBiometricsandBioinformatics, 2010, 3(6): 96-105.

[9]SONGCH,LEEK,LEEWD.ExtendedsimulatedannealingforaugmentedTSPandmulti-salesmanTSP[C]//Proceedingsofthe2003InternationalJointConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 2003: 2340-2343.

[10]GENDREAUM,LAPORTEG,SEMETF.Atabusearchheuristicfortheundirectedselectivetravelingsalesmanproblem[J].EuropeanJournalofOperationalResearch, 1998, 106(2/3): 539-545.

[11]CLEARM.Discreteparticleswarmoptimization,illustratedbythetravelingsalesmanproblem[M]//NewOptimizationTechniquesinEngineering.Berlin:Springer, 2004: 219-239.

[12]DORIGOM,GAMBARDELLALM.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransactionsonEvolutionaryComputation, 1997, 1(1): 53-66.

[13]COLORNIA,DORIGOM,MANIEZZOV.Distributedoptimizationbyantcolonies[C]//Proceedingsofthe1991EuropeanConferenceOnArtificialLife.Amsterdam:Elsevier, 1991: 134-142.

[14]DORIGOM,MANIEZZOV,COLORNIA.Theantsystem:optimizationbyacolonyofcooperatingagents[J].IEEETransactionsonSystems,Man,andCybernetics, 1996, 26(1): 29-41.

[15]STUTZLET,HOOSH.Improvementsontheantsystem:introducingMAX-MINantsystem[C]//Proceedingsofthe1998InternationalConferenceonArtificialNeuralNetworksandGeneticAlgorithms.Berlin:Springer, 1998: 245-249.

[16] 鄭松,侯迪波,周澤魁.動態(tài)調整選擇策略的改進蟻群算法[J].控制與決策,2008,23(2):225-228.(ZHENGS,HOUDB,ZHOUZK.Antcolonyalgorithmwithdynamictransitionprobability[J].ControlandDecision, 2008, 23(2): 225-228.)

[17] 吳華鋒,陳信強,毛奇凰,等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報,2013,34(4):165-170.(WUHF,CHENXQ,MAOQH,etal.ImprovedantcolonyalgorithmbasedonnaturalselectionstrategyforsolvingTSPproblem[J].JournalonCommunications, 2013, 34(4): 165-170.)

[18] 程畢蕓,魯海燕,徐向平,等.求解旅行商問題的改進局部搜索混沌離散粒子群優(yōu)化算法[J].計算機應用,2016,36(1):138-142,149.(CHENGBY,LUHY,XUXP,etal.Improvedlocal-search-basedchaoticdiscreteparticleswarmoptimizationalgorithmforsolvingtravelingsalesmanproblem[J].JournalofComputerApplications, 2016, 36(1): 138-142, 149.)

[19] 徐金榮,李允,劉海濤,等.一種求解TSP的混合遺傳蟻群算法[J].計算機應用,2008,28(8):2084-2087.(XUJR,LIY,LIUHT,etal.Hybridgeneticantcolonyalgorithmfortravelingsalesmanproblem[J].JournalofComputerApplications, 2008, 28(8): 2084-2087.)

[20] 張弛,涂立,王加陽.新型蟻群算法在TSP問題中的應用[J].中南大學學報(自然科學版),2015,46(8):2944-2949.(ZHANGC,TUL,WANGJY.Applicationofself-adaptiveantcolonyoptimizationinTSP[J].JournalofCentralSouthUniversity(ScienceandTechnology), 2015, 46(8): 2944-2949.)

[21] 張長勝,孫吉貴,歐陽丹彤.一種自適應離散粒子群算法及其應用研究[J].電子學報,2009,37(2):299-304.(ZHANGCS,SUNJG,OUYANGDT.Aself-adaptivediscreteparticleswarmoptimizationalgorithm[J].ActaElectronicaSinica, 2009, 37(2): 299-304.)

[22] 饒衛(wèi)振,金淳,陸林濤.考慮邊位置信息的求解ETSP問題改進貪婪算法[J].計算機學報,2013,36(4):836-850.(RAOWZ,JINC,LULT.Animprovedgreedyalgorithmwithinformationofedges’locationforsolvingtheeuclideantravelingsalesmanproblem[J].ChineseJournalofComputers, 2013, 36(4): 836-850)

[23] 李擎,張超,陳鵬,等.一種基于粒子群參數優(yōu)化的改進蟻群算法[J].控制與決策,2013,28(6):873-878.(LIQ,ZHANGC,CHENP,etal.Improvedantcolonyoptimizationalgorithmbasedonparticleswarmoptimization[J].ControlandDecision, 2013, 28(6): 873-878.)

[24] 李成兵,郭瑞雪,李敏.改進蟻群算法在旅行商問題中的應用[J].計算機應用,2014,34(S1):131-132,165.(LICB,GUORX,LIM.ApplicationofImprovedantcolonyalgorithmintravelingsalesmanproblem[J].JournalofComputerApplications, 2014, 34(S1): 131-132, 165.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(11371174),theFundamentalResearchFundsfortheCentralUniversities(1142050205135260,JUSRP51317B).

XU Kaibo, born in 1992, M. S. candidate. His research interests include optimization and control.

LU Haiyan, born in 1970, Ph. D., associate professor. Her research interests include combinatorial optimization, intelligent algorithm.

CHENG Biyun, born in 1992, M. S. candidate. Her research interests include optimization and control.

HUANG Yang, born in 1991, M. S. candidate. His research interests include optimization and control.

Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP

XU Kaibo, LU Haiyan*, CHENG Biyun, HUANG Yang

(SchoolofScience,JiangnanUniversity,WuxiJiangsu214122,China)

Concerning the drawbacks of the Ant Colony Optimization (ACO) algorithm such as low convergence rate and being easy to fall into local optimum solutions, an ACO algorithm based on Improved Pheromones Double Updating and Local Optimization (IPDULACO) was proposed. Double updating was performed on the pheromones of subpaths whose path contribution degrees to the current global optimal solution obtained by colony were bigger than the prescribed path contribution threshold. The selected probability of the subpaths which were used to constitute the potential optimal solution was increased and the convergence rate of the proposed algorithm was accelerated. Then, when the ant colony fell into the local optimal solution in the search process, the random insertion method was utilized to change the city sequences of the current local optimal solution in order to enhance the algorithm’s ability of jumping out of local optimal solution. The improved algorithm was applied to several classical Traveling Salesman Problem (TSP) instances in the simulation experiments. The experimental results show that, for small-size TSP instances, the IPDULACO can obtain the known optimal solution in less number of iterations. For relatively large-size TSP instances, the IPDULACO can obtain the optimal solution with higher accuracy in less number of iterations. Therefore, the IPDULACO has the stronger ability of searching for the global optimal solution and faster convergence rate, and it can be used for solving TSP effectively.

Traveling Salesman Problem (TSP); Ant Colony Optimization (ACO) algorithm; pheromones double updating; local optimization

2016- 12- 06;

2017- 03- 01。

國家自然科學基金資助項目(11371174)；中央高?；究蒲袠I(yè)務費專項資金資助項目(1142050205135260,JUSRP51317B)。

許凱波(1992—)，男，山西晉城人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制； 魯海燕(1970—)，女，山東淄博人，副教授，博士，主要研究方向：組合最優(yōu)化、智能算法； 程畢蕓(1992—)，女，安徽馬鞍山人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制；黃洋(1991—)，男，河南信陽人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制。

1001- 9081(2017)06- 1686- 06

10.11772/j.issn.1001- 9081.2017.06.1686

TP301.6

A