基于改進蟻群算法的二維MUSIC多譜峰搜索研究

陳 宇，王 彪

(江蘇科技大學，江蘇鎮江212003)

0 引 言

空間信號到達方向(Direction of Arrival, DOA)作為聲吶陣列信號處理的一個重點，其作用在于確定搜索空間信號源的位置。Schmidt[1]在 1979年提出的基于特征分解的多重信號分類(Multiple Signal Classificaion, MUSIC)算法真正突破了瑞利限，實現了超分辨DOA估計，以MUSIC算法為代表的基于特征分解的子空間算法得到了研究者的認可，該類算法一般需要在算法所對應的空間譜函數上進行譜峰搜索，計算量巨大。如何進行快速有效的譜峰搜索一直是研究的熱點，可將譜峰搜索算法分為兩類：無策略搜索算法和策略搜索算法。無策略搜索方法是指這類算法遵循固定的搜索方法來進行譜峰搜索，代表算法為傳統的均勻遍歷法，該算法根據預設的精度要求來對解空間進行遍歷搜索，計算量大，且計算量隨著精度要求的提高而增大。策略搜索算法中，有一類算法是采用分步搜索的辦法，這類算法的特點是先進行粗搜索，再對部分區域進行細搜素，如文獻[2]提出的算法，該算法將噪聲子空間進行分塊，逐步收斂到譜峰附近，再進行細搜素，但是空間中的信號并不能保證服從某一分布，所以分塊的依據有待商榷；如果分塊不合理，會在無信號空間進行搜索從而造成計算資源的浪費。文獻[3-4]提出設置一個門限，然后通過大步進搜索，尋找出高于門限的譜峰所在的一個大致范圍，再在該范圍內進行小步進搜索，尋找出準確的譜峰。但是文中也表示，門限設置的好壞直接影響了算法的成功率。與上述策略算法不同，群智能算法充分利用了空間譜函數的形狀[5-6]，確定相應的搜索策略從而快速收斂到譜峰附近；同時，群智能算法并不需要對空間進行分塊，這大大加強了算法的魯棒性。如文獻[7]提出的基于遺傳算法的MUSIC譜峰搜索技術，文獻[8]提出的基于雞群優化算法的譜峰搜索，都取得了很好的效果，但是由于群智能算法屬于全局優化算法，所以鮮有文章考慮空間中存在多個信號源的情況，也即多譜峰搜索問題。

在實際應用中，水下或者水面經常存在多個信號源，同時有些信號源相距很近，例如海戰中的航母編隊。在該實際背景下如何快速準確地估計出所有信號源的波達方向是本文的研究重點。蟻群算法作為群智能算法中的典型算法，已有非常完善的應用背景與數學理論依據，本文利用蟻群算法來進行DOA估計的研究，并且針對傳統蟻群算法的一些缺陷，提出了更加適合多譜峰搜索的改進蟻群算法，并利用仿真實驗，證明了本文算法的有效性。

1 二維MUSIC算法

1.1 接收信號模型[9]

1.2 MUSIC推導[9]

通過特征分解可以將陣列協方差矩陣R劃分為信號子空間與噪聲子空間兩個空間，即：

2 蟻群算法改進

2.1 蟻群算法介紹[10]

螞蟻在尋找食物時，會在其經過的路徑上釋放一種可以稱之為“信息素”的物質，蟻群內的螞蟻對“信息素”具有感知能力，它們會沿著“信息素”濃度較高的路徑行走，而每只路過的螞蟻都會在路上留下“信息素”，這就形成一種類似正反饋的機制，通過這種機制可以快速找到食物源。而蟻群算法正是利用了這種特性來進行全局優化。

2.2 蟻群算法的改進

2.2.1 聚類分析思想

蟻群算法為全局優化算法，在迭代過程中會不斷收斂到最優解附近。但是DOA估計為多譜峰搜索問題(當存在多個信號源的情況下)，每個譜峰的幅值不一樣，所以蟻群往往聚集到幅值最高的譜峰附近，從而使得其他譜峰處螞蟻較少，影響了估計的精度，也容易造成估計失敗。針對該問題，本文創新地將機器學習中的聚類思想與傳統的蟻群算法相結合，將每個譜峰周圍距離該譜峰最近的螞蟻歸為一類，通過這種方式，使得蟻群可以互不干擾地分開搜索不同的譜峰。該改進的步驟為：假設蟻群規模為，在蟻群迭代開始之前利用信源數K，根據信息素最大且距離較遠的原則從蟻群中找出K個聚類質心點[9-11]{C1,C2,… ,CK}，然后根據誤差平方和最小準則將所有的螞蟻進行聚類。則在第t次迭代中，誤差平方和函數為

