基于K-近鄰域搜索的遺傳算法求解旅行商問題

徐偉華,魏傳祥,張根瑞,趙彩梅,熊 堅

(昆明理工大學(xué) 交通工程學(xué)院,云南 昆明 650500)

0 引 言

旅行商問題(Traveling Salesman Problem，TSP)是多種組合優(yōu)化問題的集中概括和基本形式，它在物流配送[1]、車輛路徑優(yōu)化[2]和生產(chǎn)調(diào)度等領(lǐng)域都有廣泛應(yīng)用.由Holland首次提出的遺傳算法(Genetic Algorithm, GA)是一種啟發(fā)式全局搜索算法，適用于處理離散問題和非線性問題.針對GA存在收斂速度慢、局部搜索能力差和容易早熟等不足，為提高GA求解TSP問題的性能，國內(nèi)外研究者進行了諸多探索.Chang等[3]通過注入人工染色體的方法保持和提高種群多樣性，防止算法陷入局部最優(yōu)；Chang等[4]利用GA和蟻群算法構(gòu)成的混合算法求解TSP問題；Victer Paul等[5]采用基于有序距離向量的種群初始化技術(shù)以提高種群的多樣性；Wang[6]成功運用兩種局部優(yōu)化算子加強GA的局部搜索能力；Rafsanjani等[7]在GA中引入局部搜索算法并采用系數(shù)控制機制以彌補GA局部搜索能力較弱的不足；Hassanat等[8]采用基于線性回歸分析的種群初始化方法；Riazi[9]在GA中引入雙染色體方法，旨在加快算法的收斂速度；Hassanat等[10]研究了GA交叉和變異概率的動態(tài)控制策略；Kaabi等[11]采用基于最近鄰的貪婪式種群初始化方法；Arram等[12]提出了多父級順序交叉算子(Multi-Parent Order Crossover, MPOX)，遺傳算法求解質(zhì)量有所提高；Paul等[13]為提高種群多樣性和遺傳算法的收斂速度，設(shè)計了基于有序距離向量的交叉算子以提高算法收斂速度；Mirzaie[14]將模因算法應(yīng)用于GA的變異操作.

綜上所述，以往研究的特點如下：(1)依靠種群播種技術(shù)和注入人工染色體的方法提高種群多樣性；(2)引入其他智能算法彌補GA存在的不足；(3)通過設(shè)置參數(shù)自適應(yīng)調(diào)節(jié)機制，提高算法收斂速度和求解精度；(4)設(shè)計新型交叉算子提高GA性能.與上述研究不同，本研究將通過分析TSP的特性，在變異操作中減少無效操作的同時從變異距離中獲取啟發(fā)式信息，提高變異操作的有效性和效率.此外，還通過改進選擇模式，確保種群多樣性不隨種群的進化而逐代降低，防止算法早熟收斂.

1 問題的描述

基于圖論可將TSP問題定義為:已知賦權(quán)無向完全圖G(V,E)，V是由n(n為正整數(shù))個不同頂點所構(gòu)成的頂點集V={v1,v2,…,vn}，E是由V中的頂點兩兩連接而組成的邊集E={(vi,vj)|vi,vj∈V}，w(vi,vj)表示邊(vi,vj)的距離.TSP問題就是要從G(V,E)中找到哈密頓回路X={x1,x2,…,xn}，滿足目標函數(shù)：

(1)

2 改進遺傳算法

2.1 編碼與種群初始化

GA把問題的可行解視為生物種群中的個體(染色體)，通過編碼將可行解轉(zhuǎn)化為計算機可以處理的數(shù)據(jù)結(jié)構(gòu).本研究采用整數(shù)編碼方式，一個完全排列的整數(shù)序列即為一條染色體.當TSP問題的可行解以染色體形式存在時會有多種等效情況，染色體中基因所代表頂點的相對順序與哈密頓回路保持一致的染色體都等效，本文將這一特點稱為染色體的“多態(tài)性”.為提高初始種群質(zhì)量，借鑒貪婪算法的思想進行種群初始化.產(chǎn)生初始種群的基本步驟：

step1：從頂點集V中隨機選擇一個頂點作為染色體的首位基因；

step2：逐個從頂點集V中選擇距離上一次加入染色體的頂點最近的頂點作為下一位基因，直到所有頂點被加入染色體且保證每條染色體中不存在重復(fù)頂點；

