改進(jìn)鯨魚優(yōu)化算法在無源時差定位中的應(yīng)用*

陳光武， 佘一鳴， 楊菊花， 任 超

(1.蘭州交通大學(xué) 自動控制研究所，甘肅 蘭州 730070；2.甘肅省高原交通信息工程及控制重點(diǎn)實(shí)驗(yàn)室，甘肅 蘭州 730070)

0 引 言

到達(dá)時間差(time difference of arrival,TDOA)技術(shù)在無源定位中具有對硬件要求低、不需要特定的時間戳要求以及精度較高的優(yōu)勢。目前對于TDOA問題的研究有多種方法，一般來說較為常見的有泰勒級數(shù)展開法[1,2]，這種方法的缺點(diǎn)就是迭代初期的初值必須有一定的準(zhǔn)確度，否則容易出現(xiàn)算法不收斂的情況。此外，解決這類問題較為常見的還有最小二乘算法。例如：約束總體最小二乘法，順序最小二乘法等[3～5],這些算法也是處理定位問題的傳統(tǒng)方法。這類算法的優(yōu)勢在于速度快，計(jì)算量少，在噪聲較小時定位精度較高，是當(dāng)前研究較為成熟的方法。文獻(xiàn)[6]提出一種約束最小二乘法，針對約束最小二乘無源定位算法中最優(yōu) Lagrange乘數(shù)的求解問題，提出了新的計(jì)算方法。2014年，曲付勇等人[7]提出的基于約束總體最小二乘法的方法，使非線性問題轉(zhuǎn)變?yōu)閹Ъs束條件的最小二乘模型問題，將約束最小二乘定位解作為約束總體最小二乘的定位解。以上這些針對最小二乘法的改進(jìn)方法雖然在噪聲較小時精度很高，但是卻有兩個顯著的不足：1)這類算法在計(jì)算過程中含有求逆矩陣的步驟，為了使矩陣不出現(xiàn)奇異，必須通過增加觀測站來提升精確度，在三維情況中，在基礎(chǔ)原理上至少需要4個觀測站才可滿足條件，對于改進(jìn)算法所需的觀測站最少也得5個才可比較精確地找到位置；2)這類方法只能用于噪聲較小的環(huán)境，否則就會出現(xiàn)門限效應(yīng)，從而導(dǎo)致精度大幅度下降。

除去上述的各種解析法以外，還有智能優(yōu)化算法被運(yùn)用到這一問題的解決，2005年李俊峰等人[8]提出利用粒子群優(yōu)化算法去解決TDOA問題。2017年劉寶生等人[9]提出利用遺傳優(yōu)化算法對時差問題求解，但其算法的計(jì)算量較大。這類使用智能優(yōu)化算法的方法首先在搜索范圍內(nèi)初始化大量的隨機(jī)點(diǎn)，通過建立符合要求的適應(yīng)度函數(shù)來篩選合適的隨機(jī)點(diǎn)，然后利用迭代過程在這些較好的隨機(jī)點(diǎn)中找出最優(yōu)解，這個解即為目標(biāo)位置。這種方法不存在矩陣求逆的過程，所以，對基站個數(shù)的要求較最小二乘的方法少。

目前使用智能算法處理TDOA問題時一般會出現(xiàn)算法后期收斂太慢，陷入局部最優(yōu)解的問題，還有一些智能算法的控制參數(shù)過多，不但加大了調(diào)整參數(shù)的難度而且還使得計(jì)算速度減慢，所以，找到一種針對這類問題的合適的智能算法顯得十分重要。

2016年，澳大利亞學(xué)者M(jìn)irjalili S根據(jù)座頭鯨的捕食行為，提出了一種新的群體智能算法即鯨魚優(yōu)化算法(whale optimization algorithm，WOA)[10]。這種全局搜索算法的優(yōu)勢在于結(jié)構(gòu)簡單，調(diào)節(jié)的參數(shù)少，運(yùn)算速率快，也間接減少了參數(shù)影響問題。本文將改進(jìn)WOA(improved WOA,IWOA)應(yīng)用于三維時差定位，通過對適應(yīng)度函數(shù)和初始化的調(diào)整，使其更加適合時差問題的解決，并將IWOA算法與其他智能優(yōu)化算法進(jìn)行性能比較。

