一種基于連續蟻群算法的快速最大似然DOA估計

王輝輝 陳玉鳳

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

0 引言

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

1 ML算法

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

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

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

2.1 基于連續空間的蟻群算法

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

上式中的Θ對應于整個連續的搜索空間，i表示整個搜索空間的維度;wl(l=1，2，…，L)為權值向量，且ωl(Θ)～N(1，q2L2)，各向量之間相互獨立;，其中L是搜索空間的抽樣個數。

2.2MACOML算法

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

a.利用Logistic映射產生初始狀態空間

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

對應目標函數值f，將搜索空間進行降序排列，目標函數值f為方位的似然估計值。權值向量由式(8)計算:

且wl～N(1，q2L2)。圖1為檔案表，其中的目標函數值、權值ωl、解狀態空間一一對應。

圖1 檔案表

b.候選狀態的更新

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

c.局部搜索

一次循環中螞蟻獲得最優解為θi，在其小鄰域范圍內再進行局部的隨機搜索。設隨機搜索的新位置為 θ0，如果 f(θ0)＞ f(θi)，則 θi= θ0，否則保持當前解。搜索是向著最優方向尋找的，因此局部搜索的搜索步長應該隨著循環次數的增加而逐步的減小，這樣可以提高搜索速度。局部搜索新位置由式(10)確定，式中σ為局部搜索步長:

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

式中σmax和σmin為常數值;kk為當前循環次數;iter為循環次數。為了降低人為因素，本文通過隨機采樣對步長進行更新，步長參數更新由式(12)為:

d.更新狀態空間

根據新產生的解計算其目標函數值，若f(Φ)＞f(Θ1)，則ΘL=Φ，其中Θ1，ΘL分別對應狀態態空間的第一個和最后一個狀態，根據目標函數值f將搜索空間進行降序排列。否則狀態空間不發生變化。

e.迭代結束判決

3 算法仿真分析

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

對于ACOML和MACOML來說，對于兩個目標的最大似然估計，兩種方法的螞蟻種群個數都是2，也就是幾個目標對應螞蟻種群就有幾只螞蟻。圖2給出了信噪比為5dB時，ACOML和MACOML的迭代收斂過程。在經過136次迭代后MACOML算法收斂到最優值，而ACOML算法需要710次迭代才能收斂到最優結果。兩種算法在經過迭代后都可以收斂到最優解，能夠準確的估計目標的方位，但是MACOML收斂所使用的次數明顯少于ACOML算法。

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

圖2 優化迭代結果

圖3 分辨概率曲線

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

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

圖4 均方誤差曲線

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

4 結束語

最大似然方位估計方法在進行譜峰搜索時需要進行多維網格非線性搜索，隨著目標個數增加，計算量呈指數關系增長，針對計算量大的問題，本文在ACOML算法的基礎上提出了一種改進蟻群算法的最大似然估計算法MACOML，采用Logistic映射產生的初始狀態空間來代替ACOML算法中的隨機序列產生的初始狀態空間，提高了初始種群在搜索空間中的均勻性，同時在尋優過程中增加了局部搜索，給出了算法的詳細步驟。計算機仿真實驗表明:在雙目標情況下，新方法保持了最大似然估計方法的高分辨性能，同時計算復雜度變小，為工程的實現奠定了重要的基礎。

［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］金勇，李捷，黃建國，基于Metropolis-Hastings抽樣的短采樣寬帶信號近似最大似然方位估計AML算法［J］.系統工程與電子技術，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，France，1991，134-142.

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