聚類完成后再進行算法的剩余部分，一次迭代完成之后再進行重新聚類，重新選取信息素更高的點作為質心點，所以本文提出的算法既是蟻群算法，同時也是完整的聚類算法。通過引入聚類思想，讓屬于不同族的螞蟻去尋找不同的譜峰，從而避免了最高譜峰對蟻群算法性能的影響。

2.2.2 動態調整搜索范圍

本文的蟻群算法采用了局部搜索和全局搜索兩種搜索模式。在一次迭代中，螞蟻采取哪一種搜索方式是由轉移概率決定的；在第t次迭代中，第i個螞蟻的轉移概率公式為[7]

式中：T(…)表示信息素，Ci表示第i個螞蟻所屬族的質心點。則當該螞蟻距離所在質心點較近也即Pi,t較小時，采用局部搜索，其搜索譜峰公式為

當該螞蟻距離所在質心較遠也即Pi,t較大時，采用全局搜索，其搜索公式為

式(11)～(12)中，co,t為第t次迭代后第i個螞蟻的坐標，rnd為0～1之間的隨機數，λt為第t次迭代的步長。dt-1為上次迭代后的搜索范圍的上下邊界差，轉移概率Pi,t的大小往往用一個轉移概率常數來衡量，本文取概率轉移常數為0.05。設置上下邊界可以防止螞蟻跑出搜索范圍，在傳統的蟻群算法中，上下邊界是固定不動的，比如需要搜索 -90°～90°范圍的 DOA，則上界設置為 90°，下界設置為-90°。本文創新地隨著蟻群算法的迭代調整搜索的邊界，從而達到動態調整搜索范圍的效果，調整的準則如下：

在同等仿真條件下，利用Matlab軟件繪制出未使用和使用動態調整搜索范圍的最終螞蟻分布的投影圖，其中圖1(a)未采用動態調整搜索范圍，可以看出蟻群可以分別收斂到三個譜峰附近，但是并不集中，這會造成雖然估計成功，但是收斂速度較慢、誤差較大的問題，而圖1(b)采用了動態調整搜索范圍，可以看出蟻群不僅可以找到三個譜峰，而且收斂得非常緊密，通過這兩張圖的對比，可以看成該改進方法的有效性。

圖1 采用與不采用動態搜索策略蟻群投影圖Fig.1 Ant colony projection diagrams with and without dynamic search strategy

2.3 算法流程

結合了上述兩個改進方法后，蟻群算法流程可以描述為：

(1) 設置最大迭代次數T，蟻群規模為A，目標誤差為ET，信息素揮發常數Rau，轉移概率常數p0，初始化迭代次數T為1，上邊界為Ru,1，下邊界為RL,1。

(2) 隨機設置螞蟻的初始位置，設置每只螞蟻的初始信息素為其空間譜函數上對應的函數值。

(3) 運用聚類分析的思想在蟻群中找出K個質心點，將其余螞蟻分成K個族。

(4) 計算每只螞蟻的狀態轉移概率Pi,t。

(5) 更新每個族的上邊界和下邊界為Ru,k,t(x)，Ru,k,t(y)，Rl,k,t(x)，Rl,k,t(y)。

(6) 通過狀態轉移概率選擇搜索模式。

(7) 對超出搜索范圍的螞蟻進行越界處理。

(8) 更新信息素，更新公式為

式中Tau,i,t為第i個螞蟻在第t次迭代中的信息素，由兩部分組成，加號前為經過揮發后殘余的信息素，加號后為該次迭代中新留下的信息素。

(9) 得出本次迭代估計的譜峰值，即為各個族的質心點Ck,t，計算誤差Et；如果誤差Et小于目標誤差ET，則結束；如果誤差大于目標誤差則轉到步驟(3)，直到達到最大迭代次數或者誤差小于目標誤差。定義均方誤差為

式中：DOAk表示與Ck,t相對應的實際波達方向。通過對誤差取對數可以更好地繪制誤差曲線圖。

3 仿真與結果分析

3.1 實驗設計

主要參數如下：陣元數為M=N=8，為 8×8的均勻面陣；快拍數為500；蟻群規模為400。

3.2 實驗結果

設置信噪比為10 dB，迭代次數為100次，空間存在三個信號源，其波達方向分別為(10°, 15°)、(20°, 35°)和(30°, 55°)，繪制出空間譜函數與迭代前后蟻群分布圖如圖2所示。

圖2(a)為迭代前的蟻群分布圖，可以看出螞蟻隨機地分布在空間譜函數上，圖2(b)經過50 次迭代后，所有的螞蟻被分成了三個族，分別用紅、黃、綠這三種顏色來區分不同的族，并且都收斂到了每個族對應的譜峰上，直觀地說明了算法的有效性。實際DOA估計結果如表1所示。

