基于改進粒子群算法的路徑規劃

賈會群 魏仲慧 何 昕 張 磊 何家維 穆治亞

(1.中國科學院長春光學精密機械與物理研究所， 長春 130033； 2.中國科學院大學， 北京 100049)

0 引言

路徑規劃是機器人研究中最基本、最關鍵的問題[1-4]，目的在于尋找到一條從起點到終點的最短路徑，使機器人安全到達預定的目的地。近些年，專家學者們提出很多有關機器人路徑規劃的算法[5-15]。一類是傳統方法，如視圖法[8]、人工勢場法[9]、自由空間法[10-11]等；另一類是新興的智能仿生算法，如粒子群算法[7]、雞群算法[12]、蜂群算法[13]、狼群算法[14]、鳥群算法[15]等。相較于傳統的算法，通過模擬生物的一種或幾種行為而提出的智能仿生算法，為解決復雜環境下的路徑規劃問題提供了新思路。

粒子群算法(Particle swarm optimization, PSO)是一種模擬魚群的仿生算法，具有易于實現、收斂速度快、所需調整的參數少等優點，一經提出便得到學術界的廣泛關注[16-20]。針對PSO的研究主要集中在參數調整[16-18]、種群結構改進以及與其他方法相結合的改進[19-20]。文獻[16]通過分析慣性權重因子ω大小同PSO收斂性的關系，提出了線性自適應慣性權重因子的PSO改進算法，提高了算法的收斂性。文獻[17]在迭代過程中將適應度值較差的粒子的慣性權重因子置零，減小了算法的無效迭代，使算法的收斂性得到進一步提升。文獻[18]通過分析加速因子c1、c2和PSO收斂性的關系，提出了線性的自適應加速因子的PSO改進算法，使算法的收斂性獲得了一定的改善。文獻[19]提出了PSO和遺傳算法的混合算法用于路徑規劃，文獻[20]提出了雁群和PSO混合算法進行路徑規劃。雖然已有文獻對PSO進行了研究和改進，但目前粒子群算法依然存在收斂精度低、搜索停滯等缺點，導致在路徑規劃時不能得到最優的規劃路徑。

針對目前算法存在的問題，受文獻[12，18]的啟發，通過分析文獻中方法的優缺點，本文提出使用三角函數的變化方式自適應地調整慣性權重因子和加速因子，使慣性權重因子和加速因子在算法運行各階段的配合最佳，提高算法的搜索能力；然后引入母雞和小雞兩種更新方程對搜索停滯的粒子進行擾動，提高粒子群的多樣性，并在引入的方程中使用粒子群全局最優解，使得擾動后的粒子向全局最優解靠近，減少無效擾動，以提高算法的收斂精度及穩定性。

1 PSO算法的數學理論

文獻[21]首次提出粒子群算法，假設粒子群規模大小為n，搜索區域維數為D，xi=(xi1,xi2,…,xiD)為粒子i(i∈1,2,…,n)在搜索區域的位置，vi=(vi1,vi2,…,viD)為粒子i的速度，pi=(pi1,pi2,…,piD)為粒子i搜索的最優位置，pg=(pg1,pg2,…,pgD)為粒子群搜索的最優位置，則對于第k+1次迭代，粒子的位置更新公式為

(1)

(2)

ω——慣性權重因子

c1、c2——加速因子

rand()——(0,1)間的隨機數

2 PSO算法的改進

造成傳統的PSO收斂精度低，搜索停滯的原因有[22]：① 算法收斂后期，因粒子群多樣性降低，導致算法陷入局部最優值即“早熟”。② 因粒子容易被困在較差的搜索區域并很難跳出，造成搜索停滯，導致收斂效率低。為了解決上述問題，從粒子群參數及算法更新方程兩方面進行改進。

2.1 PSO算法的參數改進

傳統的粒子群算法的更新公式包括3部分：上一代粒子速度值、單個粒子學習部分和粒子群之間相互學習部分。第1部分受權重因子ω的控制，第2、3部分受加速因子c1、c2的控制。目前較多的研究主要集中在對一種參數的改進[16-17]，文獻[18]對慣性權重因子和加速因子同時進行改進，相較于對一種參數的改進，兩種參數同時改進的PSO算法在優化精度和收斂速度上具有一定的優勢。但文獻[18]中加速因子是在基于線性變化的基礎上進行擾動，導致擾動效果并不明顯。因此本文在文獻[18]的基礎上做進一步改進，即將線性變化的加速因子替換為非線性變化的加速因子，非線性擾動強度大，有利于提高種群的多樣性，這對解決“早熟”問題是有利的。

本文慣性權重因子仍然使用文獻[18]提出的余弦變化權重因子，其數學表達式為

(3)

其中ωmax=0.95ωmin=0.4

