嚴(yán)浙平，鄧 超，遲冬南，趙玉飛

哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，哈爾濱 150001

雙種群粒子群算法及其在UUV路徑規(guī)劃中的應(yīng)用

嚴(yán)浙平，鄧 超，遲冬南，趙玉飛

哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，哈爾濱 150001

1 引言

粒子群算法（Particle Swarm Optimization）是群智能（Swarm Intelligence，SI）計(jì)算方法的一種，最早由美國學(xué)者Kennedy和Eberhart于1995年提出。由于PSO概念和參數(shù)調(diào)節(jié)都比較簡單，易于實(shí)現(xiàn)，具有較強(qiáng)的尋優(yōu)能力。一經(jīng)提出便受到廣泛關(guān)注，許多專家學(xué)者對其進(jìn)行了深入的研究和分析，提出了很多改進(jìn)策略，以提高算法的性能[1-2]。

常見的改進(jìn)方案是對PSO參數(shù)的優(yōu)化。文獻(xiàn)[3]建立了慣性權(quán)重隨種群多樣性測度的變化關(guān)系，利用其對慣性權(quán)重進(jìn)行自適應(yīng)調(diào)整，仿真結(jié)果顯示該算法在平均最優(yōu)值和成功率上都有所提高，對多峰函數(shù)的效果尤其明顯。文獻(xiàn)[4]針對PSO參數(shù)改變提出時(shí)變加速度系數(shù)的三條改進(jìn)策略。以求能夠更加有效、準(zhǔn)確地找到最優(yōu)解。許多學(xué)者還對PSO的信息拓?fù)浣Y(jié)構(gòu)進(jìn)行了改進(jìn)。文獻(xiàn)[5]提出一種雙種群粒子群算法，利用兩組搜索方向相反的主、輔子群相互協(xié)同，充分利用搜索域內(nèi)的有用信息，擴(kuò)展了種群的搜索范圍。文獻(xiàn)[6]提出一種改進(jìn)的基于多種群協(xié)同進(jìn)化的粒子群優(yōu)化算法，通過種群進(jìn)化信息生成解優(yōu)勝區(qū)域，指導(dǎo)變異生成的粒子群向最優(yōu)解子空間逼近。實(shí)驗(yàn)表明該方法具有較好的全局收斂能力和穩(wěn)定性。粒子群算法與仿生智能算法的結(jié)合使用也獲得了廣泛的關(guān)注。文獻(xiàn)[7]提出了一種改進(jìn)協(xié)同微粒群算法（ICPSO），并用其建立一類非線性對象的神經(jīng)網(wǎng)絡(luò)辨識(shí)模型，獲得了較好的效果。文獻(xiàn)[8]借鑒蟻群優(yōu)化算法的信息素共享機(jī)制，設(shè)計(jì)了粒子信息留存規(guī)則、信息獲取和融合規(guī)則以及粒子演化規(guī)則，實(shí)現(xiàn)了群體信息的充分分享，改善了算法的尋優(yōu)能力。通過與其他類型的改進(jìn)優(yōu)化算法對比驗(yàn)證了該算法的有效性。

為了能進(jìn)一步提高粒子群算法搜索精度和穩(wěn)定性，提高粒子群算法性能，本文提出一種雙種群粒子群算法，其中一個(gè)種群側(cè)重局部搜索，另一個(gè)種群側(cè)重全局搜索，兩個(gè)種群協(xié)調(diào)進(jìn)化。

近年來UUV作為海洋探測與開發(fā)的有力工具越來越受到人們的重視。UUV路徑規(guī)劃方法是保證UUV有效完成作業(yè)任務(wù)的重要問題，得到了廣泛關(guān)注。有很多學(xué)者將智能優(yōu)化算法應(yīng)用于UUV路徑規(guī)劃，取得了較好的規(guī)劃效果[9-11]。為驗(yàn)證本文所提方法在工程應(yīng)用中的有效性，將改進(jìn)的粒子群算法應(yīng)用于UUV路徑規(guī)劃問題，并進(jìn)行了仿真驗(yàn)證。

2 粒子群算法的幾種經(jīng)典改進(jìn)