1 多站TDOA定位模型的建立

在三維時空中建立時差觀測模型，假設(shè)存在M個觀測站，設(shè)定基站的位置Si=[xi,yi,zi]，i=1,2,…,M，目標(biāo)位置L=[x,y,z]。觀測目標(biāo)發(fā)出的信號到達(dá)基站時間ti為

(1)

(2)

eri=ceti

(3)

ri,j=c(ti-tj)=c(ti+eti-tj-etj)=ri+eri-rj-erj

(4)

即

(5)

為了使得似然函數(shù)取得最大值，相當(dāng)于求解式(6)

(6)

2 IWOA

2.1 種群初始化優(yōu)化

將尋找目標(biāo)位置的空間假定為一個N×M維的，N代表的是種群數(shù)量，M則代表空間的維數(shù)，Lm和Um分別表示空間的上下限，m=1,2,…,M，初始化種群的初始位置依據(jù)式(7)在空間中隨機(jī)產(chǎn)生

Xim=Lm+rand(1,3)(Um-Lm)

(7)

初始化的種群散布情況對接下來的搜尋過程有著較大影響，大部分智能算法采用隨機(jī)分布，本文則采取復(fù)雜程度較低的Chan算法[11]先去生成一個初始解，將這個解去替換掉初始種群中的一個隨機(jī)解，對初始種群進(jìn)行優(yōu)化處理。因?yàn)槌跏冀獗容^接近最終估計(jì)解，所以,全局搜索的效率會提升。

2.2 改進(jìn)適應(yīng)度函數(shù)

2.2.1 針對基站不同影響問題

根據(jù)式(6)可以看出，傳統(tǒng)的解析法對于這個問題的求解較為復(fù)雜，本文利用IWOA對其求解，可以根據(jù)式(6)得出適應(yīng)度函數(shù)

(8)

式中X為位置矢量，適應(yīng)度函數(shù)的構(gòu)建將會對算法產(chǎn)生較大影響，結(jié)合式(2)可以得出如下結(jié)論：主基站的到達(dá)時間t1對式(8)中的每一項(xiàng)都有作用，但是從基站的達(dá)到時間ti則對其中的i-1項(xiàng)有影響，可知主從基站存在差異，主基站的影響較大，假如主基站的測量誤差較大，那么對于適應(yīng)度函數(shù)將產(chǎn)生很大影響。

所以做出進(jìn)一步改進(jìn)，改進(jìn)的適應(yīng)度函數(shù)為

(9)

利用式(9)將每個基站作為主基站去處理，消除了主從基站差異。篩選出其中的最小值作為改進(jìn)的f(X)代入方程，具體公式為

f(X)=min[f1(X),f2(X),…,fM(X)]

(10)

(11)

2.2.2 針對優(yōu)化算法調(diào)整

在此基礎(chǔ)上對其進(jìn)一步改進(jìn)，通過引入慣性權(quán)重因子ω協(xié)調(diào)全局和局部性能。具體如下：在運(yùn)算過程中，將各個個體的適應(yīng)度值按大小進(jìn)行排序，將序列分割成兩部分，分別計(jì)算平均數(shù)值fa1fa2(fa1

1)f(i)

此時的個體適應(yīng)度優(yōu)于較好平均值，說明此個體的質(zhì)量較好，此時應(yīng)該在其附近進(jìn)行小范圍運(yùn)動，有利于對局部的搜索能力提升，所以,ω取值(0.8,1.2)之間的隨機(jī)數(shù)。

2)f(i)>fa2

此時個體的適應(yīng)度比較差群體的平均值還差，說明其位置不好，個體應(yīng)該在大范圍移動去尋找有利位置，故此時ω以50%概率選擇(0.3,0.6)或者(1.3,1.6)之間的隨機(jī)數(shù)。

3)f(i)介于兩數(shù)值之間

此時個體的適應(yīng)度數(shù)值不好也不壞，按照一般規(guī)律運(yùn)動即可。ω取值為1即可。

2.3 WOA的優(yōu)化

WOA主要分為3個部分：包圍收縮、覓食以及螺旋式更新。