step3：重復(fù)N(N為正整數(shù))次step1和step2則可生成初始種群，N即為種群規(guī)模.

2.2 變異操作

K-近鄰域定義為：在給定的距離度量w中，對于包含n個頂點V={v1,v2,…,vn}的TSP問題，頂點vi(1≤i≤n)的K-近鄰域是距離頂點vi最近的k個頂點的集合，記為Nk(vi)={c1,c2,…，ck}，k(1≤k≤n)代表近鄰域范圍大小.用K-近鄰度Pk(vi,cs)衡量頂點vi與其K-近鄰域Nk(vi)中頂點cs(1≤s≤k)間遠近程度：

(2)

此外，為提高算法的局部搜索能力，利用TSP問題中頂點間的距離信息，通過計算和比較變異距離差，選擇合適的變異位置以提高算法的局部搜索能力.結(jié)合上述分析，設(shè)計了啟發(fā)式移位算子(Heuristic Move Operator，HMO)和啟發(fā)式逆序算子(Heuristic Reverse Operator，HRO).

2.2.1 啟發(fā)式移位算子原理

step1:按變異概率選擇個體X=(x1,x2,…，xn)；

step2：從X中隨機選擇頂點xm(1≤m≤n)，按公式(5)從Nk(xm)中選擇近鄰頂點xd.具體方法如下：先用公式(3)計算Nk(xm)中所有頂點被選概率p(cs)，再用公式(4)分別計算Nk(xm)中前s個頂點的被選累計概率ps，最后生成一個隨機數(shù)r∈[0,1]，按公式(5)選擇近鄰點xd.如果xd==xm-1或xd==xm+1，返回step1；

相關(guān)計算公式如下：

(3)

(4)

(5)

step3：計算染色體移位變異后路徑距離的變化值Δλ1和Δλ2：

Δλ1=(w(xd-1,xm)+w(xd,xm)+w(xm-1,xm+1))-(w(xm-1,xm)+w(xm,xm+1)+w(xd-1,xd))

(6)

Δλ2=(w(xd,xm)+w(xd+1,xm)+w(xm-1,xm+1))-(w(xm-1,xm)+w(xm,xm+1)+w(xd,xd+1))

(7)

Δλ1、Δλ2計算原理如圖1所示.

(a)Δλ1計算原理 (b)Δλ2計算原理

step4：如果Δλ1≤Δλ2，將xm移動到xd-1和xd之間，否則將xm移動到xd和xd+1之間，如圖2所示.

圖2 染色體移位變異示意圖

2.2.2 啟發(fā)式逆序算子原理

step1：按變異概率選擇個體X=(x1,x2,…,xn)；

step2：從X中隨機選擇頂點xm，同上采用公式(5)從xm的K-近鄰域Nk(xm)中選擇一個近鄰頂點xd；

step3：計算染色體逆序變異后距離的變化值Δλ3、Δλ4、Δλ5和Δλ6：

Δλ3=(w(xm-1,xd-1)+w(xm,xd))-(w(xm-1,xm)+w(xd-1,xd))

(8)

Δλ4=(w(xm-1,xd)+w(xm,xd+1))-(w(xm-1,xm)+w(xd,xd+1))

(9)

Δλ5=(w(xm,xd-1)+w(xm+1,xd))-(w(xm,xm+1)+w(xd-1,xd))

(10)

Δλ6=(w(xm,xd)+w(xm+1,xd+1))-(w(xm,xm+1)+w(xd,xd+1))

(11)

Δλ3～Δλ6的計算原理如圖3所示:

圖3 逆序變異距離計算原理圖

step4：由于染色體具有“多態(tài)性”，因此xm和xd在染色體中的相對位置關(guān)系可能會有md兩種情況.逆序操作分以下9種情況：

case0：Δλ3≥0且Δλ4≥0且Δλ5≥0且Δλ6≥0，不進行任何逆序操作；case1：dm且Δλ3<0，對xm～xd-1進行逆序操作；case6：d>m且Δλ4<0，對xm～xd進行逆序操作；case7：d>m且Δλ5<0，對xm+1～xd-1進行逆序操作；case8：d>m且Δλ6<0，對xm+1～xd進行逆序操作.case1～case8的逆序操作分別如圖4所示.

圖4 染色體逆序變異示意圖

2.3 交叉操作

