基于貪心邊的MMAS改進(jìn)算法及在TSP中的應(yīng)用

方潔

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

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

DOIDOI：10.11907/rjdk.173153

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：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)化問題的方法，這種思想來源于真實(shí)蟻群的行為，特別是它們的覓食行為，螞蟻在尋找食物源時(shí)，會(huì)在其經(jīng)過的路徑上釋放一種信息素，并能夠感知其它螞蟻釋放的信息素。利用信息素濃度大小表征路徑的遠(yuǎn)近，螞蟻會(huì)以較大概率優(yōu)先選擇信息素濃度較高的路徑，并釋放一定量的信息素，以增強(qiáng)該條路徑上的信息素濃度，形成一種正反饋?zhàn)饔?，直至螞蟻找到一條從巢穴到食物源的最短路徑。

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

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

1 最大最小蟻群算法MMAS

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

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

（1）信息素更新。

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

通常，在MMAS中選擇混合的方案，即選擇迭代最佳螞蟻?zhàn)鳛樾畔⑺馗碌哪J(rèn)值，選擇全局最佳螞蟻用于一些固定次數(shù)的迭代。實(shí)驗(yàn)證明搜索過程中增加全局最佳螞蟻用于信息素更新的動(dòng)態(tài)混合策略是一種最優(yōu)策略。因此，信息素更新遵循公式（3），其中Δτbestij=1/f（sbest），f（sbest）為迭代最佳路徑長(zhǎng)度或全局最佳路徑長(zhǎng)度[6]。

2 基于貪心邊的MMAS改進(jìn)算法（MMAS_GE）

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

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

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

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

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

2.1.3 路徑選擇

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

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

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

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

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

2.2 MMAS_GE算法步驟

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真與分析

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

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

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

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

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

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

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

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

3.3 與其它MMAS改進(jìn)算法對(duì)比

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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