2.3.1 包圍收縮

座頭鯨識別獵物并且將其包圍，在此過程中以鯨群中處于最佳的捕食位置作為目標(biāo)或最接近目標(biāo)的位置，其他鯨魚向其移動，其表達(dá)式為

(12)

A=2ar-a

C=2r

(13)

式中a為一個控制變量，取值通過a=2-2t/tmax形式變化，tmax為最大迭代次數(shù)，r為(0,1)間隨機(jī)數(shù)。

2.3.2 覓食搜索

在此階段進(jìn)行隨機(jī)搜索行為，表示如下

(14)

2.3.3 螺旋式更新

此階段是模仿座頭鯨狩獵中，鯨魚通過螺旋移動方式向著最優(yōu)解靠近，數(shù)學(xué)模型建立如下

(15)

(16)

其中，第i個鯨魚目前位置和最佳個體的距離關(guān)系，b為個螺旋形狀參數(shù)，l為(-1,1)間的隨機(jī)數(shù)。

此時的鯨魚不僅要以螺旋形式游動而且要收縮包圍獵物，其通過50%的概率在螺旋游動和收縮包圍兩種機(jī)制之間進(jìn)行位置變化，表示如下

(17)

其中，p為(0,1)間隨機(jī)數(shù)。

2.4 IWOA算法步驟

使用IWOA算法針對TDOA定位問題的具體步驟如下：

1)初始化種群和各個參數(shù)。根據(jù)式(7)隨機(jī)初始化種群個體，然后如2.1節(jié)所述，通過使用Chan算法產(chǎn)生一個初始解去替換種群中一個隨機(jī)的個體；

2)對種群計(jì)算適應(yīng)度。通過式(10)分別計(jì)算出當(dāng)前個體的適應(yīng)度值，記錄其中的適應(yīng)度最優(yōu)值個體位置；

3)開始迭代，當(dāng)t

4)位置更新。使用式(17)通過p值選擇行為機(jī)制；

5)計(jì)算更新后種群的適應(yīng)度,通過適應(yīng)度數(shù)值比較進(jìn)行位置替換；

6)重復(fù)步驟(3)～步驟(5)，直至算法到達(dá)迭代次數(shù)的門限，輸出最優(yōu)食物位置以及其適應(yīng)度取值,此時的獵物位置就是目標(biāo)的估計(jì)位置。

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

3.1 收斂性能分析

本文設(shè)定三維時空模型，在此條件下，通過與常見的粒子群(PSO)算法及其改進(jìn)權(quán)重的粒子群(IPSO)算法，遺傳算法(GA)，經(jīng)典WOA進(jìn)行對比，驗(yàn)證IWOA對于TDOA非線性問題求解的性能，仿真實(shí)驗(yàn)的環(huán)境設(shè)定如下：基站按照Y型分布，在地上的基站的坐標(biāo)分別為，主觀測站S1=[0,0,0]，從觀測站S2=[0,15,0]，S3=[-10,10,0]，S4=[-10,-10,0]，目標(biāo)位置L=[80,55,20]，單位km。

種群數(shù)為40，迭代上限為500，以此條件進(jìn)行迭代運(yùn)算，以反應(yīng)其不同算法針對TDOA問題計(jì)算的特性，結(jié)果如圖1所示。

圖1 算法迭代對比

從圖1中可以看出，經(jīng)過500次的迭代過程，曲線均是可以收斂的，前期過程中可以看出，IWOA算法由于引入了初始解，初始種群更接近全局最優(yōu)解，其搜索范圍相比其他算法更有效，效率也較其他算法有提升，減緩了智能算法迭代次數(shù)多的劣勢。其他算法由于前期過程需要在整個空間中做充分的全局搜尋工作，所以，需要進(jìn)行更多次迭代才可以收斂到較小值。