文獻(xiàn)[12]指出，較大的慣性因子可以加強(qiáng)算法的全局搜索能力，較小的慣性因子可以加強(qiáng)局部搜索能力。針對慣性因子對算法性能的影響特點(diǎn)，有很多改進(jìn)算法，以獲得更好的搜索效果。典型的做法是在搜索初期慣性權(quán)重較大，重點(diǎn)進(jìn)行廣泛的全局搜索，隨著搜索的進(jìn)行，逐漸減小慣性權(quán)重，加強(qiáng)局部搜索能力，最終算法收斂到極值點(diǎn)。

如文獻(xiàn)[13]提出慣性權(quán)重線性下降的粒子群算法（LWPSO），表達(dá)式如公式（1）所示：

其中，wmax，wmin分別為w的最大和最小值，G，k分別為最大迭代次數(shù)和當(dāng)前迭代次數(shù)。

文獻(xiàn)[14]提出慣性權(quán)重指數(shù)形式遞減的粒子群算法（EPSO），表達(dá)式如公式（2）所示：

其中，wmax，wmin分別為w的最大和最小值，G，k分別為最大迭代次數(shù)和當(dāng)前迭代次數(shù)。

Kennedy和Eberhart研究認(rèn)為，粒子群搜索過程中如果個(gè)體經(jīng)驗(yàn)學(xué)習(xí)因子所占比重比群體經(jīng)驗(yàn)學(xué)習(xí)因子所占比重大，則會(huì)使得粒子在搜索空間中過度搜索。如果群體經(jīng)驗(yàn)學(xué)習(xí)因子所占比重比個(gè)體經(jīng)驗(yàn)所占比重大，則會(huì)使得粒子過早收斂于局部最優(yōu)值。為此Ratnaweera等提出時(shí)變加速系數(shù)（ΤVAC）的粒子群算法[4]，在搜索過程中c1和c2隨時(shí)間變化，在搜索初期c1＞c2，粒子趨向群體最優(yōu)，在搜索后期c1＜c2，粒子趨近全局最優(yōu)解，具體公式如公式（3）和公式（4）所示：

其中，MΑXITR表示最大迭代次數(shù)，iter表示當(dāng)前迭代次數(shù)，c1i，c2i，c1f和c2f均為常數(shù)，研究表明，c1由2.5變到0.5，c2由0.5變到2.5時(shí)可以獲得較好的搜索效果。ΤVAC粒子群算法求解單峰函數(shù)時(shí)搜索精度和穩(wěn)定性都有所提高，但在求解多峰函數(shù)時(shí)效果并不理想[4]。

3 雙種群粒子群算法

為了有效利用慣性權(quán)重和學(xué)習(xí)因子對粒子群算法的影響，有效改進(jìn)粒子群算法性能，考慮采用兩個(gè)不同搜索的種群協(xié)調(diào)進(jìn)化的雙種群粒子群算法（Τwo-Subpopulation Particle Swarm Optimization，ΤSPSO）實(shí)現(xiàn)粒子尋優(yōu)。

在粒子進(jìn)化過程中，具有當(dāng)前最優(yōu)位置的種群應(yīng)側(cè)重于局部搜索，則該種群的慣性因子取較小的值，自身經(jīng)驗(yàn)學(xué)習(xí)因子比社會(huì)經(jīng)驗(yàn)學(xué)習(xí)因子低。而不具有當(dāng)前最優(yōu)位置的種群應(yīng)側(cè)重于全局搜索，則該種群的慣性因子取較大的值，自身經(jīng)驗(yàn)學(xué)習(xí)因子比社會(huì)經(jīng)驗(yàn)學(xué)習(xí)因子高。兩個(gè)種群在進(jìn)化過程中受共同的群體最優(yōu)位置影響進(jìn)行進(jìn)化，從而實(shí)現(xiàn)信息共享，協(xié)調(diào)進(jìn)化。為進(jìn)一步提高搜索性能，借鑒文獻(xiàn)[14]的經(jīng)驗(yàn)，側(cè)重全局搜索的種群的慣性因子，并不取恒定大值，而是隨著迭代次數(shù)的增加，由大到小以指數(shù)規(guī)律變小。在搜索后期最終側(cè)重于局部搜索。

即有粒子進(jìn)化方程：

