基于貪心邊的MMAS改進算法及在TSP中的應用

方潔

摘要：最大最小蟻群算法通過對信息素更新和限制的改進，有效提高收斂速度，但難以避免出現停滯并陷入局部最優的困境。基于貪心邊的MMAS改進算法規定一種新的搜索停滯狀態，設定不同等級貪心邊，并在停滯狀態下利用搜索過程中尋找到的貪心邊進行優先搜索。該算法使搜索能夠盡早地集中在有效邊進行，丟棄“無用”搜索，提高發現更優路徑的可能性。利用TSP標準實例進行測試，結果表明改進算法的最優解更加接近實際最優解，具有更高的全局尋優能力和更快的收斂速度。

關鍵詞：貪心邊；優先級；搜索停滯；最大最小蟻群算法；旅行商問題

DOIDOI：10.11907/rjdk.173153

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2018）008-0097-05

英文摘要Abstract：Through the update of pheromone and restriction improvement，MMAS can improve the speed of convergence effectively.However，it is difficult to avoid stagnation and falling into local optima.The improved MMAS algorithm based on greedy-edge defines a new search stagnation state and sets different levels of greedy-edges.When the new search stagnation state occurs，greedy-edges will be chosen.The algorithm focuses the search on the effective edges as early as possible，and discards the useless path.，thus the possibility of finding better path is improved.Experiments on data in TSPLIB show that the improved algorithm can get the optimal solution which is closer to the actual optimal solution，and has higher global optimization ability and faster convergence speed.

英文關鍵詞Key Words：greedy-edge； priority； search stagnation； MMAS； TSP

0 引言

蟻群算法是一種成功應用于多種NP-hard組合優化問題的方法，這種思想來源于真實蟻群的行為，特別是它們的覓食行為，螞蟻在尋找食物源時，會在其經過的路徑上釋放一種信息素，并能夠感知其它螞蟻釋放的信息素。利用信息素濃度大小表征路徑的遠近，螞蟻會以較大概率優先選擇信息素濃度較高的路徑，并釋放一定量的信息素，以增強該條路徑上的信息素濃度，形成一種正反饋作用，直至螞蟻找到一條從巢穴到食物源的最短路徑。

至今，蟻群算法已經成功應用于旅行商問題、車輛路徑問題[1]、智能裝載問題[2-3]等多個領域，取得了較好的實驗效果。然而蟻群算法也存在一些缺陷，特別是過早收斂、容易陷入局部最優解等。針對這些缺點，許多學者在基本蟻群算法（Ant Colony System，ACS）[4]基礎上提出了不同改進算法，如Ant-Q蟻群算法[5]僅對循環中最短路徑上的信息量作更新，并僅讓信息量大的路徑以較大的概率被選中；最大最小螞蟻系統（Max-Min Ant System，MMAS）[6]限定了信息素值的上下限，使各條路徑上的信息素保持在某個區間范圍內，從而避免算法過早收斂；李成兵等[7]提出的改進蟻群算法以輪盤賭的方式進行狀態轉移，并調整全局信息素的更新方式增強全局搜索能力；耿志強等[8]提出的基于混沌的MMAS算法利用混沌的遍歷特性產生一組較優路徑指導初始信息素的非均勻分布，運用混沌擾動的方法增強算法跳出局部最優的能力；王寶生等[9]提出基于邊緣初始化和自適應全局信息素的改進蟻群算法，具有較好的搜索最優解的能力，不會過早收斂。這些算法都一定程度提高了全局搜索能力，但不能避免停滯現象的出現，同時最優解的精度也有待進一步提高。

本文在MMAS的基礎上提出一種改進算法，對算法的搜索停滯狀態進重新定義，設置貪心邊及其優先級，分析不同貪心邊參數性能，并在該停滯狀態下優先在貪心邊進行搜索。根據優先級的高低進行選擇，更快、更集中地進行有效搜索。最后利用TSP標準實例進行實驗測試，結果表明該算法取得的最優解更加接近實際最優解，求解精度有較大提高，同時加快了收斂速度。

1 最大最小蟻群算法MMAS

旅行商問題即TSP問題，指給定一個城市的集合以及城市之間的旅行代價，尋找經過每個城市一次且僅一次，最終回到起始城市旅行代價最小的路徑。若將該問題構造成一個圖，則TSP問題可以抽象為尋找圖中最短哈密爾頓回路[10]。