在迭代的后期，IWOA相比于經(jīng)典WOA采取了一種新的適應(yīng)度函數(shù)策略，其對個體位置好壞的評價標(biāo)準(zhǔn)更準(zhǔn)確，使得算法可以收斂到更低的適應(yīng)度值，而其他智能算法都是采用一般的適應(yīng)度函數(shù)，所以其最后收斂結(jié)果近似且高于IWOA。在后期，IWOA的適應(yīng)度已經(jīng)明顯低于IPSO算法了，此外值得注意的是，在仿真的過程中，PSO及其IPSO算法，GA很容易出現(xiàn)問題，會出現(xiàn)因?yàn)閰?shù)設(shè)置問題導(dǎo)致收斂結(jié)果出現(xiàn)問題，而且這類智能算法的參數(shù)比較多，對收斂的速度和效率的影響較大，在實(shí)際中找到最優(yōu)參數(shù)是很困難的，IWOA在這一方面與其相比有著明顯的優(yōu)勢。

3.2 精度分析

為了觀察算法在位置判斷中的精確性，對不同位置的目標(biāo)源進(jìn)行位置判斷，采用Monte-Carlo方法仿真統(tǒng)計(jì)各個算法的定位正確率。仿真條件為，上界ub=[100,100,50]，下界lb=[-100,-100,0]，單位km，最大迭代次數(shù)600次，種群數(shù)40，對各個目標(biāo)源進(jìn)行5000次的Monte-Carlo仿真實(shí)驗(yàn)，并與WOA，PSO及其IPSO算法進(jìn)行比較，設(shè)定距離超過15 m即為錯誤，實(shí)驗(yàn)結(jié)果如表1所示。

表1 定位正確率 %

從表1中可以看出，在目標(biāo)位置較近的情況下，幾種算法的準(zhǔn)確率都是比較高的，當(dāng)目標(biāo)源位置開始變遠(yuǎn)時，幾種算法便出現(xiàn)差異性，PSO算法和WOA的正確率開始降低。IPSO通過改進(jìn)線性權(quán)重，在迭代后期，其由于權(quán)重數(shù)值變小，個體的移動步長也隨其減少，所以在后期時其強(qiáng)于PSO算法，另外PSO算法的過程中很容易陷入到局部極值之中，所以其準(zhǔn)確率較低。

相比于PSO及其改進(jìn)算法，IWOA更適合處理TDOA定位問題，其算法中特有的搜索策略使得權(quán)值隨適應(yīng)度函數(shù)值隨機(jī)調(diào)整，使得種群在尋優(yōu)中更加多樣化，即增強(qiáng)了全局搜索的隨機(jī)性，提升全局搜索能力，平衡了局部探索和全局最優(yōu)的問題。從結(jié)果看出，條件相同時，IWOA的準(zhǔn)確率較高，其面對不同的目標(biāo)位置時，算法的穩(wěn)定性也比較好。

圖2 實(shí)驗(yàn)結(jié)果

根據(jù)試驗(yàn)結(jié)果可以看出，在目標(biāo)較近時，幾種算法都沒有出現(xiàn)太大的波動，IWOA比較貼合克拉美羅界，其他算法曲線相比之下略高于IWOA曲線。對于遠(yuǎn)場的目標(biāo)，IWOA的精度更高，可以更好地接近克拉美羅界。綜上，IWOA的穩(wěn)定性較好，精度更高。另外，由于PSO及其改進(jìn)算法，GA等涉及參數(shù)較多，且選取適合的參數(shù)需要更多的條件，所以復(fù)雜度較大，而IWOA的參數(shù)較少，且由于改進(jìn)了適應(yīng)度函數(shù)，計(jì)算結(jié)果更為準(zhǔn)確，相對其他算法結(jié)構(gòu)簡單，且精度更高。在所選試驗(yàn)誤差功率下，實(shí)驗(yàn)中幾種算法沒有出現(xiàn)因門限問題導(dǎo)致的大幅度曲線波動，曲線變化較平穩(wěn)。

4 結(jié)束語

本文針對時差定位非線性問題使用了一種新型的鯨魚優(yōu)化算法(IWOA)，通過對初始種群和適應(yīng)度函數(shù)的調(diào)整，使得本文算法更加貼合定位問題。通過與其他智能優(yōu)化算法的定位性能比較，結(jié)果表明，IWOA具有結(jié)構(gòu)簡單，計(jì)算效率較高，定位的精度高且穩(wěn)定性好的優(yōu)勢，對于實(shí)際利用基站定位有一定參考價值。