基于改進(jìn)粒子群算法的路徑規(guī)劃

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

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

0 引言

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

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

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

1 PSO算法的數(shù)學(xué)理論

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

(1)

(2)

ω——慣性權(quán)重因子

c1、c2——加速因子

rand()——(0,1)間的隨機(jī)數(shù)

2 PSO算法的改進(jìn)

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

2.1 PSO算法的參數(shù)改進(jìn)

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

本文慣性權(quán)重因子仍然使用文獻(xiàn)[18]提出的余弦變化權(quán)重因子，其數(shù)學(xué)表達(dá)式為

(3)

其中ωmax=0.95ωmin=0.4

式中kmax——最終迭代次數(shù)

k——本次算法迭代次數(shù)

ω(k)——第k次迭代對應(yīng)的慣性權(quán)重因子

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

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

根據(jù)式(1)，算法的學(xué)習(xí)部分受加速因子c1、c2的控制，c1控制單個粒子的學(xué)習(xí)部分，c2控制粒子群之間的相互學(xué)習(xí)部分。文獻(xiàn)[20]中提到適當(dāng)?shù)恼{(diào)節(jié)加速因子可以優(yōu)化算法的尋優(yōu)過程，優(yōu)化前期PSO算法進(jìn)行全局搜索時要求個體從全局學(xué)習(xí)，因此要求前期c1取較大的值，后期PSO算法進(jìn)入局部搜索時群體學(xué)習(xí)很重要，要求c2取較大的結(jié)果。經(jīng)過分析，本文采用正弦函數(shù)模擬加速因子的變化，提出新的自適應(yīng)加速因子

(4)

(5)

式中ca、cb、cα、cβ——待確定參數(shù)

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

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

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

圖1～3中實(shí)線為按三角函數(shù)規(guī)律變化的自適應(yīng)慣性權(quán)重因子ω及加速因子c1、c2，虛線為各參數(shù)的線性規(guī)律變化。從圖中可以看出，3個按照三角函數(shù)規(guī)律變化的參數(shù)之間是一種配合的關(guān)系，這是因?yàn)樗惴ǖ捌趹T性權(quán)重因子取值較大，PSO算法進(jìn)行全局搜索，此時加速因子c1大、c2小，有助于個體對全局的學(xué)習(xí)；到了后期慣性權(quán)重因子取值較小，PSO算法進(jìn)行局部搜索，此時c1小、c2大，有助于局部搜索時群體的學(xué)習(xí)，并且3種參數(shù)都是按三角函數(shù)規(guī)律增大或減小，使得各參數(shù)的大小配合達(dá)到最佳，提高算法的搜索能力。

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

(6)

(7)

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

2.2 引入多種更新策略

當(dāng)粒子被困在較差的搜索區(qū)域時，算法的優(yōu)化結(jié)果一般會變差[17]，本文的優(yōu)化問題是求取最小值，其變差的情況表示為

f(xk+1)>f(xk)

(8)

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

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

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

當(dāng)?shù)?次判定粒子出現(xiàn)無效搜索時使用母雞更新方程進(jìn)行擾動

(9)

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

(10)

s2=exp(fi-ft)

(11)

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

fi——第i個粒子的適應(yīng)度值

fg——全局最優(yōu)適應(yīng)度值

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

s1、s2——學(xué)習(xí)因子

abs()——取絕對值函數(shù)

當(dāng)式(9)擾動失敗即粒子使用式(9)更新之后仍然是無效搜索狀態(tài)，這時將加大擾動強(qiáng)度使用小雞更新方程進(jìn)行擾動。

(12)

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

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

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

改進(jìn)后算法流程如下：

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

(2)計(jì)算粒子的適應(yīng)度值，計(jì)算當(dāng)前各粒子的個體最優(yōu)值以及種群的全局最優(yōu)值。

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

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

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

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

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

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

(9)判定k是否達(dá)到最大迭代次數(shù)，若是輸出最優(yōu)收斂結(jié)果，否則轉(zhuǎn)至步驟(3)。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文對傳統(tǒng)粒子群算法改進(jìn)的有效性，本文任意選取5個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行函數(shù)優(yōu)化，并將其應(yīng)用于機(jī)器人路徑規(guī)劃，從實(shí)際應(yīng)用來驗(yàn)證算法的有效性，實(shí)驗(yàn)平臺為Matlab 2014。

3.1 函數(shù)優(yōu)化

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

表1 標(biāo)準(zhǔn)測試函數(shù)Tab.1 Standard test function

為了保證實(shí)驗(yàn)所得數(shù)據(jù)的有效性，每個標(biāo)準(zhǔn)測試函數(shù)單獨(dú)進(jìn)行50次統(tǒng)計(jì)實(shí)驗(yàn)，根據(jù)統(tǒng)計(jì)結(jié)果計(jì)算出最優(yōu)值、平均最優(yōu)值(Mean)和標(biāo)準(zhǔn)差(Std)，對改進(jìn)算法(WCPSO)的性能進(jìn)行評價。對比算法選用傳統(tǒng)算法即固定慣性權(quán)重粒子群算法[21](PSO)、線性自適應(yīng)慣性權(quán)重因子粒子群算法[16](WPSO)和線性自適應(yīng)加速因子粒子群算法[18](CPSO)3種較為常用的算法。所有算法設(shè)置相同的參數(shù)：種群數(shù)60，迭代次數(shù)1 000。實(shí)驗(yàn)結(jié)果如表2所示。

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

3.2 路徑規(guī)劃實(shí)驗(yàn)

將改進(jìn)的算法(WCPSO)應(yīng)用到機(jī)器人路徑規(guī)劃，驗(yàn)證改進(jìn)算法在實(shí)際應(yīng)用中的有效性。

3.2.1環(huán)境模型

采用導(dǎo)航點(diǎn)模型[1]構(gòu)建環(huán)境模型如圖4所示，起點(diǎn)坐標(biāo)(0,0)，終點(diǎn)坐標(biāo)(9,8)， 障礙物數(shù)學(xué)表達(dá)式為

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

(13)

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

表2 函數(shù)優(yōu)化結(jié)果Tab.2 Results of function optimization

圖4 環(huán)境模型Fig.4 Environment model

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

3.2.2適應(yīng)度函數(shù)

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

(14)

(15)

式中K——障礙物個數(shù)

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

w——安全因子，根據(jù)文獻(xiàn)[1]設(shè)置w=100

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

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

3.2.3實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)選用函數(shù)優(yōu)化結(jié)果僅次于改進(jìn)算法的WPSO算法作為對比算法，2種算法參數(shù)設(shè)置相同：種群規(guī)模150，迭代次數(shù)500。為了保證結(jié)果的可靠性，改進(jìn)算法和對比算法分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)。

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

圖5 實(shí)驗(yàn)對比結(jié)果Fig.5 Comparison of experimental results

4 結(jié)束語

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

圖6 改進(jìn)算法路徑規(guī)劃結(jié)果Fig.6 Path planning results of improved algorithm