基于改進粒子群算法的路徑規(guī)劃研究與應(yīng)用

董林威,高宏力,潘江

(西南交通大學(xué) 機械工程學(xué)院,四川 成都 610031)

0 引言

旅行商問題[1](travel salesman problem,TSP)是一個NP-hard優(yōu)化問題,可被描述為求解一次性不重復(fù)地走過n個給定的城市且回到最初城市的最短閉環(huán)路徑。針對旅行商問題的求解主要有啟發(fā)式算法以及近似算法。其中標準粒子群算法基于群體和個體的適應(yīng)度大小進行進化更新,用于求解TSP問題時具有整合參數(shù)少、迭代簡單以及快速收斂等特點[2],但是又存在易陷入局部最優(yōu)、收斂精度不高等問題。基于上述缺陷,近年來諸多學(xué)者基于優(yōu)化的粒子群算法求解TSP問題進行了大量的研究。文獻[3]根據(jù)粒子適應(yīng)度值對群體中表現(xiàn)性能各異的粒子采取不同的慣性權(quán)重調(diào)整策略,保持種群發(fā)展過程中的慣性權(quán)重多樣性,兼顧了全局和局部的搜索尋優(yōu)能力。文獻[4]基于灰狼算法的發(fā)展多樣性,提出參數(shù)自適應(yīng)的粒子群灰狼混合算法,引導(dǎo)粒子種群進化方向的準確性。文獻[5]提出基于自適應(yīng)動態(tài)優(yōu)秀系數(shù)的粒子群算法(SECPSO),在粒子搜索的每條路徑上設(shè)置權(quán)重系數(shù),并且根據(jù)種群搜索解的能力進行自適應(yīng)變化,基于3-opt局部搜索方式評價和共享粒子的位置信息,一定程度上加大了粒子群后期的收斂速度和精度。

但是SECPSO算法在針對中大規(guī)模數(shù)據(jù)的求解時,存在收斂速度較慢,精度不高的問題[5]。基于此,本文提出一種改進自適應(yīng)雜交退火粒子群算法(improved adaptive hybrid annealing PSO,IAHAPSO),在尋優(yōu)能力和求解效率上相較傳統(tǒng)算法都有較大優(yōu)勢。另外搭建四軸裁剪系統(tǒng)與所提算法結(jié)合,以解決裁剪路徑規(guī)劃問題,進一步驗證了所提算法的有效性。

1 旅行商問題的標準粒子群算法

1.1 旅行商問題

旅行商問題可被描述為:在給定城市距離的基礎(chǔ)上,一次性不重復(fù)地走過n個給定的城市且回到最初城市的最短閉環(huán)路徑,該路徑又被稱為最短Hamilton回路。其目標函數(shù)可表示為求解一段城市序列τ=(V1,V2,…,Vn)使得式(1)最小,其中Vn代表城市標號。

(1)

式中:Td為總距離;d(Vi,Vi+1)為頂點ci到頂點cj的距離,也稱為費用矩陣。

1.2 應(yīng)用粒子群算法的旅行商求解

1)交換子

定義粒子1位置向量:Xi=[xi1,xi2,xi3,…,xin],粒子2位置向量:Xj=[xj1,xj2,xj3,…,xjn],則有交換子vij=(xia,xja)表示對兩個位置向量在序列a處的位置進行對調(diào)。

2)交換序列

對交換子組成的序列V=[v1,v2,v3,…,vn]稱為交換序列。

3)速度定義

粒子的速度表示為對位置向量中城市的交換序列向量,是對位置向量的城市順序進行調(diào)整。即速度向量Vi=[vi1,vi2,vi3,…,vin]中vin表示交換子vin=(xn,xv,in),將原位置向量中按向量順序?qū)λ饕秊閚處的城市與索引為vin的城市進行位置互換。

4)位置速度更新公式

在對速度位置重新定義后,用于求解旅行商問題的粒子群算法更新公式如下:

(2)

(3)

旅行商問題為離散問題,對位置的更新需要按照?運算符分步進行,即:

(4)

(5)

(6)

2 所提算法

