基于簡(jiǎn)化野草粒子濾波的純距離定位算法*

王 璐，劉 忠

（海軍工程大學(xué)電子工程學(xué)院，武漢 430033）

基于簡(jiǎn)化野草粒子濾波的純距離定位算法*

王 璐，劉 忠

（海軍工程大學(xué)電子工程學(xué)院，武漢 430033）

針對(duì)入侵式野草優(yōu)化粒子濾波算法（IWOPF）在純距離目標(biāo)定位與跟蹤應(yīng)用中計(jì)算量較大的問(wèn)題，提出了一種簡(jiǎn)化野草粒子濾波算法（SIWOPF）。該算法簡(jiǎn)化了有效粒子數(shù)的選取方法，省略了IWOPF中需要通過(guò)最大種群數(shù)目控制粒子數(shù)量的步驟，且在每次迭代選取有效粒子時(shí)優(yōu)先選取適應(yīng)度值較高的粒子，因而在提高算法的運(yùn)算速率的同時(shí)進(jìn)一步提高了算法的估計(jì)精度。仿真結(jié)果表明，新算法適用于純距離系統(tǒng)，且算法性能優(yōu)于粒子濾波算法（PF）、IWOPF算法。

入侵式野草優(yōu)化算法，粒子濾波算法，純距離

0 引言

純距離目標(biāo)定位跟蹤問(wèn)題又稱為純距離目標(biāo)運(yùn)動(dòng)分析，是通過(guò)獲取觀測(cè)站與目標(biāo)的距離信息，并利用這些隨時(shí)間變化的距離序列來(lái)實(shí)時(shí)估計(jì)目標(biāo)運(yùn)動(dòng)參數(shù)的技術(shù)［1-5］。近年來(lái)隨著水下無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的發(fā)展，對(duì)純距離目標(biāo)運(yùn)動(dòng)分析問(wèn)題的研究越來(lái)越迫切。

由于純距離問(wèn)題具有較強(qiáng)的非線性，傳統(tǒng)的估計(jì)方法如PLE、MGEKF等已不再適用。粒子濾波（PF）是目前應(yīng)用比較廣泛的非線性估計(jì)方法［6-7］，但常規(guī)粒子濾波算法存在樣本集貧化現(xiàn)象的重要缺陷，解決該問(wèn)題的方法是增加足夠數(shù)量的粒子，但這會(huì)導(dǎo)致運(yùn)算量急劇膨脹。2006年，Mehrabian和Lucas［8］提出了一種從自然界野草進(jìn)化機(jī)理演化而來(lái)的隨機(jī)搜索方法，稱為入侵式野草優(yōu)化（IWO）方法，該算法具有計(jì)算簡(jiǎn)單、能有效收斂于問(wèn)題最優(yōu)解的特點(diǎn)。文獻(xiàn)［9］將粒子濾波算法與入侵式野草優(yōu)化方法結(jié)合，提出了入侵式野草優(yōu)化粒子濾波算法（IWOPF），有效地解決了粒子濾波樣本集貧化現(xiàn)象，但隨著迭代次數(shù)的增加，粒子數(shù)量也呈非線性增加，雖然可以通過(guò)設(shè)定最大種群數(shù)目控制粒子數(shù)量，但在純距離系統(tǒng)目標(biāo)定位跟蹤應(yīng)用中，計(jì)算量仍偏大。

本文提出了一種簡(jiǎn)化野草粒子濾波算法（SIWOPF），通過(guò)設(shè)定每次迭代后選取的有效粒子數(shù)恒等于初始粒子數(shù)，簡(jiǎn)化了有效粒子數(shù)的選取方法，省略了IWOPF中需要通過(guò)最大種群數(shù)目控制粒子數(shù)量的步驟，提高了算法運(yùn)行速率，且在每次迭代時(shí)選取適應(yīng)度值較高的粒子，進(jìn)一步提高了算法的估計(jì)精度。

1 純距離系統(tǒng)描述

