改進(jìn)蟻群算法在TSP 問題中的應(yīng)用

徐書揚(yáng)，王海江

（浙江科技學(xué)院，杭州310023）

0 引言

蟻群算法是一種于1992 年由文獻(xiàn)[1]用于尋找最優(yōu)路徑的經(jīng)典概率型算法。與其他啟發(fā)式算法相比，蟻群算法具有良好的魯棒性（可改進(jìn)方向多，適用于多種問題的解決）以及優(yōu)越的全局搜索能力（蟻群算法往往以全局最優(yōu)為目標(biāo)解決問題）。因此，蟻群算法在多個(gè)領(lǐng)域中得以應(yīng)用，例如：區(qū)域建設(shè)[2]、路徑規(guī)劃[3-6]、影像測量[7]、調(diào)度管理[8-9]等。然而，蟻群算法也同樣存在一些不足之處，例如：在處理信息量較大的問題時(shí)迭代速度過慢，算法易陷入局部最優(yōu)而錯(cuò)過最優(yōu)解，對(duì)參數(shù)的設(shè)置有很高的要求，錯(cuò)誤的參數(shù)設(shè)置容易導(dǎo)致結(jié)果誤差過大等[10-11]。

針對(duì)傳統(tǒng)蟻群算法存在的問題，不少學(xué)者提出蟻群算法的改進(jìn)方案來解決蟻群算法本身的缺陷。例如，在TSP（Traveling Salesman Problem）問題的解決中，黃澤斌[12]曾提出利用K-近鄰分區(qū)方法對(duì)大規(guī)模TSP問題進(jìn)行聚類分區(qū)，然后利用蟻群算法對(duì)每個(gè)子區(qū)域進(jìn)行最優(yōu)化求解，最后再將連接這些子區(qū)域之間距離最近的點(diǎn)連接起來實(shí)現(xiàn)TSP 問題的求解，該算法相較于傳統(tǒng)算法有更快的收斂速度，并且在處理信息量較大的圖中有更小的算法復(fù)雜度，節(jié)約了解決問題的時(shí)間成本。但是，連接兩個(gè)子區(qū)域的方式為尋找子區(qū)域之間距離最近的點(diǎn)將其相連，意味著連接兩個(gè)子區(qū)域之間的路徑有且僅有一條，從而降低了算法探尋更優(yōu)路徑的可能性，使得結(jié)果易產(chǎn)生較大的偏差。在點(diǎn)與點(diǎn)的路徑規(guī)劃問題中俞燁[13]曾提出啟發(fā)式因子的改進(jìn)方案，該方案令啟發(fā)式因子既考慮到下一步距離最近的結(jié)點(diǎn)，也考慮到下一步所到結(jié)點(diǎn)距離終點(diǎn)的距離，從而在圖像信息量較小時(shí)一定程度上避免了算法陷入局部最優(yōu)，也加快了算法初期的收斂速度。但是這樣的改進(jìn)策略僅適用于信息量較小的圖，當(dāng)圖中信息量較大時(shí)，對(duì)下一結(jié)點(diǎn)到終點(diǎn)距離的考慮反而會(huì)是干擾算法收斂的因素。Stützle T[14]曾提出最大-最小蟻群系統(tǒng)的概念，在每次迭代中僅更新最優(yōu)路徑上的信息素，此方法加快了算法收斂的速度，但是同時(shí)也增大了算法陷入局部最優(yōu)的可能。

