求解旅行商問題的改進k-opt遺傳算法

趙 濤,葉志偉, 宗欣露, 潘 虎

(湖北工業大學計算機學院, 湖北 武漢 430068)

旅行商問題(travelling salesman problem,TSP)是組合優化領域的經典問題。其可描述為一個商人從任意城市出發,不重復不遺漏地訪問每一個城市,最后返回出發地,其目標是找出一條包含所有城市的最短路徑。TSP問題是一個NP問題,對車輛路徑、網絡路由和車間調度等領域有重要參考價值。許多學者深入研究并提出了線性規劃、動態規劃、分支定界和k-opt等傳統方法,這些方法在小規模TSP問題中能獲得較優的求解方案。隨著數據規模逐漸增大,上述方法在中大規模TSP問題求解時容易陷入局部最優解,且時間復雜度也隨之增加。針對中大規模TSP問題,群智能算法如蟻群優化算法(ACO)[1-2]、粒子群優化算法(PSO)[3]、模擬退火算法(SA)[4]和遺傳算法(GA)[5]等能在可期待的時間范圍內獲得可接受的解決方案,因此被更多的學者關注。

最近,謝聰[6]提出一種改進離散蝴蝶優化算法,利用貪婪策略初始化種群,結合2-opt方法、4-opt方法(雙橋實驗)和模擬退火提升算法尋優能力,但引入雙橋實驗使得算法時間復雜度很高。Karuna和Kusum[7]在灰狼優化算法(grey wolf optimizer,GWO)中引入漢明距離使其適用于組合優化問題,利用2-opt方法增強局部尋優能力。Zhang[8]在離散布谷鳥搜索算法中利用k-means算法將中大規模TSP問題劃分為多個小規模TSP問題,以此來加速中大規模TSP問題的運行效率。但由于不同規模城市之間缺乏交互能力,使得最終的求解效果較差。Zhang和Yang[9]提出一種基于麻雀搜索算法(sparrow search algorithm, SSA)的離散麻雀搜索算法(discrete sparrow search algorithm, DSSA),利用麻雀的分工作業機制和全局擾動策略平衡算法的探索和開發能力,提高了算法跳出局部最優解的能力,同時利用2-opt方法增強局部搜索能力,取得了比離散灰狼算法更好的效果。k-opt方法或其變形方法在上述算法均得到有效利用。

與此同時,許多處理連續型優化問題的新型算法在探索方面獲得極大優勢,而處理連續性問題的算法難以完全適用于離散優化問題。因此,針對離散問題的局部優化算子被越來越多的學者關注,針對TSP問題的k-opt方法成為該問題在局部優化的首先方案。Osaba等人[10]動態化調整離散蝙蝠算法,其中2-opt和3-opt方法分別用于短距離和長距離優化,該操作能夠有效地緩解算法陷入局部最優,從而根據種群個體潛力挖掘更優方案;Huang等人[11]同樣在離散青蛙跳躍算法引入2-opt方法優化精英個體,在擾動因子的基礎上強化算法搜索能力;Ahmet等人[12]在樹種算法中加入大量交換、逆轉和插入等擾動因子擴大全局探索能力,最終仍然通過2-opt方法局部搜索;Zhong等人[13]在離散鴿群優化算法中定義逆運算符、塊插入運算符和交換運算符等擾動因子加強全局探索,采用模擬退火算法、2-opt方法和3-opt方法作為局部搜索因子,既能保證種群多樣性,又能確保每個個體方案的優質性。

上述引入k-opt方法的算法,其算法時間復雜度較高。針對k-opt方法的高時間復雜度問題,本文優化原始k-opt方法提出一種求解TSP問題的改進遺傳算法。一方面,利用改進遺傳算法的交叉變異機制(交換、逆轉、插入)進行全局搜索,融合深度搜索、分層結構和禁忌表等策略強化全局搜索能力;另一方面,引入改進的k-opt方法增強局部搜索能力。算法的探索和開發能力在該機制下均得到增強。最后通過實驗證明該算法能夠高效地求解TSP問題,同時獲得解的質量較佳。

1 旅行商問題

