一種基于連續(xù)蟻群算法的快速最大似然DOA估計(jì)

王輝輝 陳玉鳳

(1.西安電子工程研究所 西安 710100;2.西北工業(yè)大學(xué)航海學(xué)院 西安 710072)

0 引言

DOA(Direction Of Arrival)估計(jì)在雷達(dá)、聲納、無(wú)線通信、無(wú)源定位等領(lǐng)域有著重要應(yīng)用。最大似然估計(jì)(maximum likelihood，ML)［1］算法是一種漸進(jìn)無(wú)偏估計(jì)，它不僅在高信噪比下性能逼近克拉美羅界，達(dá)到最佳，而且在低信噪比下也具有很好的性能。在方位估計(jì)問(wèn)題中，由于最大似然估計(jì)算法需要在全局進(jìn)行最優(yōu)化求解，因此不可避免引入復(fù)雜的計(jì)算和多維的非線性求解，這會(huì)導(dǎo)致ML算法的收斂性變差，同時(shí)不易求得最優(yōu)解［2］。近些年，為了解決最大似然估計(jì)的計(jì)算量大的問(wèn)題，迭代的方法［3］、遺傳進(jìn)化的方法［4］和馬爾科夫蒙特卡羅的方法［5］被引入ML估計(jì)的求解中，但是這些方法要求給定一個(gè)比較接近真值的初始值，容易收斂到局部極值點(diǎn)，難以收斂到全局最優(yōu)點(diǎn)等問(wèn)題。意大利學(xué)者Dorigo M首次提出了蟻群算法，該算法是一種基于模擬螞蟻覓食行為的模擬進(jìn)化算法。焦亞萌等人將蟻群算法引入到最大似然估計(jì)的求解中，提出了ACOML算法［7］，大大降低了運(yùn)算量，但是該算法使用隨機(jī)分布的策略來(lái)實(shí)現(xiàn)狀態(tài)空間的初始化，因此初始解的遍歷性不能得到很好的保證。本文使用混沌序列代替隨機(jī)序列進(jìn)行狀態(tài)空間的初始化，以增加初始解的遍歷性，同時(shí)為了尋求最優(yōu)解還在全局搜索的基礎(chǔ)上增加了局部搜索，使得計(jì)算量大大的減小，僅為ML方法的1/20，同時(shí)還具有和ML算法一致的分辨估計(jì)精度。

1 ML算法

假設(shè)陣列為均勻線列陣，且具有M個(gè)各向同性的陣元。各陣元接收到的噪聲為加性的高斯白噪聲，且彼此相互獨(dú)立。噪聲均值為零，方差為σ2n。那么對(duì)于N次采樣數(shù)據(jù)的聯(lián)合概率密度函數(shù)為:

上式中‖‖表示Euclidean范數(shù);A()θ表示M×P維陣列流型矩陣，分別表示陣元個(gè)數(shù)和入射信號(hào)源個(gè)數(shù);S表示目標(biāo)信源復(fù)振幅矢量。對(duì)上式兩邊取負(fù)對(duì)數(shù)可得:

2 基于改進(jìn)蟻群算法的最大似然估計(jì)算法(MACOML)

2.1 基于連續(xù)空間的蟻群算法

蟻群算法最早是用來(lái)解決組合優(yōu)化問(wèn)題的，主要是針對(duì)離散空間的，在最優(yōu)解的求解過(guò)程中，螞蟻在搜索路徑上信息量的留存、增減等的選擇，都是通過(guò)點(diǎn)狀分布的方式來(lái)求解的。而連續(xù)空間是用區(qū)域性的方式來(lái)表示解空間的，因此連續(xù)空間的蟻群算法和離散空間的蟻群算法在蟻群尋找最優(yōu)解的方式和策略上有一些不同。對(duì)基于連續(xù)空間的蟻群算法來(lái)說(shuō)，螞蟻在整個(gè)連續(xù)空間的搜索過(guò)程中，螞蟻下一步的搜索是由轉(zhuǎn)移函數(shù)來(lái)確定的，因此轉(zhuǎn)移函數(shù)能夠影響整個(gè)蟻群的行進(jìn)策略，進(jìn)而影響整個(gè)算法，因此對(duì)于連續(xù)空間的蟻群算法要選取合適的轉(zhuǎn)移函數(shù)。對(duì)于連續(xù)空間的蟻群算法，采用最多的就是采用概率密度函數(shù)作為轉(zhuǎn)移函數(shù)，用具有高斯核的概率密度函數(shù)作為連續(xù)空間蟻群算法的轉(zhuǎn)移函數(shù)，如下式所示:

上式中的Θ對(duì)應(yīng)于整個(gè)連續(xù)的搜索空間，i表示整個(gè)搜索空間的維度;wl(l=1，2，…，L)為權(quán)值向量，且ωl(Θ)～N(1，q2L2)，各向量之間相互獨(dú)立;，其中L是搜索空間的抽樣個(gè)數(shù)。

2.2MACOML算法

ACOML算法使用隨機(jī)分布的策略來(lái)實(shí)現(xiàn)狀態(tài)空間的初始化，因此初始解的遍歷性不能得到很好的保證。而混沌序列具有很好的遍歷性，因此本文首先用Logistic映射來(lái)產(chǎn)生一個(gè)混沌序列，用該混沌序列代替隨機(jī)序列來(lái)初始化狀態(tài)空間，然后再將初始解映射到整個(gè)解空間尋優(yōu)的可行域內(nèi)。在蟻群算法的一次迭代過(guò)程中螞蟻沒(méi)有找到最好的解，螞蟻會(huì)向找到較優(yōu)解的螞蟻所在的解空間位置移動(dòng)，這一過(guò)程稱為解空間的全局搜索，在ACOML算法中螞蟻搜索方式只有全局搜索，由于解空間為連續(xù)空間，因此全局搜索得到的解并不一定是該狀態(tài)內(nèi)的最優(yōu)解，因此本文在全局搜索的基礎(chǔ)上增加了局部搜索功能，也就是在算法循環(huán)過(guò)程中，螞蟻要在自身確定的附近的小鄰域范圍內(nèi)進(jìn)行隨機(jī)搜索，得到比當(dāng)前更優(yōu)的解。MACOML算法步驟如下:

a.利用Logistic映射產(chǎn)生初始狀態(tài)空間

其中κ是一個(gè)常數(shù)，且3．5≤κ≤4，用來(lái)表征混沌狀態(tài)的程度，Li(t)∈(0，1)。假設(shè)搜索角度的范圍為，將這個(gè)混沌序列映射到搜索角度的可行域內(nèi)，映射方式如下所示:

對(duì)應(yīng)目標(biāo)函數(shù)值f，將搜索空間進(jìn)行降序排列，目標(biāo)函數(shù)值f為方位的似然估計(jì)值。權(quán)值向量由式(8)計(jì)算:

且wl～N(1，q2L2)。圖1為檔案表，其中的目標(biāo)函數(shù)值、權(quán)值ωl、解狀態(tài)空間一一對(duì)應(yīng)。

圖1 檔案表

b.候選狀態(tài)的更新

在整個(gè)狀態(tài)空間中，螞蟻選擇下一個(gè)狀態(tài)的概率為pl，即以概率pl選取第l個(gè)以為均值，為方差的一維高斯函數(shù)進(jìn)行采樣，如式(9)所示，其中q為一個(gè)可調(diào)參數(shù)。是當(dāng)前選中的狀態(tài)和整個(gè)狀態(tài)空間的平均偏差的修正量，該修正量用信息素?fù)]發(fā)系數(shù)ξ(ξ＞0)來(lái)修正，ξ類似于離散空間中蟻群算法中的揮發(fā)速率。每只螞蟻在整個(gè)搜索空間中以pl選擇當(dāng)前解Θl，在一次迭代過(guò)程中，每只螞蟻只需選擇一次，然后由式(5)確定螞蟻的下一組候選解Φ。

c.局部搜索

一次循環(huán)中螞蟻獲得最優(yōu)解為θi，在其小鄰域范圍內(nèi)再進(jìn)行局部的隨機(jī)搜索。設(shè)隨機(jī)搜索的新位置為 θ0，如果 f(θ0)＞ f(θi)，則 θi= θ0，否則保持當(dāng)前解。搜索是向著最優(yōu)方向?qū)ふ业模虼司植克阉鞯乃阉鞑介L(zhǎng)應(yīng)該隨著循環(huán)次數(shù)的增加而逐步的減小，這樣可以提高搜索速度。局部搜索新位置由式(10)確定，式中σ為局部搜索步長(zhǎng):