因標準粒子群算法存在早熟停滯、極易陷入局部最優(yōu)以及收斂精度低等問題[7],本文提出了改進自適應(yīng)雜交退火粒子群算法(IAHAPSO),對標準粒子群算法的慣性權(quán)重采用分種群式調(diào)節(jié),對群體極值的更新融入模擬退火機制引導(dǎo)粒子正確的進化方向,并且根據(jù)種群離散度大小引入雜交變異算子,以提高算法魯棒性。

2.1 分種群自適應(yīng)慣性權(quán)重

(7)

基于粒子適應(yīng)度和種群離散度的慣性權(quán)重調(diào)整如下。

1)當fi優(yōu)于fmax_avg時,該粒子尋優(yōu)效果好,此時應(yīng)該賦予該粒子較小的權(quán)重值,調(diào)整式為

(8)

2)當fi次于fmax_avg但優(yōu)于fmin_avg時,該類粒子質(zhì)量一般,搜索能力尚能在全局搜索和局部搜索之間調(diào)節(jié),故不予改變此類粒子的慣性權(quán)重。

3)當fi次于fmin_avg時,該類粒子在種群中表現(xiàn)較差。引入種群離散度可接受值,記為σaccept,可認為當種群離散度σk<σaccept時,種群聚集程度高;相應(yīng)的種群離散度σk>σaccept時,種群發(fā)散。并且引入迭代系數(shù)μ,當k<μKmax時認為種群處于發(fā)展前期。

a)σk≤σaccept時,種群聚集程度高,種群易陷入局部最優(yōu),此時表現(xiàn)“較差”的粒子應(yīng)具有在全局最優(yōu)解附近進行搜索的能力,故ω=ωmax加大其全局搜索的能力。

b)k<μKmax且σk>σaccept時,為平衡慣性權(quán)重值對種群在全局和局部范圍內(nèi)的搜索能力,綜合考慮種群發(fā)展程度和種群離散度,采用的自適應(yīng)慣性權(quán)重調(diào)整方式如下:

(9)

上式中參數(shù)k1控制ω的范圍,考慮種群離散度和種群發(fā)展程度自適應(yīng)調(diào)節(jié)。

c)k≥μKmax且σk>σaccept時,該種情況種群發(fā)展后期且尚未收斂,應(yīng)降低慣性權(quán)重值,加大該類粒子局部搜索能力,加速收斂,故ω=ωmin。

2.2 基于模擬退火算子的群體極值更新

本文引入退火操作從諸多粒子pi中根據(jù)突跳概率更新群體極值gbest,提高算法避免陷入局部極小值的能力。種群中每個粒子按下式計算溫度T下該粒子pi相對gbest的突跳概率P*:

(10)

式中:T(k)為退火溫度,退火規(guī)律見式(11);ρ為降溫系數(shù);fg,best(1)為初始群體極值。

(11)

最后,采用輪盤賭策略及式(10)從粒子群中所有粒子確定群體極值的替代值p′i來替代gbest。

2.3 選擇交叉變異算子

本文利用種群離散度判斷種群發(fā)展的趨同程度,類似地,當σk≤σaccept時則進行遺傳變異算子。

選擇算子:本文采用基于比例選擇和最優(yōu)選擇的策略,首先復(fù)制群體最優(yōu)粒子到下一代,使其占下一代種群數(shù)量的M%,剩余1-M%的粒子采用輪盤比例策略進行選擇,每個個體被選中的概率為

(12)

經(jīng)過上述方式選出N個優(yōu)秀粒子進行后續(xù)操作,使得粒子整體朝著種群最優(yōu)的方向運動。

交叉算子:采用將選擇算子得到的N個粒子隨機進行兩兩匹配的方式,從而形成N/2組父代雙親Father,A,Father,B,以交叉概率Pc且隨機產(chǎn)生一個交叉點位置α,將Father,A的序列1-α的元素作為子代Child,A的系列1-α,將Father,B中包含F(xiàn)ather,A序列1-α的元素按照Father,B的順序作為Child,B的系列1-α,將Father,A的α之后的元素作為Child,B的剩余元素值,而將Father,B中的剩余元素按序列作為Child,A的剩余元素值。例如,有兩個父代序列,交叉點位置為3,則有:

Father,A=1,3,6,8,4,7,2,5
Father,B=2,4,3,5,1,7,6,8

交叉后子代為:

Child,A=1,3,6,2,4,5,1,8
Child,B=3,1,6,8,4,7,2,5