旅行商問題可表示為一個無向圖G=(S,E)。其中,S={1,2,…,N}表示頂點集,E為邊集,邊eij∈E,(i,j∈S,i≠j)。設cij為eij的距離,決策變量

該問題的優化目標如下:

s.t.∑j≠ixij=∑i≠jxji=1,i∈S

∑i≠jxij≤|V|-1,V?Sxij∈{0,1},i,j∈S

其中,|V|表示集合S中的頂點個數。第一個約束條件表示每個頂點僅和兩條邊連接,第二個約束條件表示不會產生任何一條子回路。式(2)即本文需要優化的目標,該問題是一個典型的組合優化問題,當前沒有確定的算法能在多項式時間范圍內找到全局最優解。

2 k-opt方法及其改進

針對TSP問題,Lin[14]在1973年提出k-opt方法優化當前路徑。該方法簡單有效,能在局部范圍內根據當前解尋找更優解,但求解效率受數據規模影響較大。本文改進原始k-opt方法提高局部搜索運行效率。

2.1 原始2-opt和3-opt方法

圖1為2-opt優化過程,該方法選擇兩個不相鄰的點i、j,根據下式尋找更短路徑。

D(i,i+1)+D(j,j+1)>D(i,j)+D(i+1,j+1)

其中D(i,j)表示i、j兩點之間的距離。若條件成立,則逆轉序列L(i+1,j)。其中L(i,j)表示現有路徑中起點為i終點為j的路徑序列。通過對現有序列不斷優化,最終構建一個更短序列。同理,圖2為3-opt優化過程,該方法選擇三個不相鄰的點i、j、k,根據下式優化當前路徑。若條件成立,則逆轉序列L(j+1,k)。

D(i,i+1)+D(j,j+1)+D(k,k+1)>D(i,k)+D(i+1,j+1)+D(j,k+1)

Helsgaun[15]系統地討論了k-opt方法中不同k取值的優缺點。2-opt和3-opt方法是基于貪心搜索的優化過程(圖1、2),因此以上方法也會繼承貪心搜索的缺點,即最終導致陷入局部最優解。同時,2-opt和3-opt方法的時間復雜度和數據規模息息相關。理論上,2-opt方法逆轉序列次數最多為O(n2),3-opt方法逆轉序列次數最多為O(n3)。

圖1 2-opt方法優化過程

圖2 3-opt方法優化過程

2.2 改進的2-opt和3-opt方法

為緩解2-opt和3-opt方法過早地陷入局部最優解,提出改進的2-opt和3-opt方法。在改進的2-opt方法中,根據當前節點i找出與自身不相鄰的所有后續節點的集合J,構造集合如下:

Diff2=D(i,i+1)+

D(J,J+1)-D(i,J)-D(i+1,J+1)

其中,集合Diff2表示所有后續節點與當前節點i發生序列交換后的差異。在集合Diff2中找出最大值max_S2,若條件max_S2>0成立,則逆轉max_S2對應的節點j和節點i之間的序列,即逆轉當前序列L(i+1,j)。在改進的3-opt方法中,根據當前節點i,j找出與自身不相鄰的所有節點的集合K,構造集合Diff3

式中：g(α),h(1-α)為分配函數，滿足以下條件：① g(0)=0,g(1)=1,h(0)=0,h(1)=0；② 0≤g(α)≤1,0≤h(1-α)≤1,α∈[0,1]；③ g(α),h(1-α)隨α的增大，嚴格遞增。

Diff3=D(i,i+1)+D(j,j+1)+D(K,K+1)-

D(i,K)-D(i+1,j+1)-D(j,K+1)

與原始2-opt方法相比,改進后的2-opt算法逆轉序列次數不超過O(n);改進后的3-opt方法逆轉序列次數不超過O(n/2)。其次,對于任意節點,改進后的2-opt方法最多逆轉序列1次,而原始的2-opt算法最多逆轉序列n-2次。

3 改進的k-opt遺傳算法

本文提出一種改進的k-opt遺傳算法求解TSP問題。首先,在原始遺傳算法中融入深度搜索、分層結構和禁忌表等機制強化遺傳算法尋優能力。然后,利用改進的k-opt方法加速算法局部搜索運行效率和盡量避免算法陷入早熟問題(圖3)。