上述算法一定程度上解決了蟻群算法的種種弊端，在某一特定場合下比起傳統(tǒng)蟻群算法有著更好的適用性。但是在非特定情況下或多或少存在一些弊端。本文以TSP 問題的討論為基，對(duì)蟻群算法做出改進(jìn)，以全局最優(yōu)為目標(biāo)，降低結(jié)果陷入局部最優(yōu)的概率，提高蟻群算法求解結(jié)果的精確度。在本問題的討論中，蘇曉琴[15]曾提出根據(jù)時(shí)間的推進(jìn)改進(jìn)信息迭代方案，使得算法能更快的收斂，這樣的改進(jìn)一定程度上能提高算法的求解精度，但是依舊未能解決算法易陷入局部最優(yōu)的情況。黃澤斌[12]曾提出用近鄰分區(qū)的方法來提高算法的求解精度，但是這樣的方法僅適用于大規(guī)模求解TSP 問題。在TSP 問題的解決中上述算法相較于傳統(tǒng)蟻群算法有著明顯的優(yōu)勢，但是，仍未解決蟻群算法的一大弊端：易陷入局部最優(yōu)。本文提出一種蟻群算法的改進(jìn)方案，使得算法能一定程度上避免陷入局部最優(yōu)的情況，提高算法整體的求解精度。

1 TSP問題和蟻群算法

1.1 TSP問題的描述

TSP 問題又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。它描述了以下場景：有一名旅行商人要拜訪各個(gè)城市，城市的數(shù)量為n，限制條件為每個(gè)城市僅拜訪一次且所有城市必須都需要拜訪，優(yōu)化目標(biāo)為使得在拜訪完所有城市并最終回到起點(diǎn)的情況下旅行商人走過的總路徑長度最短。經(jīng)典的TSP 問題中點(diǎn)與點(diǎn)之間的路徑長度為點(diǎn)與點(diǎn)之間的直線距離。本文將改進(jìn)后的蟻群算法應(yīng)用于TSP 問題的解決中，減少蟻群算法易陷入局部最優(yōu)的情況，使得TSP 問題的求解有更高的精確度。

1.2 蟻群算法的描述

蟻群算法的思想來源于自然界螞蟻覓食，螞蟻在尋找食物源時(shí)，會(huì)在路徑上留下螞蟻獨(dú)有的路徑標(biāo)識(shí)——信息素，螞蟻會(huì)感知其他螞蟻在各條路徑上留下的信息素，并根據(jù)各條路徑上的信息素濃度來選擇之后要走的路，路徑上留有的信息濃度越高，則螞蟻更傾向于選擇該路徑。在螞蟻選擇某條路徑后也會(huì)在改路徑上留下信息素吸引更多螞蟻選擇該路徑，隨著時(shí)間的推移，信息素濃度不斷增大，螞蟻選擇路徑的概率也隨之增高，由此形成了正反饋機(jī)制。由于蟻群算法的正反饋性，因此蟻群算法也屬于增強(qiáng)型學(xué)習(xí)算法的其中一種。

對(duì)于TSP 問題，設(shè)蟻群中螞蟻的數(shù)量為m，結(jié)點(diǎn)的數(shù)量為n，結(jié)點(diǎn)i 與結(jié)點(diǎn)j 之間的歐式距離為dij(t)，t 時(shí)刻結(jié)點(diǎn)i 與結(jié)點(diǎn)j 之間相連接的路徑上的信息素濃度為cij。初始時(shí)刻，螞蟻放置在不同結(jié)點(diǎn)里，且各結(jié)點(diǎn)連接路徑上的信息素濃度相同[13]，然后螞蟻按一定的概率選擇路線。不妨將Pk ij(t)設(shè)為t 時(shí)刻螞蟻k 從結(jié)點(diǎn)i 轉(zhuǎn)移到結(jié)點(diǎn)j 的概率?！拔浵乀SP”策略收到兩方面的左右，首先是訪問某結(jié)點(diǎn)的概率，這個(gè)概率的大小依賴于其他螞蟻釋放的信息素濃度。所以定義：

式中，nkij(t)為啟發(fā)函數(shù)，表示螞蟻從結(jié)點(diǎn)i 轉(zhuǎn)移到結(jié)點(diǎn)j 的概率；allowk為螞蟻k 下一步可轉(zhuǎn)移結(jié)點(diǎn)的集合，隨著時(shí)間的推移，allowk儲(chǔ)存的元素?cái)?shù)量會(huì)減小，最終會(huì)變?yōu)榭占?。a 為信息素重要程度因子。