變異算子:針對種群中的每個粒子,隨機產(chǎn)生交換序列對[β,γ],對該個體的序列位置β上的元素與序列位置γ上的元素進行互換,以此直至完成所有個體的變異。

2.4 算法流程

基于上述模塊,本文所提IAHAPSO算法的具體流程如圖1所示。

圖1 IAHAPSO算法流程

3 仿真及應(yīng)用

為驗證所提算法的性能,本文首先選擇3種標準TSPLIB測試集,以城市總距離的倒數(shù)為適應(yīng)度值fi,并且將本文IAHAPSO算法同標準PSO算法以及SECPSO算法進行比較,驗證算法的可行性。

3.1 TSP測試集及參數(shù)設(shè)置

本文選擇TSPLIB測試集當中的Eil51、St70及Ch150 3種問題進行實驗對比分析,設(shè)置相關(guān)參數(shù)如下:種群規(guī)模N=200,最大迭代次數(shù)Kmax=1 000,ωmax=0.8,ωmin=0.2,σaccept=5,Pc=0.6,M=20,μ=0.4,ρ=0.98,k1=50。SECPSO 算法中的相關(guān)參數(shù)與文獻[5]相同;標準PSO算法取ω=0.8。針對3種測試集問題,采用PSO、SECPSO以及IAHAPSO算法的求解收斂曲線如圖2—圖4所示,表1給出了3種不同算法求解問題的性能比較。

表1 性能結(jié)果比較

圖2 Eil51不同算法收斂速度

圖3 St70不同算法收斂速度

圖4 Ch150不同算法收斂速度

表1統(tǒng)計了本文所提算法與SECPSO算法的性能對比,其中平均值為各實例在各算法下迭代50次的平均結(jié)果。從表中可以看出,本文所提的算法在搜索能力上優(yōu)于SECPSO算法。另外對于部分標準測試集,雖然IAHAPSO算法在平均值上略差于SECPSO算法,但是在最優(yōu)值的求解上本文所提算法都優(yōu)于SECPSO,整體求解能力有較大的優(yōu)勢。

3.2 四軸裁剪機試驗系統(tǒng)

為驗證所提算法在實際應(yīng)用中的兼容性和有效性,搭建了如圖5所示的四軸裁剪機試驗系統(tǒng),用于對排樣固定的裁剪樣片進行切割。整體裝置由電機模組作為動力源搭建硬件框架,裁剪主體裝置整體集成在一個運動方向上,由上位機發(fā)送指令給控制器,控制器解析運動指令后控制模組運動,從而實現(xiàn)任意排樣裁剪形狀的切割。

圖5 四軸裁剪機試驗系統(tǒng)

將所提IAHAPSO算法作為方法類寫入上位機軟件中,當上位機讀取到可編譯的DXF文件時,調(diào)用該方法,優(yōu)化裁剪軌跡,并可在上位機中可視化路徑,由人工確定滿足工藝需求情況下,輸出可供PLC運動控制器讀取的運動G代碼指令,從而驅(qū)動各軸進行運動裁剪。圖6為應(yīng)用該集成方法對某一排樣圖形的裁剪路徑規(guī)劃。相較于傳統(tǒng)排樣軟件和人工排樣方法,在針對中大型排樣數(shù)量的裁剪路徑優(yōu)化時,本文所提方法運算時間可在0.5s以內(nèi),在一定程度上可有效提高生產(chǎn)效率。

圖6 集成軟件路徑優(yōu)化結(jié)果

4 結(jié)語

本文提出一種用于求解旅行商問題的改進自適應(yīng)雜交退火粒子群算法(IAHAPSO),采用分種群自適應(yīng)調(diào)整慣性權(quán)重,且基于模擬退火算子對群體極值進行更新,引入遺傳變異算子加大種群發(fā)展后期的多樣性。通過測試集仿真結(jié)果表明:IAHAPSO算法相較于其他改進PSO算法,在收斂速度和精度上都有較大提高,驗證了所提算法的優(yōu)越性。搭建四軸裁剪機實驗系統(tǒng),將所提算法用于解決裁剪樣品路徑規(guī)劃過程,較傳統(tǒng)求解過程和人工排樣方式,求解效率更高,具有一定應(yīng)用參考價值。