變量定義：

nt為種群t中粒子個(gè)數(shù)；為第k次迭代后種群t中第i個(gè)粒子第d維坐標(biāo)；ωt為種群t的慣性權(quán)重；ωmax為較大的慣性權(quán)重；ωmin為較小的慣性權(quán)重；c1為學(xué)習(xí)因子1；c2為學(xué)習(xí)因子2；為第k次迭代后種群t中第i個(gè)粒子的適應(yīng)度函數(shù)；為第k次迭代時(shí)種群t中第i個(gè)粒子第d維的速度為第k次迭代后種群最優(yōu)粒子第d維坐標(biāo)；為第k次迭代后種群t中粒子歷史最優(yōu)位置第d維坐標(biāo)。

具體算法流程如下：

4 算法性能分析

為衡量算法的性能，采用不同的測試函數(shù)對算法進(jìn)行測試，并將ΤSPSO與BPSO、LWPSO、EPSO、ΤVAC性能進(jìn)行比較。

采用的測試函數(shù)為：

（1）Sphere函數(shù)

（5）Griewank函數(shù)

仿真時(shí)，對于ΤSPSO取種群1和種群2中粒子個(gè)數(shù)均為n=15，對于BPSO、LWPSO、EPSO取種群粒子個(gè)數(shù)為n=30。學(xué)習(xí)因子取c1=c2=2.0，自變量維數(shù)D=10，慣性因子ω設(shè)為0.7，ωmax設(shè)為0.9，ωmin設(shè)為0.4，cmax=2.5，cmin=0.5，搜索空間xi∈[-100，100]，速度變量范圍νi∈[-100，100]，搜索過程中，如果粒子位置超出邊界，則此時(shí)邊界坐標(biāo)設(shè)為粒子位置坐標(biāo)，并將速度設(shè)為零。如果速度超出邊界，則將速度邊界值設(shè)為速度值。為了獲得更加準(zhǔn)確的仿真結(jié)果，對每個(gè)函數(shù)的優(yōu)化都重復(fù)100次，每次都迭代1 000次，對得到的100個(gè)結(jié)果求取平均數(shù)和標(biāo)準(zhǔn)差。仿真結(jié)果如表1所示。

由表1可以看出，對于單模態(tài)函數(shù)搜索精度和穩(wěn)定性由低到高依次為BPSO、LWPSO、EPSO、ΤVAC、ΤSPSO。對于多模態(tài)函數(shù)ΤVAC的效果要稍優(yōu)于其他算法。圖1給出了Sphere函數(shù)與Rastrigin函數(shù)進(jìn)化過程中的平均適應(yīng)度變化曲線，其中實(shí)線為BPSO進(jìn)化過程曲線，虛線為ΤVAC進(jìn)化過程曲線，點(diǎn)線為LWPSO進(jìn)化過程曲線，雙劃線為EPSO、點(diǎn)劃線為ΤSPSO進(jìn)化過程曲線。由圖1中可以看出，無論對單模態(tài)函數(shù)還是多模態(tài)函數(shù)，迭代收斂由快到慢依次為ΤSPSO、ΤVAC、BPSO、EPSO、LWPSO。

表1 BPSO、LWPSO、EPSO、ΤVAC和ΤSPSO對比結(jié)果1）

圖1 平均適應(yīng)度變化曲線圖

為驗(yàn)證算法在不同維數(shù)下的性能，對測試函數(shù)，維數(shù)從10維增加到100維，分別計(jì)算了五種算法作用下結(jié)果的均值和標(biāo)準(zhǔn)差。表2給出了Rosenbrock函數(shù)由10維增加到100維的部分實(shí)驗(yàn)數(shù)據(jù)。由表2可知，隨著測試函數(shù)維數(shù)的增加各算法的搜索精度和穩(wěn)定性均會(huì)顯著下降，而ΤSPSO與ΤVAC的下降程度比較小，對于高維測試函數(shù)ΤVAC的搜索精度和穩(wěn)定性較ΤSPSO略強(qiáng)。

表2 Rosenbrock函數(shù)不同維數(shù)下BPSO、LWPSO、EPSO、ΤVAC和ΤSPSO對比結(jié)果1）