與實(shí)際情況類似的一點(diǎn)是：隨著時(shí)間的推移，殘留在路徑上的信息素會(huì)逐漸揮發(fā)，螞蟻在經(jīng)過路徑時(shí)殘留的信息素量也會(huì)逐漸等同于信息素?fù)]發(fā)量，最終使信息素殘留量趨于穩(wěn)定。令α表示信息素?fù)]發(fā)程度，那么所有螞蟻遍歷完所有結(jié)點(diǎn)之后，各路徑上的信息素殘留量的數(shù)學(xué)表達(dá)式如下：

Δ為所有螞蟻在結(jié)點(diǎn)i 與結(jié)點(diǎn)k 連接路徑上釋放信息素而增加的信息素濃度，通常情況下：

式中，Q 為路徑信息素常量，l 為第k 只螞蟻所經(jīng)過路徑的總長度。

2 蟻群算法的改進(jìn)

2.1 初始信息素濃度的賦值

在傳統(tǒng)蟻群算法中，各條路徑上的初始信息素濃度相等，這意味著在第一次迭代時(shí)各個(gè)結(jié)點(diǎn)對(duì)螞蟻有相同的吸引力，這樣會(huì)造成以下兩個(gè)弊端[13]：

（1）初始信息素的濃度不具有指導(dǎo)性，使得算法收斂速度過慢。

（2）前幾次迭代螞蟻有概率向錯(cuò)誤的路徑轉(zhuǎn)移，信息素在錯(cuò)誤的路徑上殘留，導(dǎo)致算法易陷入局部最優(yōu)。

為了解決以上兩個(gè)問題，本文對(duì)信息素濃度賦以合理的初值，確保算法向正確的方向收斂。初始信息素濃度的具體數(shù)學(xué)表達(dá)式如下：

其中，k0為常數(shù)，確保各條路徑上初始信息素濃度在合理的范圍內(nèi)，dij為結(jié)點(diǎn)i 與結(jié)點(diǎn)j 的歐幾里得距離（直線距離），τij為連接結(jié)點(diǎn)i 與結(jié)點(diǎn)j 的路徑的初始信息素濃度。dij與τij呈反比關(guān)系，意味著初次迭代中距離越短的路徑對(duì)螞蟻有越強(qiáng)的吸引力，使各條路徑上的初始信息素濃度在算法收斂的過程中有著合理的導(dǎo)向性，增大了最優(yōu)路徑被選擇的概率。一定程度上加快了算法的收斂速度并避免陷入局部最優(yōu)的情況。

2.2 信息素的更新策略

由于蟻群算法的正反饋機(jī)制，隨著時(shí)間的推移，蟻群算法會(huì)逐漸收斂，各條路徑上的信息素濃度更多的集中在當(dāng)前最優(yōu)路徑上，使得每次螞蟻所選擇各條路徑的概率趨于穩(wěn)定，此時(shí)容易忽略潛在的最優(yōu)路徑，那么便有了陷入局部最優(yōu)的可能。為了增強(qiáng)算法的全局搜索能力，減少局部最優(yōu)發(fā)生的概率，需要提出一種更合理的信息更新策略。在迭代次數(shù)較小時(shí)，需要保證螞蟻在路徑上留下信息素濃度足夠高，以確保迭代初期算法能更快的收斂，而當(dāng)算法收斂到一定程度時(shí)，如果多次迭代中算法所求得最優(yōu)路徑長度一直未發(fā)生變化，那么算法既有可能已經(jīng)得到了正確結(jié)果，也有可能陷入局部最優(yōu)得到了有一定偏差的結(jié)果。此時(shí)為了避免算法陷入局部最優(yōu)，需要適當(dāng)增加信息素?fù)]發(fā)量以及減小螞蟻?zhàn)哌^路徑留下的信息素量，避免信息素過于集中，使得螞蟻能有更大概率去探索潛在的最優(yōu)路徑，提高算法的全局搜索能力。為方便算法的描述，給出如下定義：