圖3 改進的k-opt遺傳算法流程

在改進的遺傳算法中,首先通過隨機編碼初始化種群個體,然后以距離作為適應度函數計算不同個體的適應度值。同時,采用改進的k-opt方法初始化,使種群個體獲得較優解,加速算法的尋優能力。然后,算法采用交換、逆轉和插入三種方式全局搜索。其中,交換是指將有序序列中隨機兩個節點的位置交換,逆轉是指將有序序列中隨機一個片段置換方向,插入是指將有序序列中的任意一個節點插入到與自身不相鄰的位置。通過上述三種方式,種群個體在全局內隨機搜索。同時,融合深度搜索、分層結構和禁忌表三種策略增強遺傳算法的搜索能力。

首先,采用基于排序的分層結構(第一層群體、第二層群體和劣質群體)細化種群,該策略啟發于灰狼優化算法[16]:

其中,N為城市規模大小,p∈[1,N]且為整數,X(i)表示種群中的第i個個體,通過分層結構將種群分為三個不同的分支。第一層群體包含較優求解方案;第二層群體包含次優求解方案;劣質群體包含擬合效果較差的求解方案。對第一、二層群體進行基于深度搜索的全局探索。即對第一、二層個體分別獨立搜索M1、M2次(M1、M2為超參數)。此外,重新初始化劣質群體,增大遺傳算法的全局搜索能力。同時采用改進后的k-opt方法快速接近局部較優解。該分層結構使優質個體具有更高的頻率被優化,同時也使群體有更大概率搜索到更優方案。最后,采用精英策略保留新生成的優質個體。

超參數M1、M2根據城市規模取兩組不同的值。當城市規模不大于100時,降低深度搜索頻率;當城市規模大于100時,加大深度搜索頻率。其公式如下:

此外,在每次搜索之前隨機更換序列起點位置,但不改變城市序列順序,其目的是動態化調整搜索起點。更進一步,在交換、逆轉和插入三種搜索方式中,通過添加禁忌表提升搜索有效性。禁忌表的設計細節如下:

2)對任意種群個體均初始化一個(1,N)零矩陣禁忌表單Tabu,并判斷個體相鄰節點是否存在于禁忌表中。若其鄰域節點存在于禁忌表,將禁忌表單中該節點的位置置1,表示該節點的鄰域節點為較理想節點。

3)隨機從S(S={1,2,…,N})或禁忌表單Tabu中選擇兩個節點(x1,x2),節點設計如下:

其中,R是一個隨機數且R∈[0,1]。當(x1,x2)來自禁忌表單Tabu時,從Tabu中隨機選擇兩個位置為0的節點;當(x1,x2)來自S時,隨機從S中選擇兩個不相鄰的節點。

4 實驗和結果分析

實驗采用MATLAB2021編程,PC內存為64GB,Intel(R),Core(TM) i7-11800H CPU。為了驗證該算法的有效性,實驗采用多個公開TSPLIB實例進行測試,并將本算法和原始遺傳算法(GA)、離散灰狼優化算法(DGWO)和離散麻雀搜索算法(DSSA)進行對比(表1)。在求解TSP問題的眾多算法中,DGWO和DSSA是目前較新穎的工作,DGWO的效果明顯強于GA、ACO、PSO等經典算法,而DSSA獲得比離散蝙蝠算法[10]和離散青蛙算法[11]更優的處理方案[9]。三種對比算法的超參數均為默認參數。由于算法所采用的種群規模和迭代次數均不一致,為了統一對比,本文所有算法的種群規模均為50,分別對每個實例求解10輪,每輪迭代100次。評價指標為10次運行中的最優求解路徑長度Best和算法平均運行時長Time(單位:秒)。在當前公開的最優路徑長度數據中,均只保留到整數,因此本實驗中的最優求解路徑長度也采用向下取整的方式保留到整數位。此外,計算不同算法最優求解路徑長度和TSPLIB提供方案的差異,得到兩者偏差的百分比Gap(單位:%)。

其中,Best表示算法最優求解路徑長度,S0表示TSPLIB公開的最優方案。指標Gap反映算法逼近最優解的能力,其值越小越好。