為有效防止算法早熟和停滯，MMAS算法在ACS算法基礎上主要進行了以下兩方面的改進：

（1）信息素更新。

在迭代過程中采用最優方案，即每次迭代后僅對一只螞蟻經過的路徑增加信息素。ACS改進算法一般僅使用全局最佳方案（從第一次迭代至當前迭代，找到最好解決方案的螞蟻），MMAS則主要使用迭代最佳方案（即從本次迭代中找到最好解決方案的螞蟻）。在迭代最佳和全局最佳螞蟻中作出適當選擇可以提高搜索性能。當僅僅使用全局最佳螞蟻，搜索會很快集中到最終結果，更好的方案可能會被限制，容易陷入被低質量解決方案限制的危險，而選擇迭代最佳螞蟻則會降低這種危險，因為迭代最優的結果每次都可能不同。因此大多數路徑上的信息素都會增強，不會過早陷入局部最優。

通常，在MMAS中選擇混合的方案，即選擇迭代最佳螞蟻作為信息素更新的默認值，選擇全局最佳螞蟻用于一些固定次數的迭代。實驗證明搜索過程中增加全局最佳螞蟻用于信息素更新的動態混合策略是一種最優策略。因此，信息素更新遵循公式（3），其中Δτbestij=1/f（sbest），f（sbest）為迭代最佳路徑長度或全局最佳路徑長度[6]。

2 基于貪心邊的MMAS改進算法（MMAS_GE）

2.1 搜索停滯狀態處理

2.1.1 搜索停滯狀態判斷

文獻[11]描述的搜索停滯是指每次迭代中所有的螞蟻遵從相同路徑，不斷創建同樣的路徑，以至于更好的路徑不可能被找到。實際搜索過程中會出現迭代最優解持續保持不變的情況，這說明算法有可能已陷入某一局部最優解，繼續執行可能導致搜索停滯。為了避免出現停滯狀態，應提前采取相應措施使算法繼續向前推進。

在搜索停滯狀態中，每次迭代所有螞蟻遵從相同的路徑，MMAS_GE算法采取提前檢測的方法，設定一個限定值KeepMax=[螞蟻總數/2]，即一半及以上的螞蟻若遵從相同路徑且迭代最優解持續KeepMax代內保持不變時，判定該算法處于搜索停滯狀態。

2.1.2 貪心邊及其優先級設置

2.1.3 路徑選擇

當算法處于停滯狀態時，不再依據式（1）進行路徑選擇，需要對選擇規則進行調整。由于貪心邊中優先級較高的邊可能獲得較短的哈密爾頓路徑，因此路徑的優化選擇在優先級高的邊中進行。此外，由于TSP的最優解中絕對不含任何交叉線路的情況[12]，MMAS_GE算法針對貪心邊進一步篩選。

當出現所述停滯狀態時，整個搜索過程考慮以下兩點：

（1）搜索的起點。在優先級為1的邊中隨機選擇一個城市節點作為搜索的起點。

（2）下一個搜索的城市節點。螞蟻選擇下一個城市時依據貪心邊的優先級進行選定，優先選擇優先級高的邊所對應的城市結點。若依據降序在所有優先級為1～3的邊中沒有可選的城市結點，則在剩余未訪問的邊中選擇啟發信息最大的邊所對應的城市結點。同時，在可供選擇的貪心邊中選擇不交叉的線路，若該邊與已走過路徑交叉，則修改其優先級為0，繼續搜索。

由于螞蟻所走的路徑為一個哈密爾頓回路，因此在選擇下一個搜索的城市節點時，有可能出現路徑待選一端沒有滿足條件的城市節點，但路徑的起點端卻存在滿足條件的城市節點與其連接，這時需要將整段路徑反轉。舉例說明如下：某只螞蟻經過路徑為（a1，a2，…，ai-1，ai），選擇第i+1個訪問城市時，查找從ai出發的優先級為1的邊，若存在則篩選出不相交的邊，并通過輪盤賭算法選擇其中一個結點作為第i+1個節點；若不存在，并不是立即查找從ai出發優先級為2的邊，而是查找路徑另一端a1節點是否存在對應優先級為1的可選邊，存在則將該路徑反轉，即路徑為（ai，ai-1，…，a2，a1），第i+1個訪問的城市節點為與a1相連的可選節點；若兩端均不存在滿足條件的城市節點與其連接，則在從ai出發的優先級為2的邊中繼續查找，以此類推。