假設(shè)目標(biāo)作勻速直線運(yùn)動(dòng)，觀測(cè)站機(jī)動(dòng)，只考慮運(yùn)動(dòng)平面的兩維情形，坐標(biāo)系如圖1所示。取Y軸為北，X軸為東，坐標(biāo)原點(diǎn)為觀測(cè)站的初始位置，tk時(shí)刻目標(biāo)的運(yùn)動(dòng)狀態(tài)為（xT（tk），yT（tk），vTx（tk），vTy（tk））T，觀測(cè)站運(yùn)動(dòng)狀態(tài)為（xo（tk），yo（tk），vox（tk），voy（tk））T，其中xT（tk）、xo（tk）分別為目標(biāo)、觀測(cè)站位置的X軸分量，yT（tk）、yo（tk）分別為目標(biāo)、觀測(cè)站位置的Y軸分量，vTx（tk）、vox（tk）分別為目標(biāo)、觀測(cè)站速度的X軸分量，vTy（tk）、voy（tk）分別為目標(biāo)、觀測(cè)站速度的Y軸分量，則目標(biāo)與觀測(cè)站的相對(duì)運(yùn)動(dòng)狀態(tài)可表示為：

其中：r（tk）表示tk時(shí)刻目標(biāo)與觀測(cè)站的距離，可簡(jiǎn)寫為tk，測(cè)量噪聲△（tk）是均值為零，方差為R（tk）的高斯白噪聲。

2 簡(jiǎn)化入侵式野草優(yōu)化粒子濾波算法（IWOPF）

2.1 入侵式野草優(yōu)化算法（IWO）

IWO是模擬野草繁殖過(guò)程的隨機(jī)搜索仿生學(xué)優(yōu)化算法，將待求解問(wèn)題轉(zhuǎn)化為目標(biāo)函數(shù)優(yōu)化問(wèn)題。一般來(lái)言，IWO包括以下4個(gè)步驟［10］：

（1）種群初始化。初始化參數(shù)并按函數(shù)定義域要求隨機(jī)產(chǎn)生初始種群。

（2）生長(zhǎng)繁殖。雜草個(gè)體根據(jù)自身適應(yīng)度值、種群中最大和最小適應(yīng)度值產(chǎn)生種子。

式（3）中：Fi為當(dāng)前野草適應(yīng)值，F(xiàn)max和Fmin為常數(shù)，分別表示種群中所有植株適應(yīng)度值的最大、最小值，Nmax和Nmin為常數(shù)，分別表示單個(gè)野草產(chǎn)生種子數(shù)的最大、最小值。式（3）表明，適應(yīng)度高的種子子代數(shù)目多，適應(yīng)度差的個(gè)體也有生存與繁殖的機(jī)會(huì)。

（3）空間擴(kuò)散?？臻g擴(kuò)散體現(xiàn)了算法的隨機(jī)性和適應(yīng)性。第i次迭代后產(chǎn)生的種子在父代雜草個(gè)體附近以正態(tài)分布N（0，σi2）隨機(jī)地?cái)U(kuò)散，稱為子代。進(jìn)化中第i代的標(biāo)準(zhǔn)差σi如下式所示：

式（4）中：itermax表示最大代數(shù)，iter表示當(dāng)前代數(shù)，n為非線性調(diào)和指數(shù)，表示生物群體動(dòng)力學(xué)上的選擇勢(shì)力，一般取為3。σ0為方差初始值，σfinal為方差最終值。

（4）適者生存。每次繁殖迭代后，種群數(shù)量將有可能超過(guò)環(huán)境資源的承受力，需通過(guò)最大種群數(shù)目Pmax控制數(shù)量。

2.2 簡(jiǎn)化入侵式雜草粒子濾波算法（SWIOPF）