5 UUV路徑規(guī)劃

5.1 模型建立

UUV航跡規(guī)劃，是指尋找從UUV作業(yè)起始點(diǎn)到作業(yè)任務(wù)目標(biāo)點(diǎn)的最優(yōu)航跡，通常要求航行時(shí)間最短、能耗最小以及生存概率最大，使得UUV安全高效地完成作業(yè)任務(wù)。假設(shè)起始點(diǎn)坐標(biāo)為P0(x0，y0，z0)，航跡點(diǎn)坐標(biāo)為Pi(xi，yi，zi)，i=1，2，…，n，目標(biāo)點(diǎn)坐標(biāo)為Pg(xg，yg，zg)。UUV航跡規(guī)劃即是尋找一系列滿足一定條件的航跡點(diǎn)Pi。本文利用改進(jìn)的粒子群優(yōu)化算法實(shí)現(xiàn)航跡規(guī)劃。規(guī)劃開始時(shí)，從起始點(diǎn)依次尋找航跡點(diǎn)。為簡化運(yùn)算，采用極坐標(biāo)表示法有Li(Ri，ψi，θi)，且每段航跡段固定長度，即Ri為恒值。這樣每個(gè)粒子在三維搜索空間中搜索優(yōu)化的ψi，θi。為進(jìn)一步提高搜索性能，對每個(gè)粒子新產(chǎn)生的候選點(diǎn)進(jìn)行航跡回溯，即，假設(shè)已尋找到i個(gè)航跡點(diǎn)，接下來需要尋找第Pi+1個(gè)航跡點(diǎn)，假設(shè)粒子進(jìn)化中，一個(gè)粒子在搜索空間中找到一點(diǎn)Pi+1，此時(shí)進(jìn)行回溯，分析Pi+1點(diǎn)依次與之前航跡點(diǎn)的連線（即，分別連線Pi+1PiPi-2…P0，Pi+1Pi-1Pi-2…P0，…）。如果連線未遭遇障礙或威脅，則為一條有效航跡，比較所得幾條有效航跡的代價(jià)函數(shù)，代價(jià)函數(shù)較優(yōu)的航跡作為該粒子的當(dāng)前代價(jià)函數(shù)，參與比較，并保存該航跡。通過依次迭代，逐點(diǎn)尋優(yōu)。最終完成UUV在作業(yè)區(qū)間的航跡規(guī)劃，得到一條次優(yōu)的航跡。UUV航跡規(guī)劃過程示意圖如圖2所示。

圖2 UUV航跡規(guī)劃過程示意圖

5.2 路徑規(guī)劃條件

（1）角度約束

由于航行器機(jī)動(dòng)性能的限制，需要對航行器的艏搖角和縱傾角進(jìn)行約束。

令Di=[xi-xi-1yi-yi-1zi-zi-1]，UUV的最大轉(zhuǎn)彎角度為θmax，則有約束條件[11]：

（2）路徑長度約束

由于水下航行器攜帶能源和作業(yè)時(shí)間的限制，需要對航跡長度進(jìn)行約束，即規(guī)劃路徑必須小于等于預(yù)設(shè)的最大距離。

（3）安全曲面約束

航行器規(guī)劃的航跡必須要與障礙保持足夠的安全裕度，這樣才能有效地降低航行器碰觸障礙的概率。

（4）作業(yè)深度約束

UUV作業(yè)通常要滿足一定的安全隱蔽性，并且考慮減小與水面船舶的遭遇概率，設(shè)定UUV最小作業(yè)深度Hmin；由于UUV自身耐壓、水密等指標(biāo)限制，需要設(shè)定UUV最大作業(yè)深度Hmax。

（5）監(jiān)聽威脅

本文研究監(jiān)聽威脅下的UUV航跡規(guī)劃，威脅源為已探明敵方水聲監(jiān)聽源。在不考慮聲速、海流、水溫等影響條件下，UUV所受某水聲監(jiān)聽源的威脅只與距離有關(guān)。圖3所示為監(jiān)聽源探測范圍示意圖。

圖3 水聲監(jiān)聽源

圓心(x′0，y′0)為監(jiān)聽源中心位置。其水平截面內(nèi)的各點(diǎn)威脅概率可采用高斯分布函數(shù)來建模。有：