局部搜索步長(zhǎng)由(11)式確定:

式中σmax和σmin為常數(shù)值;kk為當(dāng)前循環(huán)次數(shù);iter為循環(huán)次數(shù)。為了降低人為因素，本文通過(guò)隨機(jī)采樣對(duì)步長(zhǎng)進(jìn)行更新，步長(zhǎng)參數(shù)更新由式(12)為:

d.更新?tīng)顟B(tài)空間

根據(jù)新產(chǎn)生的解計(jì)算其目標(biāo)函數(shù)值，若f(Φ)＞f(Θ1)，則ΘL=Φ，其中Θ1，ΘL分別對(duì)應(yīng)狀態(tài)態(tài)空間的第一個(gè)和最后一個(gè)狀態(tài)，根據(jù)目標(biāo)函數(shù)值f將搜索空間進(jìn)行降序排列。否則狀態(tài)空間不發(fā)生變化。

e.迭代結(jié)束判決

3 算法仿真分析

接收基陣為8陣元的均勻線列陣，陣元間距為半波長(zhǎng)。兩個(gè)等強(qiáng)窄帶信號(hào)源入射角分別為-3°和3°，中心頻率為f0=3MHz，采樣頻率為fs=6MHz，采樣快拍數(shù)為100，檔案表中的解的個(gè)數(shù)為L(zhǎng)=100，q=0．1，ξ=0．01。蒙特卡洛實(shí)驗(yàn)次數(shù)為100次。角度掃描范圍為搜索步長(zhǎng)為step=0．2°。利用計(jì)算機(jī)仿真來(lái)評(píng)估算法的性能。

對(duì)于ACOML和MACOML來(lái)說(shuō)，對(duì)于兩個(gè)目標(biāo)的最大似然估計(jì)，兩種方法的螞蟻種群個(gè)數(shù)都是2，也就是幾個(gè)目標(biāo)對(duì)應(yīng)螞蟻種群就有幾只螞蟻。圖2給出了信噪比為5dB時(shí)，ACOML和MACOML的迭代收斂過(guò)程。在經(jīng)過(guò)136次迭代后MACOML算法收斂到最優(yōu)值，而ACOML算法需要710次迭代才能收斂到最優(yōu)結(jié)果。兩種算法在經(jīng)過(guò)迭代后都可以收斂到最優(yōu)解，能夠準(zhǔn)確的估計(jì)目標(biāo)的方位，但是MACOML收斂所使用的次數(shù)明顯少于ACOML算法。

每個(gè)目標(biāo)方位估計(jì)值與其所對(duì)應(yīng)的真實(shí)方位值之差的絕對(duì)值小于相鄰兩個(gè)目標(biāo)真實(shí)值間隔的一半，就認(rèn)為兩個(gè)目標(biāo)是可分辨的。本文中將算法能夠成功分辨兩個(gè)或者多個(gè)目標(biāo)的概率，也就是兩個(gè)目標(biāo)可分辨的概率稱之為分辨概率。圖3是在不同信噪比下三種算法的分辨概率曲線，由圖可知三種算法對(duì)雙目標(biāo)的分別概率幾乎一致。

圖2 優(yōu)化迭代結(jié)果

圖3 分辨概率曲線

本文中對(duì)新算法估計(jì)性能評(píng)價(jià)的另一個(gè)衡量因素為估計(jì)精度的均方誤差(RMSE)，RMSE的計(jì)算是在可分辨的基礎(chǔ)上進(jìn)行的，也就是只統(tǒng)計(jì)可分辨的估計(jì)值，它是對(duì)多次蒙特卡洛實(shí)驗(yàn)的估計(jì)值和真實(shí)值的均方差的一個(gè)平均。圖4為三種算法的均方根誤差曲線。信噪比低于-14dB時(shí)，方位估計(jì)精度均方根誤差起伏較大，這是由于在低信噪比條件下三種方法的分辨概率都已經(jīng)不高，統(tǒng)計(jì)的均方根誤差沒(méi)有實(shí)際意義。