式中kmax——最終迭代次數

k——本次算法迭代次數

ω(k)——第k次迭代對應的慣性權重因子

根據式(3)畫出不同迭代次數時慣性權重因子的變化曲線，如圖1所示。

圖1 ω變化曲線Fig.1 Variation curves of ω

根據式(1)，算法的學習部分受加速因子c1、c2的控制，c1控制單個粒子的學習部分，c2控制粒子群之間的相互學習部分。文獻[20]中提到適當的調節加速因子可以優化算法的尋優過程，優化前期PSO算法進行全局搜索時要求個體從全局學習，因此要求前期c1取較大的值，后期PSO算法進入局部搜索時群體學習很重要，要求c2取較大的結果。經過分析，本文采用正弦函數模擬加速因子的變化，提出新的自適應加速因子

(4)

(5)

式中ca、cb、cα、cβ——待確定參數

按照文獻[20]，c1在[0.5,2.5]和c2在[0.5,2.5]取值時，可得到較高的尋優結果，因此確定ca=1，cb=1.5，cα=1，cβ=1.5。圖2、3分別為加速因子c1、c2隨迭代次數的變化曲線。

圖2 c1變化曲線Fig.2 Variation curves of c1

圖3 c2變化曲線Fig.3 Variation curves of c2

圖1～3中實線為按三角函數規律變化的自適應慣性權重因子ω及加速因子c1、c2，虛線為各參數的線性規律變化。從圖中可以看出，3個按照三角函數規律變化的參數之間是一種配合的關系，這是因為算法迭代前期慣性權重因子取值較大，PSO算法進行全局搜索，此時加速因子c1大、c2小，有助于個體對全局的學習；到了后期慣性權重因子取值較小，PSO算法進行局部搜索，此時c1小、c2大，有助于局部搜索時群體的學習，并且3種參數都是按三角函數規律增大或減小，使得各參數的大小配合達到最佳，提高算法的搜索能力。

將所提的按三角函數規律變化的慣性權重因子和加速因子方程代入式(1)、(2)得

(6)

(7)

式(6)、(7)為含有自適應參數的PSO算法的位置更新公式。

2.2 引入多種更新策略

當粒子被困在較差的搜索區域時，算法的優化結果一般會變差[17]，本文的優化問題是求取最小值，其變差的情況表示為

f(xk+1)>f(xk)

(8)

式中f(xk+1)——第k+1次迭代所得適應度值

f(xk)——第k次迭代所得適應度值

如果算法運行時連續3次迭代出現式(8)描述的情況，認為粒子處于較差的搜索區域，粒子出現無效搜索。為了解決這一問題，本文受雞群算法[12]的啟發，通過引入雞群算法中母雞和小雞2種不同擾動強度的更新方程，對無效搜索的粒子進行擾動，其目的就是通過不同強度的擾動增加粒子的多樣性，使粒子跳出較差的搜索區域，脫離局部最優。

當第1次判定粒子出現無效搜索時使用母雞更新方程進行擾動

(9)

其中s1=exp((fi-fg)/(abs(fi)+ε))

(10)

s2=exp(fi-ft)

(11)

式中t——粒子序號，t≠i

fi——第i個粒子的適應度值

fg——全局最優適應度值

ε——保證分母不為零的極小數，本文調用Matlab 2014自帶的極小數為2.225 1×10-308

s1、s2——學習因子

abs()——取絕對值函數

當式(9)擾動失敗即粒子使用式(9)更新之后仍然是無效搜索狀態，這時將加大擾動強度使用小雞更新方程進行擾動。

(12)

式中FL——[1,2]之間的任意實數，為了獲得較大的擾動，本文取FL=2

式(12)類似于鳥群算法中鳥群飛行行為[15]，可以使粒子從一個位置跳到另一個位置。

式(9)、(12)為在原來方程的基礎上改進后的方程，與原方程的不同之處在于改進后的方程都用了全局最優位置解，目的是在對這些搜索較差的粒子進行擾動時，同時使這些粒子向全局最優位置靠近，避免了無效擾動，有利于提高算法的搜索效率。

改進后算法流程如下：

(1)PSO算法各參數初始化包括粒子初始位置、初始速度等，令迭代次數k=1。

(2)計算粒子的適應度值，計算當前各粒子的個體最優值以及種群的全局最優值。

(3)使用式(6)、(7)對粒子更新。

(4)連續迭代3次，判斷f(xk+1)>f(xk)是否成立，成立轉至步驟(5)，否則轉至步驟(8)。

(5)使用式(9)對粒子進行擾動。

(6)連續迭代3次，判斷f(xk+1)>f(xk)是否成立，成立即式(9)擾動失敗轉至步驟(7)，否則轉至步驟(8)。

(7)使用式(12)對粒子進行擾動。