其中r表示位置向量r=[x，y]Τ，Q表示監(jiān)聽源的威脅程度。μ和K分別表示平均值和方差，有：

為簡化威脅源的威脅模型，在每一監(jiān)聽源的不同水平截面采用同一二維高斯分布函數(shù)。由多維高斯法則，在位置r處受多個(gè)監(jiān)聽源威脅的程度為各監(jiān)聽源威脅概率分布的疊加：

UUV行進(jìn)過程中，遭遇到大于一定威脅度的區(qū)域時(shí)，選擇繞行。

5.3 仿真驗(yàn)證

選取海底三維地形圖的一部分{[0，15 000]，[0，15 000]，[500，－500]}作為規(guī)劃空間。取起始點(diǎn)為（4 000，1 000，－180），目標(biāo)點(diǎn)（13 000，14 000，－40）。為便于表示，威脅聲源用柱形表示。威脅聲源坐標(biāo)（6 500，7 300），（7 500，4 500），（9 500，9 000），（11 000，10 000）。當(dāng)威脅概率大于0.4時(shí)，UUV需要規(guī)避威脅。UUV最大轉(zhuǎn)角qmax=60°仿真結(jié)果如圖4所示。由圖4可以看出，UUV可以很好地規(guī)避固定障礙威脅和監(jiān)聽聲源威脅，并得到較優(yōu)的航行路徑。

圖4 UUV航跡規(guī)劃仿真圖

6 結(jié)論

在粒子進(jìn)化過程中，具有當(dāng)前最優(yōu)位置的種群側(cè)重于局部搜索，而不具有當(dāng)前最優(yōu)位置的種群側(cè)重于全局搜索。兩個(gè)種群有效地協(xié)調(diào)合作，使得雙種群粒子群算法ΤSPSO在搜索精度、穩(wěn)定性以及搜索速度上均優(yōu)于BPSO、LWPSO、EPSO、ΤVAC算法。將ΤSPSO用于UUV三維空間的軌跡規(guī)劃問題，可實(shí)現(xiàn)UUV對固定障礙以及聲源威脅的有效規(guī)避，獲得了較好的無碰路徑。

[1]Chander A，Chatterjee A，Siarry P.A new social and momentum component adaptive PSO algorithm for image segmentation[J].Expert Systems with Applications，2011，38：4998-5004.

[2]Gupta S，Devi S.Modified PSO algorithm with high exploration and exploitation ability[J].International Journal of Software Engineering Research&Practices，2011，1（1）：15-19.

[3]張頂學(xué)，關(guān)治洪，劉新芝.一種動(dòng)態(tài)改變慣性權(quán)重的自適應(yīng)粒子群算法[J].控制與決策，2008，23（11）：1253-1257.

[4]Ratnaweera A，Halgamuge S K，Watson H C.Self-organizing hierarchical Particle Swarm Optimizer with time-varying acceleration coefficients[J].IEEE Τransactions on Evolutionary Computation，2004，8（3）：240-255.

[5]焦巍，劉光斌.動(dòng)態(tài)環(huán)境下的雙子群PSO算法[J].控制與決策，2009，24（7）：1083-1091.

[6]陶新民，徐晶，楊立標(biāo)，等.改進(jìn)的多種群協(xié)同進(jìn)化微粒群優(yōu)化算法[J].控制與決策，2009，24（9）：1406-1411.

[7]都延麗，吳慶憲，姜長生，等.改進(jìn)協(xié)同微粒群優(yōu)化的模糊神經(jīng)網(wǎng)絡(luò)控制系統(tǒng)設(shè)計(jì)[J].控制與決策，2008，23（12）：1327-1337.

[8]呂強(qiáng)，劉士榮，邱雪娜.基于信息素機(jī)制的粒子群優(yōu)化算法的設(shè)計(jì)與實(shí)現(xiàn)[J].自動(dòng)化學(xué)報(bào)，2009，35（11）：1410-1419.

[9]陳雄，趙一路，韓建達(dá).一種改進(jìn)的機(jī)器人路徑規(guī)劃的蟻群算法[J].控制理論與應(yīng)用，2010，27（6）：821-825.