計(jì)算量分析:定義ML算法進(jìn)行一次譜峰搜索所需要的計(jì)算量為Δ，則ML算法的復(fù)雜度為JML=。對(duì)于ACOML和MACOML算法，T，I分別是螞蟻個(gè)數(shù)、達(dá)到估計(jì)精度的最小迭代次數(shù)，則這兩種算法的計(jì)算復(fù)雜度均為 J=。當(dāng)信噪比為0dB時(shí)，MACOML、ACOML兩種方法平均迭代次數(shù)為:IMACOML=185，IACOML=680，則對(duì)于雙目標(biāo)三種算法的計(jì)算量分別為:JML=10000Δ，JACOML=1360Δ，JMACOML=470Δ。

圖4 均方誤差曲線

由以上分析可知三種算法的性能幾乎一致，MACOML算法的計(jì)算量約是ML算法的1/20。，ML的計(jì)算量隨著目標(biāo)個(gè)數(shù)的增多呈指數(shù)增長(zhǎng)，而ACOML、MACOML算法的計(jì)算量則僅僅是線性增長(zhǎng)，因此，當(dāng)目標(biāo)個(gè)數(shù)增大時(shí)本文提出的快速算法的運(yùn)算速度會(huì)更加優(yōu)于ML算法。另外隨著方位的搜索范圍變大，搜索步長(zhǎng)減小，ML算法的計(jì)算量會(huì)增大，而ACOML和MACOML算法不受這些因素的影響。

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

最大似然方位估計(jì)方法在進(jìn)行譜峰搜索時(shí)需要進(jìn)行多維網(wǎng)格非線性搜索，隨著目標(biāo)個(gè)數(shù)增加，計(jì)算量呈指數(shù)關(guān)系增長(zhǎng)，針對(duì)計(jì)算量大的問(wèn)題，本文在ACOML算法的基礎(chǔ)上提出了一種改進(jìn)蟻群算法的最大似然估計(jì)算法MACOML，采用Logistic映射產(chǎn)生的初始狀態(tài)空間來(lái)代替ACOML算法中的隨機(jī)序列產(chǎn)生的初始狀態(tài)空間，提高了初始種群在搜索空間中的均勻性，同時(shí)在尋優(yōu)過(guò)程中增加了局部搜索，給出了算法的詳細(xì)步驟。計(jì)算機(jī)仿真實(shí)驗(yàn)表明:在雙目標(biāo)情況下，新方法保持了最大似然估計(jì)方法的高分辨性能，同時(shí)計(jì)算復(fù)雜度變小，為工程的實(shí)現(xiàn)奠定了重要的基礎(chǔ)。

［1］W.J.Zeng，X.L.Li.High-resolution multiple wideband non stationary source localization with unknown number of source ［J］.IEEE Trans.on Signal Processing，2010，58(6):3125-3136.

［2］A.A.Tadaion，M.Derakhtian，S.Gazor，et al.A fast multiple source detection and localization array signal processing algorithm using the spatial filtering and ML approach ［J］.IEEE Trans.on Signal Processing，2007，55(5):1815-1827.

［3］Petre Stoica，Randolph L.Moses，Benjamin Friedlander，et al.Maximum likelihood estimation of parameters of multiple sinusoids from noisy measurements［J］.IEEE Trans.on A-coustic，Speech，and Signal Processing，1989，37(3):378-392.

［4］M Li，Y Liu.Genetic algorithm based maximum likelihood DOA estimation ［DB］.RADAR，2002，502-506.

［5］金勇，李捷，黃建國(guó)，基于Metropolis-Hastings抽樣的短采樣寬帶信號(hào)近似最大似然方位估計(jì)AML算法［J］.系統(tǒng)工程與電子技術(shù)，2009，31(12):2809-2812.

［6］Colorni A，Dorigo M，Maniezzo V，et al.Distributed Optimization by Ant Colonies.In Proceeding of the 1st European Conference on Artificial Life ［C］.Paris，F(xiàn)rance，1991，134-142.

［7］焦亞萌，黃建國(guó)，侯云山，基于蟻群算法的最大似然方位估計(jì)快速算法，系統(tǒng)工程與電子技術(shù)，2011，33(8):1718-1721.