方潔

摘要：最大最小蟻群算法通過對信息素更新和限制的改進，有效提高收斂速度，但難以避免出現(xiàn)停滯并陷入局部最優(yōu)的困境?；谪澬倪叺腗MAS改進算法規(guī)定一種新的搜索停滯狀態(tài)，設(shè)定不同等級貪心邊，并在停滯狀態(tài)下利用搜索過程中尋找到的貪心邊進行優(yōu)先搜索。該算法使搜索能夠盡早地集中在有效邊進行，丟棄“無用”搜索，提高發(fā)現(xiàn)更優(yōu)路徑的可能性。利用TSP標(biāo)準(zhǔn)實例進行測試，結(jié)果表明改進算法的最優(yōu)解更加接近實際最優(yōu)解，具有更高的全局尋優(yōu)能力和更快的收斂速度。

關(guān)鍵詞：貪心邊；優(yōu)先級；搜索停滯；最大最小蟻群算法；旅行商問題

DOIDOI：10.11907/rjdk.173153

中圖分類號：TP312

文獻標(biāo)識碼：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.

英文關(guān)鍵詞Key Words：greedy-edge； priority； search stagnation； MMAS； TSP

0 引言

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

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

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

1 最大最小蟻群算法MMAS

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

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

（1）信息素更新。

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

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

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

2.1 搜索停滯狀態(tài)處理

2.1.1 搜索停滯狀態(tài)判斷

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

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

2.1.2 貪心邊及其優(yōu)先級設(shè)置

2.1.3 路徑選擇

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

當(dāng)出現(xiàn)所述停滯狀態(tài)時，整個搜索過程考慮以下兩點：

（1）搜索的起點。在優(yōu)先級為1的邊中隨機選擇一個城市節(jié)點作為搜索的起點。

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

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

2.2 MMAS_GE算法步驟

算法的具體實現(xiàn)過程如下：

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

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

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

（4）進入迭代循環(huán)。每次迭代結(jié)束時進行搜索停滯狀態(tài)的判定，若stopflag=0，跳到步驟（2）；若stopflag=1，計算滿足條件的貪心邊并設(shè)置優(yōu)先級，跳到步驟（5）。

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

（6）若迭代次數(shù)=N_IT_COUNT，輸出全局最優(yōu)路徑，結(jié)束算法；否則轉(zhuǎn)步驟（4）繼續(xù)搜索，直至算法結(jié)束。

3 實驗仿真與分析

3.1 參數(shù)λ性能分析

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

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

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

3.2 改進算法對最優(yōu)解和收斂速度的影響

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

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

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

3.3 與其它MMAS改進算法對比

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻：

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

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

[3] 葛瑋，徐衛(wèi)紅，程海水.基于最大最小蟻群算法的智能裝載方法[J].山東農(nóng)業(yè)大學(xué)學(xué)報：自然科學(xué)版，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] 李成兵，郭瑞雪，李敏.改進蟻群算法在旅行商問題中的應(yīng)用[J].計算機應(yīng)用，2014，34（S1）：131-132+165.

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

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

[10] 姚金濤，祝勝林，孔宇彥.具有壽命估算的最大-最小螞蟻系統(tǒng)[J].計算機工程與應(yīng)用，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].計算機應(yīng)用研究，2010，27（6）：2087-2089.

（責(zé)任編輯：江 艷）