2.2 MMAS_GE算法步驟

算法的具體實現過程如下：

（1）算法參數和信息素的初始化，設定N_IT_COUNT為最大迭代次數，stopflag為搜索停滯標志量，初始為0（未停滯）。初始化每條邊的最小哈密爾頓長度為某一恒定較大值，且優先級為0。

（2）根據狀態轉移函數計算概率pkij（t），選擇下一個城市節點，搜索過程中不斷更新每條邊的最小哈密爾頓長度。此外，計算本次迭代取得迭代最優解的螞蟻數量。

（3）根據MMAS算法中的信息素更新原則進行更新后，跳到步驟（6）。

（4）進入迭代循環。每次迭代結束時進行搜索停滯狀態的判定，若stopflag=0，跳到步驟（2）；若stopflag=1，計算滿足條件的貪心邊并設置優先級，跳到步驟（5）。

（5）繼續迭代，m只螞蟻均優先在貪心邊中進行初始搜索城市的選取，并根據優先級的高低進行后續城市結點的選擇。搜索完成后，跳到步驟（3）。

（6）若迭代次數=N_IT_COUNT，輸出全局最優路徑，結束算法；否則轉步驟（4）繼續搜索，直至算法結束。

3 實驗仿真與分析

3.1 參數λ性能分析

為了考察參數λ對于算法效果的影響，并確定貪心邊的優先級，采用標準測試用例eil51和kroA100進行分析，參數設置如下：螞蟻個數m=n（城市個數），α=1.0，β=2.0，ρ=0.98，Pbest=0.05，每組螞蟻迭代n*100次，每個測試用例運行20次。

針對eil51和kroA100，分別取λ為-2、-1和0進行測試，根據目前所得實際最優路徑（以下稱最優解）進行比對，可得在3種參數情況下，最優解中貪心邊命中率（即最優解中屬于貪心邊的個數/最優解總邊數，如eil51最優解總邊數為51）見表1所示。

由表1可知，只有當λ取值為0時，才能在貪心邊中命中所有最優解的邊。此外，經過測試，當λ取值為3時，每次實驗的迭代及全局最優解中的邊均為貪心邊，使得搜索的可選范圍很廣，不能突出貪心邊的優勢，仍然不能有效地獲得全局最優解。所以MMAS_GE算法選取λ取值分別為0、1、2三個等級來設定貪心邊，既保證最優解中的邊都能在貪心邊中命中，又能有效利用貪心邊的優勢進行求解。

3.2 改進算法對最優解和收斂速度的影響

為了檢驗算法的正確性和有效性，從TSPLIB中選擇3個TSP實例eil51、kroA100和d198，利用C++語言編寫程序進行測試，并與最大最小蟻群算法MMAS進行比較。算法中主要參數設置同3.1節，每組螞蟻迭代n*100次，對各種算法測試20次求平均值。所得結果如表2所示。

由表2可以看出，在同樣參數情況下，MMAS_GE算法的平均值更接近最優解，且在城市規模較小的情況下能多次取得目前實際最優解。

此外，本文在MATLAB 7.0軟件上模擬兩種算法在eil51、kroA100和d198三個實例的運行情況，橫坐標軸為迭代次數，縱坐標軸為每次迭代的全局最優路徑長度。由圖1～圖3的進化曲線可以看出，eil51和kroA100兩種算法的收斂速度接近，但MMAS_GE算法求解精度更高，且隨著迭代次數的增加后期仍能不斷搜索到更優解。從d198的收斂曲線可以看出它的收斂速度高于MMAS，求解精度也更高。

3.3 與其它MMAS改進算法對比

文獻[8]提出的基于混沌的MMAS算法能在算法陷入停滯時利用Tent映射將信息素轉化為混沌變量，并運用混沌擾動的方法跳出局部最優解，具有較高的全局尋優成功率和較快的收斂速度。因此，利用上述3個標準TSP實例將改進后的算法與該算法進行比較。參數設置如下：m=40，α=1.0，β=2.0，ρ=0.95，Pbest=0.05，最大迭代次數100 000，每個測試用例運行20次。實驗結果如表3所示。