交叉操作是產(chǎn)生優(yōu)質(zhì)新個體的重要途徑，能直接影響GA的求解精度和效率.多父級順序交叉算子MPOX[12]是在雙親順序交叉算子(Order Crossover, OX)的基礎(chǔ)上發(fā)展而來，它可產(chǎn)生無重復(fù)個體且合法的后代.相比于傳統(tǒng)的OX，應(yīng)用MPOX的GA求解效率更高，因此本研究將采用MPOX進行變異操作.

2.4 適應(yīng)度評價與選擇

個體的評價和選擇方式對種群多樣性發(fā)展有重要影響.傳統(tǒng)GA采用的輪盤賭法、錦標賽法等可實現(xiàn)優(yōu)勢個體的積累，然而隨著種群的進化以及優(yōu)勢個體不斷的積累，種群的多樣性逐漸降低，不利于全局尋優(yōu).為更大程度地保留優(yōu)質(zhì)基因和保持種群的多樣性，設(shè)計全精英選擇法進行個體選擇.全精英選擇法是基于適應(yīng)度值大小的選擇方法，故采用路徑總距離作為適應(yīng)度值.全精英選擇法的基本步驟：

step1：將交叉和變異產(chǎn)生的新個體與父代種群合并；

step2：將合并種群中的重復(fù)個體剔除；

step3：按照適應(yīng)度值從小到大將所有個體排序并選擇適應(yīng)度最小的N個個體作為新種群.

2.5 改進遺傳算法流程設(shè)計

綜上，設(shè)計改進遺傳算法(Improved Genetic Algorithm，IGA),如圖5所示.

圖5 改進遺傳算法流程

3 實驗與結(jié)果分析

實驗在Intel Core i5-5200U 2.20 GHz處理器的計算機上進行，選用MATLAB 2018b作為編程軟件和實驗平臺，對標準TSP問題實例進行仿真計算.設(shè)置種群的規(guī)模N=100，最大進化代數(shù)Gmax=5 000，交叉概率PC=0.8，啟發(fā)式移位算子變異概率Pmm=0.1，啟發(fā)式逆序算子變異概率Pmr=0.1，變異操作的K-近鄰域搜索范圍k=20.

3.1 局部搜索能力分析

圖6是采用隨機移位算子(Random Move Operator, RMO)和隨機逆序算子(Random Reverse Operator, RRO)的GA求解Pcb442的路徑圖；圖7是采用HMO、HRO的GA求解Pcb442的最優(yōu)路徑圖.圖6明顯存在迂回路徑，IGA求解效果更優(yōu)，啟發(fā)式變異算子可以有效提高算法局部優(yōu)化能力.

圖6 采用RMO和RRO的遺傳算法求得Pcb442最優(yōu)解

圖7 采用HMO和HRO的遺傳算法求得Pcb442最優(yōu)解

3.2 種群多樣性分析

種群多樣性是指種群中所有個體之間的差異程度，有內(nèi)在結(jié)構(gòu)和外在特征上的差異.根據(jù)個體適應(yīng)度值來定義種群多樣性評價指標，已知包含N個個體的種群P={X1，X2，…,XN}，種群適應(yīng)度值F={f1,f2,…，fN}.包含N個個體的種群P的多樣性評價指標[16]為：

(12)

在使用相同種群初始化方法(貪婪算法)和變異算子(HMO、HRO)情況下，分別采用輪盤賭選擇法和完全精英選擇法的GA求解Pcb442.圖8展示了采用輪盤賭法的GA求解Pcb442種群進化過程中種群多樣性隨種群變化的情況，種群多樣性呈現(xiàn)震蕩下跌的趨勢;圖9是采用完全精英選擇法的GA求解Pcb442過程中種群多樣性的變化趨勢，種群的多樣性程度比較穩(wěn)定且呈現(xiàn)微弱上升的趨勢.通過比較圖8和圖9可以發(fā)現(xiàn),相較于輪盤賭選擇法，全精英選擇法能更好地保持種群多樣性.

圖8 輪盤賭選擇法

圖9 全精英選擇法

3.3 改進遺傳算法整體性能分析