IWO算法在進(jìn)化過(guò)程中通過(guò)計(jì)算個(gè)體的適應(yīng)度值選取優(yōu)秀個(gè)體進(jìn)行繁殖進(jìn)化，這與粒子濾波算法中通過(guò)計(jì)算粒子的權(quán)重選擇優(yōu)秀個(gè)體是相似的，因此，可以將IWO中野草個(gè)體適應(yīng)度值與PF中粒子權(quán)重相對(duì)應(yīng)。

令k時(shí)刻第i個(gè)粒子的適應(yīng)度值［11］為

式中：zk為觀測(cè)值，z贊k|k-1為預(yù)測(cè)觀測(cè)值，R為測(cè)量噪聲方差。

這樣就可以從不斷進(jìn)化的粒子集中選取適應(yīng)度值最優(yōu)的粒子，在增加粒子多樣性的同時(shí)跟蹤適應(yīng)度值較大的粒子。

又因?yàn)榱Ｗ訛V波算法在純距離系統(tǒng)實(shí)際應(yīng)用中，如水下聲學(xué)傳感器網(wǎng)絡(luò)定位跟蹤中初始粒子一般選取幾百個(gè)，這種情況下一般2次～3次迭代后，就會(huì)達(dá)到最大種群數(shù)目，此時(shí)重復(fù)判斷是否達(dá)到最大種群數(shù)目沒(méi)有實(shí)際意義，還會(huì)增加算法的計(jì)算量。因此，可以設(shè)定每次迭代后的選取的有效粒子數(shù)恒等于初始粒子數(shù)，在保證粒子多樣性的同時(shí)選取適應(yīng)度值高的粒子，提高了算法精度，同時(shí)省略了利用最大種群數(shù)目控制粒子數(shù)量的步驟，提高了算法的運(yùn)算速率。算法步驟如下：

步驟1：根據(jù)狀態(tài)分布情況產(chǎn)生初始粒子xki，i=1，2，…，N，N為設(shè)定的初始粒子數(shù)；

步驟2：根據(jù)式（5）計(jì)算每個(gè)粒子權(quán)值Fi；

步驟3：根據(jù)式（3）、式（4）計(jì)算每個(gè)粒子xki可產(chǎn)生的種子數(shù)Nseed和標(biāo)準(zhǔn)方差σiter，將每個(gè)粒子xki產(chǎn)生的種子按N（0，σ2iter）分布在父代xki附近；

步驟4：根據(jù)式（5）計(jì)算子代的權(quán)值；

步驟5：子代與父代合并，將所有粒子按適應(yīng)度值降序排列，選取前N個(gè)粒子再次進(jìn)行繁殖迭代，直至迭代次數(shù)等于itermax；

步驟6：狀態(tài)估計(jì)

步驟8:重復(fù)步驟2-步驟7，直至仿真結(jié)束。

算法流程圖如圖2所示。

3 仿真分析

由圖3可以看出，PF、IWOPF、SIWOPF三種算法均能實(shí)現(xiàn)對(duì)目標(biāo)的有效跟蹤，但由圖4、表2可知，SIWOPF算法的誤差最小，估計(jì)精度最佳，這是因?yàn)槊看畏敝车鷷r(shí)，集中選取適應(yīng)度值高的粒子，避免了適應(yīng)度值低的粒子的干擾，使得算法估計(jì)精度明顯提高。在算法運(yùn)行速率方面，PF算法用時(shí)最長(zhǎng)，由于SIWOPF算法改進(jìn)了IWOPF算法中需要通過(guò)最大種群數(shù)目控制粒子數(shù)量的步驟，速率提高了一倍多，更能滿足純距離系統(tǒng)目標(biāo)定位與跟蹤中實(shí)時(shí)性的要求。

仿真結(jié)果表明，SIWOPF算法適用于純距離目標(biāo)定位與跟蹤，且在估計(jì)精度和運(yùn)行速率性能方面，均優(yōu)于PF、IWOPF算法。

4 結(jié)束語(yǔ)