表3針對3個實例對比MMAS_GE、CMMAS和MMAS 3種算法，其中指標SR是文獻[8]提出的性能分析指標，稱為尋優成功率，表示成功運行次數SRN占總運行次數TRN的百分比。成功運行是指某次搜索達到期望值Optimal×（1+1.25%），其中Optimal為全局最優路徑長度，即要求誤差不超過1.25%。總運行次數TRN如前所述為20次。而本算法在分析時設定Optimal為截至目前該實例的實際最優解。

從表3可以看出，可以分別從尋優成功率、最優解、最差解和平均值進行分析：

（1）MMAS_GE算法的尋優成功率最高，對3個實例的尋優成功率均為100%，說明所有誤差均在1.25%以內，并且在d198中成功率相對于CMMAS提高了5%，相對于MMAS提高了20%。

（2）MMAS_GE算法的最優解和最差解的誤差最低。當城市規模小于等于100時，3種算法都能獲得最優解，但最差解均有較大提高，如eil51和kroA100兩個實例的最差解誤差MMAS_GE相比CMMAS分別降低了144%和0.43%，相比MMAS則分別降低了1.21%和073%；當城市規模大于100時，MMAS_GE在最優解和最差解上均表現出較好的性能，如在d198的測試中，最優解最接近實際最優解，誤差僅為0.05%，相比CMMAS和MMAS分別降低了0.06%和0.23%，而最差解誤差也分別降低了0.24%和0.67%。

（3）MMAS_GE算法的平均值精度也均有大幅度提升，3個標準實例的精度相比MMAS算法分別提高了0.26%、0.31%和0.15%。d198的測試結果顯示，MMAS_GE與CMMAS算法的性能不相上下，均能取得較優的平均值。

綜上可知，當螞蟻數量小于或等于城市數量時，MMAS_GE算法均能取得較好的性能，所以適當提前處理搜索停滯，減少“無用邊”的搜索，可以縮小搜索范圍，提高搜索精度。

4 結語

本文提出的MMAS_GE算法是一種改進的MMAS算法，在信息素的更新上采用MMAS算法更新規則，但對搜索停滯狀態重新進行約定，并設定3種級別的貪心邊在停滯狀態下進行優先搜索。從測試結果可知，該算法能讓搜索較早地集中在優先級較高的貪心邊中進行，避免了無用搜索，從而提高精度，特別是最優解的精度。但對類似d198這種城市規模較大的實例來說，處理時間較長，這是需要進一步解決的問題，今后可以考慮將固定順序多次出現的城市作為一個整體，進一步縮小城市整體規模，達到降低算法復雜性、提高算法性能的目的。

參考文獻：

[1] 謝驪玲，宋彥斌，楊坦，等.求解車輛路徑問題的改進MMAS算法[J].計算機技術與發展，2016，26（3）：27-30.

[2] 田冉，孫林夫，唐慧佳，等.基于最大最小蟻群算法的多卸載點車載裝箱模型研究[J].重慶交通大學學報：自然科學版，2016，35（2）：156-162.

[3] 葛瑋，徐衛紅，程海水.基于最大最小蟻群算法的智能裝載方法[J].山東農業大學學報：自然科學版，2014，45（3）：366-371.

[4] DORIGO M，GAMBADELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

[5] DORIGO M，GAMBADELLA L M .A study of some properties of Ant-Q[C].Proceedings of the 4th International Conference on Parallel Problem Solving from Nature，1996：656-665.

[6] STUTZLE T，HOOS H.Max-min ant system[J].Future Generation Computer Systems，2000，16（8）：889-914.

[7] 李成兵，郭瑞雪，李敏.改進蟻群算法在旅行商問題中的應用[J].計算機應用，2014，34（S1）：131-132+165.

[8] 耿志強，邱大洪，韓永明.基于混沌的MMAS算法及其在旅行商問題中的應用[J].計算機工程，2016，42（3）：192-197.

[9] 王寶生，屈寶存.蟻群算法在求解TSP問題中的改進研究[J].電子設計工程，2014，22（22）：14-18.

[10] 姚金濤，祝勝林，孔宇彥.具有壽命估算的最大-最小螞蟻系統[J].計算機工程與應用，2011，47（24）：27-29+50.

[11] DORIGO M，MANIEZZO V，COLRNI A.The ant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man and Cybernetics，1996，26（1）：29-41.

[12] 侯文靜，馬永杰，張燕，等.求解TSP的改進蟻群算法[J].計算機應用研究，2010，27（6）：2087-2089.

（責任編輯：江 艷）