定義如果存在某個(gè)時(shí)間節(jié)點(diǎn)T0，在T0之前的固定時(shí)長范圍內(nèi)，算法所探索的最優(yōu)路徑未發(fā)生變化，則稱該時(shí)間結(jié)點(diǎn)T0為信息素發(fā)散點(diǎn)。

每次迭代信息素更新的具體數(shù)學(xué)表達(dá)式如下：

式中，τij為連接結(jié)點(diǎn)i 與結(jié)點(diǎn)j 的路徑上的信息素濃度，Δτk ij為本次迭代中螞蟻k 在路徑上留下的信息素量，ρ為信息素?fù)]發(fā)比率，a,b 為常數(shù)，控制當(dāng)時(shí)間t 在過了信息素發(fā)散點(diǎn)后信息素的增加量和揮發(fā)量。

2.3 信息素矩陣的重置

盡管式（5）和文獻(xiàn)[15]所給出的信息素更新方案能一定程度上避免陷入局部最優(yōu)，但是并不能完全排除陷入局部最優(yōu)的可能，為了更大程度上避免陷入局部最優(yōu)的可能，我們?cè)谶@里引入了熔斷機(jī)制——當(dāng)時(shí)間達(dá)到信息素發(fā)散點(diǎn)后的一段固定時(shí)間內(nèi)，如果最優(yōu)路徑并沒有發(fā)生變化，則將信息素矩陣按式（4）的方式重新進(jìn)行賦值。

2.4 改進(jìn)蟻群算法的具體流程

圖1 改進(jìn)后蟻群算法流程圖

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

為對(duì)改進(jìn)后蟻群算法的有效性與合理性進(jìn)行驗(yàn)證，在五組結(jié)點(diǎn)位置坐標(biāo)互不相同的平面圖上通過MATALB 2018b 進(jìn)行編程，用改進(jìn)后的算法與傳統(tǒng)蟻群算法進(jìn)行比對(duì)。初始參數(shù)如下：α=1，β=5，ρ=0.1，Nmax=800，T=70，m=6，a=0.02，b=0.02，k0=100。

按以上參數(shù)分別代入改進(jìn)后蟻群算法與傳統(tǒng)蟻群算法，對(duì)每種情況分別求解1000 次求得結(jié)果如表1 所示。在得到表1 所示結(jié)果后對(duì)兩種算法的正確收斂情況和平均路徑長度減少情況進(jìn)行比對(duì)后求得結(jié)果如表2 所示。

表1 兩種算法正確收斂率與絕對(duì)誤差值表

表2 算法正確收斂增加率與絕對(duì)誤差值減少率表

對(duì)比五種不同情況下的改進(jìn)后蟻群算法與傳統(tǒng)蟻群算法的正確收斂率和絕對(duì)誤差，我們可以發(fā)現(xiàn)在相同的參數(shù)設(shè)置下改進(jìn)后的蟻群算法能更好地規(guī)避局部收斂的情況，增加算法正確收斂的比率，從而大大減小求解誤差，得到更精確的答案。

4 結(jié)語

通過對(duì)蟻群算法的改進(jìn)，使得蟻群算法在解決TSP 問題的過程中能更有效地規(guī)避算法陷入局部收斂的情況，提高算法的全局搜索能力，從而提高結(jié)果求解的精確度。然而，在本文對(duì)算法的改進(jìn)中要求足夠多的迭代次數(shù)以判別算法可能陷入局部收斂的情況，這是采用本文提出的改進(jìn)方法的局限性。另外，本文對(duì)算法引入了新的參量，對(duì)這些參量賦以不同的值會(huì)對(duì)結(jié)果產(chǎn)生不同程度的影響，如何這些參數(shù)設(shè)置不當(dāng)，會(huì)使得算法的全局搜索能力大大下降。因此，合理設(shè)置這些參數(shù)的值成為了本文算法應(yīng)用的一個(gè)難點(diǎn)。但總體來說，本文提出的改進(jìn)蟻群算法能很大程度上克服蟻群算法易陷入局部最優(yōu)的弊端，在求解諸如TSP 問題之類的最短路徑問題中有較好的適用性。