表1為不同算法求解結果。與其他三種對比算法相比,本文提出的算法總體上獲得了更好的解決方案。在30個TSPLIB實例中,本文算法獲得26個更優的解決方案;在pr107和u159實例上,本文算法獲得比TSPLIB提供的方案更好的處理結果;四種算法的平均偏差比為: GapGA∶GapDGWO∶GapDSSA∶GapOurs=3.788∶1.539∶1.447∶1,本文算法提供的方案在指標Gap中獲得了更低的偏差率,更接近公開方案。此外,在運行效率上本文算法也同樣優于其他三個算法。四種算法的平均運行時長比為:TimeGA∶TimeDGWO∶TimeDSSA∶TimeOurs=3.914∶16.897∶5.068∶1,在求解問題效率上,本文算法得到大幅提升,即驗證了改進k-opt方法的有效性,且原始遺傳算法在效率上優于兩種新型算法。圖4～圖6展示了部分實例在本算法上求解的最優方案,觀察發現明顯不存在路徑交叉的現象。

圖4 a280最優路線

圖5 d198最優路線

圖6 kroA200最優路線

圖7～圖9為四種算法在三個實例上的迭代收斂曲線。以圖7中a280實例擬合曲線為例,通過對比四個算法的擬合曲線發現,原始遺傳算法存在早熟問題,即算法過快收斂于局部最優解;而改進的算法即使在中期仍然能搜索出更優解。同時,改進的遺傳算法前期強化種群全局搜索能力,后期加強種群局部搜索能力,故在整個搜索過程中能較好地平衡算法的探索和開發能力。與DGWO和DSSA相比,本文算法的前期尋優能力存在微弱的差距,但整體尋優能力存在優勢。其根本原因在于:本文通過改進k-opt方法在前期增強算法探索能力,同時結合多種策略在當前解基礎上添加擾動因子,在提高算法求解質量的同時能加快算法運行效率。

圖7 d198迭代收斂曲線

圖8 a280迭代收斂曲線

圖9 kroA200迭代收斂曲線

在上述對比實驗的基礎上,本文將原始2-opt方法和改進的2-opt方法進行對比。兩種不同方法均采用改進的遺傳算法作為基本框架,指標為10次運行中的最優求解路徑長度Best、算法最優求解路徑長度和TSPLIB提供方案的差異Gap、10次平均求解路徑長度Avg、10次最優方案的方差Std和算法平均運行時長Time(單位:s)。實驗在14個小型實例數據上進行測試,其他參數均采用上述方案。分析求解結果,在指標Best中,兩個不同方法在7個實例上獲得相同的最佳求解方案,原始2-opt方法獲得3個更優的方案,改進的2-opt方法獲得4個更優的方案;在指標Avg和指標Std中,原始2-opt方法分別獲得6個更優的方案,改進的2-opt方法分別獲得7個更優的方案;在指標Time中,改進的2-opt方法明顯消耗更少的時間求解問題, 兩種方法的平均效率為Time2-opt∶ Time2-optimproved)=11.3 ∶ 1。綜上所述,改進后的2-opt方法既降低了算法時間復雜度,也減緩了原始2-opt算法過早陷入局部最優解問題。

表2 原始k-opt方法及其改進方法對比

5 總結

本文提出一種求解旅行商問題的改進k-opt遺傳算法。該算法改進原始遺傳算法以增強算法探索能力,同時融合改進的k-opt方法強化局部搜索,既能加速算法運行效率,又能減緩算法陷入局部最優解。具體地,采用交換、逆轉和插入三種策略使得種群個體在更廣闊的范圍搜索;添加禁忌表有效增加搜索;隨機置換序列順序;利用深度搜索和分層結構優化當前解。實驗采用多個公開數據集進行測試,通過對比離散灰狼算法(DGWO)、離散麻雀搜索算法(DSSA)和原始遺傳算法(GA),該算法在求解TSP問題時收斂精度和收斂效率均有良好的表現。雖然本文在求解TSP問題時獲得了較優解和較快運行效率,但將TSP問題遷移到超高規模(如TSP-art)時,該算法的求解方案和已知最優路徑還存在一定差距。如何在超高規模問題中求解TSP問題將成為下一階段的研究目標。