本文提出了一種簡(jiǎn)化野草粒子濾波算法，改進(jìn)了入侵式野草優(yōu)化粒子濾波算法中選取有效粒子數(shù)量的方法，簡(jiǎn)化了算法流程，且在每次迭代過(guò)程中選取適應(yīng)度值較高的粒子，提高了算法的估計(jì)精度。仿真結(jié)果表明，新算法有效提高算法運(yùn)算速率和估計(jì)精度，更能滿足純距離目標(biāo)定位跟蹤中實(shí)時(shí)性的要求。

Measurement［J］．IEEE Journal of Oceanic Engineering，1999，24（3）：383-387.

［2］孫仲康，郭福成，馮道旺．單站無(wú)源定位跟蹤技術(shù)［M］．北京：國(guó)防工業(yè)出版社，2008.

［3］梁玥，劉忠.單站純距離定位與跟蹤系統(tǒng)可觀測(cè)性分析［C］//火力與指揮控制2008年學(xué)術(shù)會(huì)議論文集.太原：火力與指揮控制研究會(huì)，2008:292-297.

［4］梁玥，劉忠．基于全局收斂策略的靜止目標(biāo)純距離測(cè)量下的參數(shù)估計(jì)方法［J］.火力與指揮控制，2010，35（4）：147-149，154.

［5］Wang L，Liu Z.Research on Observability of Non-maneuvering Target Tracking Based on Multiple Observers Range-only［C］//（ICITMI2012）.Guang Zhou，2012:744-748.

［6］Merwe R，Doucet A，F(xiàn)reitas N D，et al.The Unscented Particle Filter［R］.Technical Report Cued/F-Ingeng/Tr 380，Camibridge University Department of Engineering，2000：1-45.

［7］Kotecha J H，Djuric P M.Gaussian Sum Particle Filtering for Dynamic State Space Models［C］//Proceeding of the International Conference on Acoustics，Speech and Signal Processing，Salt Lake City，Utah，Citeseer，2001：3465-3468.

［8］Mehrabian A R，Lucas C.A Novel Numerical Optimization Algorithm Inspired from Weed Colonization［J］.Ecological Informatics，2006，1（3）:355-366.

［9］楊瀾，趙祥模，惠飛，等.入侵式野草優(yōu)化粒子濾波方法［J］.吉林大學(xué)學(xué)報(bào)（工學(xué)版），2013，43（4）：1070-1075.

［10］蘇守寶，方杰，汪繼文，等.基于入侵性雜草克隆的圖像聚類方法［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，36（5）：95-100.

［11］Liang Y，Liu Z.Passive Target Tracking Using an Improved Particle Filter Algorithm Based on Genetic Algorithm［C］//Lecture Notes in Electronical Engineering（ISNN2010）. ShangHai，Springer Verlag，2010：559-566.

［1］Taek L S．Observability of Target Tracking with Range-only

Range-Only Target Location Algorithm Based on Simplified Invasive Weed Particle Filter

WANG Lu，LIU Zhong
（School of Electronic Engineering，Naval University of Engineering，Wuhan 430033，China）

Since the Invasive Weed Particle Filter（IWOPF）has the problem of large amounted of calculation in range-only target location and tracking，an Simplified Invasive Weed Particle Filter（SIWOPF）is proposed.The new algorithm simplifies the selection method of the number of effective particles，the procedure of control the number of effective particles by the maximum number of population is omitted.And every time iterated，the higher value of fitness particle is chosen，so operating speeds and precision of the algorithm are both improved.The simulation results indicate that the SIWOPF can be used in range-only system，and has better performance than Particle Filter（PF）、IWOPF.

invasive weed particle filter，particle filter，Range-Only

TN953

A

1002-0640（2015）10-0065-04

2014-09-05

2014-10-07

軍隊(duì)預(yù)研基金資助項(xiàng)目（編號(hào)：9140A01060113JB11001）

王 璐（1984- ），女，山東嘉祥人，博士研究生。研究方向：目標(biāo)跟蹤與定位，系統(tǒng)建模與仿真。