(8)計算位置更新后各粒子的適應度值并更新個體最優適應度值以及全局最優適應度值。

(9)判定k是否達到最大迭代次數，若是輸出最優收斂結果，否則轉至步驟(3)。

3 實驗結果與分析

為了驗證本文對傳統粒子群算法改進的有效性，本文任意選取5個標準測試函數進行函數優化，并將其應用于機器人路徑規劃，從實際應用來驗證算法的有效性，實驗平臺為Matlab 2014。

3.1 函數優化

選取的5個測試函數包含了多種類型，其基本的數學性質如表1所示，表中U表示單峰值，M表示多峰值，N表示不可分離，S表示可分離。

表1 標準測試函數Tab.1 Standard test function

為了保證實驗所得數據的有效性，每個標準測試函數單獨進行50次統計實驗，根據統計結果計算出最優值、平均最優值(Mean)和標準差(Std)，對改進算法(WCPSO)的性能進行評價。對比算法選用傳統算法即固定慣性權重粒子群算法[21](PSO)、線性自適應慣性權重因子粒子群算法[16](WPSO)和線性自適應加速因子粒子群算法[18](CPSO)3種較為常用的算法。所有算法設置相同的參數：種群數60，迭代次數1 000。實驗結果如表2所示。

從表2的整體優化結果可以看出，對于不同類型的函數，本文所提出的改進算法(WCPSO)均取得了較高的收斂精度并且優于其他算法，其次是WPSO，傳統的PSO算法收斂效果最差。表2中，函數f3、f4、f5通過改變維度，驗證各算法對不同維度函數的優化性能：對于f3，WCPSO在不同維度上均取得了優于其他算法的結果；對于f4、f5，在不同維度時所有算法均取得相似的最優結果，但從均值和方差可以看出，WCPSO穩定性明顯優于其他算法。

3.2 路徑規劃實驗

將改進的算法(WCPSO)應用到機器人路徑規劃，驗證改進算法在實際應用中的有效性。

3.2.1環境模型

采用導航點模型[1]構建環境模型如圖4所示，起點坐標(0,0)，終點坐標(9,8)， 障礙物數學表達式為

(x-a)2+(y-b)2=R2

(13)

式中 (a,b)——障礙物圓心坐標

表2 函數優化結果Tab.2 Results of function optimization

圖4 環境模型Fig.4 Environment model

R——障礙物半徑(圖4中較大圓的半徑為1，其余小圓的半徑都為0.5)

3.2.2適應度函數

設起點坐標S(x0,y0)，終點坐標T(xn+1,yn+1)，一個粒子代表一條路徑，其在x方向和y方向上的位置為X=(x1,x2,…,xn)，Y=(y1,y2,…,yn)。路徑長度函數即適應度函數為

(14)

(15)

式中K——障礙物個數

V(k)——避障約束懲罰函數

w——安全因子，根據文獻[1]設置w=100

R(k)——障礙物k的半徑

圖4中從起點到終點理論上最短的無障礙路徑長度Lmin=12.141 590。

3.2.3實驗結果分析

實驗選用函數優化結果僅次于改進算法的WPSO算法作為對比算法，2種算法參數設置相同：種群規模150，迭代次數500。為了保證結果的可靠性，改進算法和對比算法分別進行10次獨立實驗。

圖5為10次實驗中WCPSO算法和WPSO算法所得到的路徑長度曲線，綠色曲線是理論上最短的無障礙路徑長度曲線。從圖5中可以看出：10次實驗中本文的改進算法更加接近理論值，并且一直保持較優的規劃路徑，算法穩定性較好；WPSO算法雖然也能獲得較優的路徑，但算法波動大，穩定性較差。圖6、7分別為10次實驗中WCPSO算法和WPSO算法路徑規劃的仿真結果。通過圖6和圖7的對比可以很直觀地看出本文改進算法魯棒性好、路徑規劃精度高的特性。

圖5 實驗對比結果Fig.5 Comparison of experimental results

4 結束語

為了解決目前粒子群算法中因存在搜索精度低、搜索停滯等現象，導致在機器人路徑規劃中不易獲得最優路徑的問題，本文對傳統的粒子群算法進行改進，使用三角函數變化規律自適應地調整算法中的各個參數。與傳統的線性自適應參數相比，基于三角函數規律變化的參數能夠更準確地模擬在算法迭代過程中各個參數的變化趨勢，使得各參數的大小配合達到最佳，從而使得各參數的作用充分發揮。通過在引入的母雞和小雞更新方程中使用全局最優解，對搜索停滯的粒子進行擾動，增加了粒子多樣性，避免了搜索停滯的問題，實驗結果表明改進的算法具有一定的應用價值。

圖6 改進算法路徑規劃結果Fig.6 Path planning results of improved algorithm