[10]李霞，魏瑞軒，周軍，等.基于改進(jìn)遺傳算法的無人機(jī)飛行器三維路徑規(guī)劃[J].西北工業(yè)大學(xué)學(xué)報(bào)，2010，28（3）：343-348.

[11]于飛，唐小勇，潘洪悅.改進(jìn)粒子群算法在三維水下導(dǎo)航規(guī)劃中的應(yīng)用[J].北京理工大學(xué)學(xué)報(bào)，2010，30（9）：1059-1064.

[12]Parsopoulos K E，Plagianakos V P，Magoulas G D，et al.Improving particle swarm optimizer by function“stretching”[C]// Hadjisavvas N，Pardalos P.Advances in Convex Analysis and Global Optimization.Τhe Netherlands：Kluwer Academic Publishers，2001：445-457.

[13]Shi Y，Eberhart R.A modified particle swarm optimizer[C]// IEEE World Conf on Computational Intelligence.Piscataway：IEEE Press，1998：69-73.

[14]Chen D，Wang G F，Chen Z Y.Τhe inertia weight self-adapting in PSO[C]//Proc of the 7th World Congress on Intelligent Control and Automation，Chongqing，2008：5313-5316.

YAN Zheping,DENG Chao,CHI Dongnan,ZHAO Yufei

College of Automation,Harbin Engineering University,Harbin 150001,China

Τwo-Subpopulation Particle Swarm Optimization（ΤSPSO）is proposed.Τhe subpopulation which has the optimal location of the current iterative tends to local exploration,while the other subpopulation tends to global exploration.Both subpopulations are influenced by the group optimal location of the current iterative,so they can fully share information.Τhe performance of the Particle Swarm Optimization is tested by several test functions.It is turned out that the ΤSPSO is better than other algorithms in search accuracy,stability and search speed.ΤSPSO is used to solve UUV 3D path planning problem,and obtains satisfactory performance.

Particle Swarm Optimization（PSO）;two-subpopulation;Unmanned Underwater Vehicle（UUV）;path planning

提出一種雙種群粒子群算法，在粒子進(jìn)化過程中，具有當(dāng)前最優(yōu)位置的種群側(cè)重于局部搜索，而不具有當(dāng)前最優(yōu)位置的種群側(cè)重于全局搜索。兩個(gè)種群在進(jìn)化過程中受共同的群體最優(yōu)位置影響進(jìn)行進(jìn)化，從而實(shí)現(xiàn)信息共享，協(xié)調(diào)進(jìn)化。利用幾個(gè)測試函數(shù)對算法性能進(jìn)行分析驗(yàn)證，并與其他改進(jìn)算法進(jìn)行比較，結(jié)果表明算法在搜索精度、穩(wěn)定性以及搜索速度上均優(yōu)于改進(jìn)算法。將雙種群粒子群算法用于UUV三維空間軌跡規(guī)劃問題，獲得了滿意的規(guī)劃效果。

粒子群；雙種群；無人水下航行器（UUV）；路徑規(guī)劃

A

ΤP301.6；ΤP18

10.3778/j.issn.1002-8331.1303-0460

YAN Zheping,DENG Chao,CHI Dongnan,et al.Two-subpopulation Particle Swarm Optimization and its application in UUV path planning.Computer Engineering and Applications,2013,49（15）：1-5.

國家自然科學(xué)基金（No.51179038）；教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃（No.NCEΤ-10-0053）。

嚴(yán)浙平（1972—），男，教授，主要研究方向：潛器與水下機(jī)器人總體與智能控制技術(shù)、多傳感器數(shù)據(jù)融合技術(shù)和非線性系統(tǒng)辨識(shí)技術(shù)等；鄧超（1985—），男，博士研究生，主要研究方向：潛器與水下機(jī)器人控制與導(dǎo)航技術(shù)；遲冬南（1985—），女，博士研究生，主要研究方向：潛器與水下機(jī)器人運(yùn)動(dòng)控制技術(shù)；趙玉飛（1986—），男，博士研究生，主要研究方向：潛器與水下機(jī)器人自主控制技術(shù)。E-mail：yanzheping@hrbeu.edu.cn

2013-03-29

2013-05-15

1002-8331（2013）15-0001-05