設(shè)計四組實驗檢驗全精英選擇法和啟發(fā)式變異算子對算法性能的影響.Test1：貪婪算法種群初始化+MPOX交叉算子+隨機變異算子+輪盤賭選擇；Test2：貪婪算法種群初始化+MPOX交叉算子+隨機變異算子+全精英選擇法；Test3：貪婪算法種群初始化+MPOX交叉算子+HMO、HRO+輪盤賭選擇; Test4：貪婪算法種群初始化+MPOX交叉算子+HMO、HRO+全精英選擇法.圖10分別展示了使用四組實驗的GA求解Pcb442的收斂曲線.通過對比收斂曲線Test2和Test1可以看出：在相同遺傳代數(shù)情況下，采用輪盤賭選擇和全精英選擇法的GA收斂速度相差不大，然而采用全精英選擇法的GA的求解質(zhì)量總是優(yōu)于采用輪盤賭的GA，說明全精英選擇法對于防止GA陷入局部最優(yōu)具有較好的效果;通過對比收斂曲線Test3和Test1，采用HMO、HRO的GA尋優(yōu)速度和質(zhì)量明顯優(yōu)于采用隨機變異算子的GA.由此可知，HMO、HRO有效提升了GA的尋優(yōu)效率；相較于Test1、Test2和Test3，Test4的收斂速度和求解精度都明顯更優(yōu).

圖10 收斂曲線圖

為更進一步驗證IGA的性能，從標準TSP問題實例數(shù)據(jù)庫TSPLIB中選擇21個TSP問題實例進行實驗.圖11展示了BLS和IGA求解TSP問題實例的平均誤差回歸曲線，求解誤差回歸曲線斜率分別為kBLS=0.005 8,kIGA=0.003 1.相較于BLS算法，IGA的求解誤差回歸曲線斜率更小，IGA的求解誤差隨著解TSP問題的規(guī)模的增大而增加更緩慢.由此說明，IGA的求解性能優(yōu)于BLS算法.由于其他文獻算法求解TSP實例數(shù)量較少，在此不做比較.為評價所提出的方法求解TSP問題的精度，采用公式(13)計算誤差：

圖11 求解誤差回歸曲線

(13)

式中：Opt表示已知最優(yōu)解，Mean表示平均解，Err表示平均誤差.

表1統(tǒng)計了IGA分別求解21個TSP問題實例10次的最優(yōu)解(Best)、最劣解(Worst)、平均解(Mean)、平均誤差(Err)和平均時間(Time)，并與其他研究者論文中采用的算法求解相同TSP問題實例的實驗結(jié)果進行對比分析.比較算法包括：具有塊挖掘和重組啟發(fā)式的遺傳算法(Puzzle-Based Genetic Algorithm,p-ACGA)[4]、混合遺傳算法(Hybrid Genetic Algorithm, HGA)[6]、局部搜索算法(Breakout Local Search, BLS)[17]、狼群算法(Wolf Pack Search And Local Search, WPS-LS)[18]、獅子離散群優(yōu)化算法(Discrete Lion Swarm Optimization, DLSO)[19]、離散社交蜘蛛算法(Discrete Social Spider Algorithm, DSSA)[20].IGA與上述6種算法中求解實例最多且求解效果最好的BLS算法相比，平均求解誤差降低了15.36%.

表1 實驗結(jié)果對比

4 結(jié) 論

通過研究選擇方法和變異算子對遺傳算法求解TSP問題的性能影響，得出如下結(jié)論：

1)變異算子是新基因產(chǎn)生的根本途徑，優(yōu)質(zhì)的啟發(fā)式變異算子不僅能夠提高遺傳算法的局部搜索能力，還能加快算法的尋優(yōu)速度.傳統(tǒng)遺傳變異算子具有隨機性，使算法具有較強的全局搜索能力，但隨機變異的方式使算法的效率較低.

2)遺傳算法的選擇方式關(guān)系到種群多樣性的發(fā)展，種群多樣性的增加有利于防止算法陷入局部最優(yōu)，提高求解精度.雖然傳統(tǒng)遺傳算法進化模式能逐代積累優(yōu)勢個體，然而種群中重復(fù)的優(yōu)勢個體會擠占種群空間，因此可能導(dǎo)致優(yōu)質(zhì)基因隨劣勢個體的淘汰而損失，不利于種群多樣性發(fā)展.

3)實驗結(jié)果表明：采用K-近鄰域搜索的方式可減少無效搜索，通過變異距離為變異算子尋找有效變異位置，使得變異算子在進行全局搜索時具有較強的局部搜索能力，減少算法尋優(yōu)時間.通過剔除重復(fù)個體再選擇優(yōu)勢個體作為新種群會給新個體更大的生存空間，維持種群多樣性，有利于防止算法早熟收斂.基于K-近鄰域搜索和全精英選擇法對提高遺傳算法求解TSP問題的性能有顯著效果.