圖2 迭代前后蟻群分布圖Fig.2 Ant colony distribution maps before and after iteration

表1 DOA估計結果Table 1 DOA estimation results

設置信噪比為20 dB，迭代次數為100次，空間存在三個信號源，其波達方向為(10°, 15°)、(20°, 35°)和(30°, 55°)。本文提出的蟻群算法與傳統蟻群算法的誤差對比如圖3所示，其中紅色為傳統的蟻群算法，藍色為本文改進后的蟻群算法。從圖3可以看出，迭代開始時，兩種算法的誤差大約都為25 dB，經過大約10次迭代后，本文算法的誤差下降到0 dB，快于傳統蟻群算法，經過大約40次迭代后，本文算法的誤差下降到了大約-18 dB，體現出了該算法很高的估計精度。此后，由于受MUSIC算法分辨率限制，誤差基本不再下降。而此時傳統蟻群算法誤差大約為6 dB，在接下來的迭代中，傳統蟻群算法不能保持誤差持續下降的趨勢，最終誤差為3 dB左右，精度明顯低于本文提出的算法。這說明傳統的蟻群算法并不能穩定且快速地進行多譜峰估計，而改進后的蟻群算法能夠很好地完成任務。

圖3 算法改進前后誤差對比圖Fig.3 Comparison of DOA error before and after the algorithm being improved

為了探究信噪比與算法性能的關系，對本文在不同信噪比下多譜峰搜索進行了100次蒙特卡洛仿真，設置波達方向為3個，設置目標誤差為5 dB，最大迭代數為 500。如果在最大迭代數之前達到目標誤差，則認定該次實驗成功，反之認為該次實驗失敗。統計結果如表2所示。

表2 不同信噪比下本文算法性能Table 2 Algorithm performance table under different SNRs

從表2可以看出，本文提出的算法在不同信噪比下迭代次數相差并不大，保證了不同信噪比下快速估計DOA的需求，且在高信噪比的情況下成功率均為100%，體現出本文算法具有較高的魯棒性。但是在低信噪比情況下估計成功率較低，主要原因是低信噪比情況下二維MUSIC算法性能下降較快，有時甚至不會出現明顯的譜峰。在這種情況下，本文的算法往往不能正確找到所有的波達方向，但可以找到空間譜函數中較為明顯的譜峰所對應的波達方向。

為了探究在兩個相近信號源情況下本文算法的性能，設置空間信號源的數量為 2，信噪比為20 dB，假設其波達方向分別為，則兩信號源角度距離D定義為

設置單次實驗最大迭代次數為 100，進行 100次蒙特卡洛實驗。譜峰靠近時搜索結果如圖 4所示。從圖4可以直觀地看出，兩個信號源非?？拷?，其譜峰重疊部分非常大，僅可依稀分辨出兩個峰尖。但是利用本文的算法依然可以準確地找到這兩個信號源的波達方向。

圖4 譜峰靠近時搜索結果Fig.4 Search result graph when the peaks are close to each other

信號源靠近情況下，DOA估計的結果如表 3所示。

通過計算可以得出，表 3所示的估計誤差為-1.3 dB，表明本文的算法可以正確估計出兩個相近信號源的波達方向。

表3 信號源靠近情況下DOA估計結果Table 3 DOA estimation results when the signal sources are close

進一步探究多個空間信號源與信號源之間的角度距離對于算法性能的影響，設置空間信號源數量為2，改變兩個信號源之間的角度距離，進行100次蒙特卡洛實驗，實驗結果統計如表4所示。

表4 不同角度距離下算法性能表Table 4 Algorithm performance table at different angle distances

從表4的結果可以看出，本文改進后的算法的估計成功率不受信號源之間角度距離的影響，可以應對不同的實際情況。

4 結 論

本文針對二維MUSIC算法多譜峰搜索存在的計算量大、容易失敗等問題，提出了將蟻群算法與二維MUSIC相結合的解決辦法，并針對多譜峰搜索的問題對傳統蟻群算法進行了改進，包括與機器學習中的聚類分析相結合以及動態調整搜索范圍。通過仿真可以看出，本文的改進蟻群算法可以很好地按照改進思路進行正確的聚類，并且可以在空間中存在多個信號源以及信號源比較靠近時正確地估計出他們的波達方向。與傳統蟻群算法相比，改進后的蟻群算法可以完成多譜峰搜索且具有更高的估計精度，并且在較高信噪比環境下具有較高的魯棒性。下一步的工作是改進該算法在低信噪比情況下的估計成功率。