基于改進(jìn)野狗優(yōu)化算法的二維MUSIC聲源定位研究

張藍(lán)方，韋峻峰*，廖燦杰，倪童錚

（1. 廣西民族大學(xué)電子信息學(xué)院，南寧 530000；2. 廣西高校智慧無人系統(tǒng)與智能裝備重點實驗室，南寧 530000）

0 引言

聲源定位技術(shù)在安防技術(shù)［1］、工業(yè)檢測和軍事探測［2］等領(lǐng)域應(yīng)用廣泛而備受關(guān)注。目前大體有三類聲源定位的方法，分別是基于高分辨率譜估計的定向技術(shù)、基于到達(dá)時間差定位技術(shù)和基于最大輸出功率的可控波束形成技術(shù)［3］。其中，基于特征分解的多重信號分類（multiple signal classificaion，MUSIC）算法［4］就屬于基于高分辨率譜估計的定位方法，該算法實現(xiàn)了超分辨空間信號到達(dá)方向估計，其中最關(guān)鍵的一步為譜峰搜索，此步驟所采用的網(wǎng)格搜索法雖搜索精度高，但存在計算量巨大、實時性差的問題，難以較好地在工程中應(yīng)用。近年來，已有學(xué)者嘗試引入群智能算法來解決譜峰搜索過程復(fù)雜的問題。如將遺傳算法［5］、雞群優(yōu)化算法［6］和改進(jìn)蟻群算法［7］應(yīng)用到MUSIC算法的譜峰搜索部分，它們雖然降低了算法的計算復(fù)雜度，也有較好的精度，但是這些算法仍然有著易陷入局部最優(yōu)值、收斂速度慢的問題。

針對上述現(xiàn)象，本文介紹了野狗優(yōu)化算法（dingo optimization algorithm，DOA）的改進(jìn)版本，DOA是由Peraza-Vázquez等［8］在2021年提出的一種新穎的求解優(yōu)化問題的仿生算法，具有較好的性能。Milenkovi? 等［9］已成功將DOA應(yīng)用于求解連續(xù)工程問題。為了使野狗算法性能更優(yōu)，Almazán-Covarrubias等［10］在生存標(biāo)準(zhǔn)中加入了局部搜索程序，一定程度上提高了收斂速度和精度。但野狗優(yōu)化算法仍存在優(yōu)化的余地。

本文提出一種基于精英反向?qū)W習(xí)機制［11］和二次插值［12］的改進(jìn)野狗優(yōu)化算法（improved dingo optimization algorithm，IDOA）。一方面，在種群初始化和每一次種群迭代的過程中采用精英反向?qū)W習(xí)方法，避免了種群多樣性差的問題；另一方面，引入二次插值方法，可以使算法得到更優(yōu)的局部搜索性能。本文將改進(jìn)野狗算法與傳統(tǒng)二維MUSIC 算法的譜峰搜索部分相結(jié)合，使用IDOA 算法代替網(wǎng)格搜索法，以進(jìn)一步降低計算復(fù)雜度，提高M(jìn)USIC 算法聲源定位的實時性。

1 二維MUSIC算法

本文采用均勻線陣，假設(shè)有N個波長為λ的非相干窄帶，以不同的方位角θ和俯仰角φ從遠(yuǎn)場入射到含M個陣元數(shù)的均勻線性陣上，入射信號源為S，將各陣元接收到的信號轉(zhuǎn)化成矢量表達(dá)如下：

其中：X(t)為M× 1 維接收數(shù)據(jù)矢量，S(t)是N× 1 維信號源矢量，A(θ,φ)是M×N維陣列導(dǎo)向矢量，N(t)是M× 1維噪聲矢量，且：

則陣列數(shù)據(jù)協(xié)方差矩陣為

其中：Rs是信號協(xié)方差矩陣，σ2I是噪聲協(xié)方差矩陣。由于噪聲子空間和信號子空間的正交特性，可將R矩陣進(jìn)行奇異值分解得到噪聲子空間UN和信號子空間US。則得出二維MUSIC 算法定義的空間譜函數(shù)為

對P(θ,φ)進(jìn)行二維譜峰搜索，獲得的譜峰所在的角度即為所要估計的信號波達(dá)方向角。

2 野狗算法改進(jìn)

2.1 野狗算法

2.1.1 進(jìn)攻策略

策略一：群體攻擊。捕食者通常使用高度智能的狩獵技術(shù)，野狗通常單獨捕食小獵物，如兔子；但當(dāng)捕食大獵物，如袋鼠時，它們會成群結(jié)隊。野狗能找到獵物的位置并將其包圍，其行為如式子（5）所示：

策略二：迫害攻擊。野狗通常捕獵小獵物，直到單獨捕獲為止。式子（6）模擬了野狗在單獨捕獲獵物時的軌跡：

策略三：清掃行為。野狗在棲息地隨意行走時，發(fā)現(xiàn)腐肉可供食用的行為。式子（7）用于模擬此行為：

其中：(t+ 1) 是搜索代理的新位置（表示野狗的移動）；na是在［2,SizePop/2］的倒數(shù)中生成的隨機整數(shù)；SizePop 是種群的規(guī)模。(t)是搜索代理（會攻擊的野狗）的子集，其中φ?X，X是隨機生成的野狗種群，(t)是當(dāng)前的搜索代理，(t)是從上一次迭代中找到的最佳搜索代理，β1是在［-2，2］內(nèi)均勻生成的隨機數(shù)，這是一個改變野狗軌跡大小和感覺的比例因子，β2是在［-1，1］區(qū)間內(nèi)均勻生成的隨機數(shù)，(t)是選擇的第1 個搜索代理，其中i≠r1。fitnessmax和fitnessmin分別是當(dāng)前一代中最差和最好的適應(yīng)度值，而fitness(i)是第i個野狗的當(dāng)前適應(yīng)度值。σ是由算法隨機生成的二進(jìn)制數(shù)，σ∈{ 0,1} 。

2.1.2 存活策略

澳大利亞野狗面臨滅絕的危險，主要是因為非法狩獵。在DOA 算法中，野狗的存活率值由式子（8）提供：

其中：fitnessmax和fitnessmin分別是當(dāng)前一代中最差和最好的適應(yīng)度值，而fitness( )i是第i個搜索代理的當(dāng)前適應(yīng)度值。式子（9）應(yīng)用于生存率值等于或小于0.3的搜索代理。

2.2 精英反向?qū)W習(xí)機制

對于群智能優(yōu)化算法而言，初始種群的質(zhì)量至關(guān)重要，種群質(zhì)量的好壞會影響算法尋優(yōu)能力的強弱，優(yōu)質(zhì)的初始種群能提升算法收斂速度以及得到更好的全局尋優(yōu)能力。目前精英反向?qū)W習(xí)已被較好地應(yīng)用于多種算法的改進(jìn)。郭雨鑫等［13］引入EOBL改進(jìn)哈里斯鷹算法，提高了算法的種群質(zhì)量；何小龍等［14］將EOBL運用到鯨魚優(yōu)化算法的初始化種群和每次種群迭代中，增加了算法的種群多樣性。另一方面，野狗算法的局部搜索能力還有進(jìn)一步提升的空間。

而Peraza-Vázquez 等［8］的DOA 算法沒有關(guān)于搜索空間的先驗信息，初始化種群采取的方式是隨機的，算法根據(jù)目前找到的最優(yōu)野狗個體位置來更新其它個體位置，就可能會致使野狗種群多樣性差、收斂速度慢的問題。若通過產(chǎn)生精英反向種群與初始種群一起競爭，選擇出優(yōu)秀個體作為下一代種群的方式引入先驗信息，不僅可以擴大可行解的范圍還保存了較優(yōu)解，還提高了野狗種群多樣性和質(zhì)量。

定義1：精英反向解［15］。假設(shè)為當(dāng)前種群內(nèi)的精英個體，則精英個體的反向解定義為

其中：k為［0,1］區(qū)間上的隨機數(shù)，lbj與ubj分別是動態(tài)邊界的下界與上界。動態(tài)邊界更易保存搜索經(jīng)驗，可增加算法的尋優(yōu)速度。當(dāng)越過邊界變?yōu)榉强尚薪鈺r，則使用以下公式來重置：

2.3 二次插值方法

二次插值［12］的基本思想是在確定初始區(qū)間中，不斷使用二次多項式去近似目標(biāo)函數(shù)，隨著區(qū)間的逐步縮小，二次多項式所得最優(yōu)解與研究問題最優(yōu)解之間的距離也逐漸縮短。此方法已經(jīng)成功應(yīng)用于多種算法的優(yōu)化。如Guo等［16］結(jié)合二次插值策略改進(jìn)正弦余弦算法；廖列法等［17］引入二次插值有效提升了天牛須搜索算法跳出局部最優(yōu)的能力；高建瓴等［18］使用二次插值法改進(jìn)包圍策略，提高哈里斯鷹算法局部搜索能力。

本文提出將二次插值方法引入DOA算法中，利用這種方法提高DOA 算法的局部探索能力，提高算法的收斂速度和搜索精度。該方法的步驟如下：

假設(shè)三個個體，分別是X=(x1,x2,…,xd),Y=(y1,y2,…,yd),Z=(z1,z2,…,zd)，其中X、Y是隨機選取的兩個個體，Z具有最優(yōu)適應(yīng)度值，其中d是要求解問題的維度，適應(yīng)度值分別是f(X)，f(Y)，f(Z)，使用二次插值法，通過式（12）生成新的個體使其與目前全局最優(yōu)位置進(jìn)行比對，擇優(yōu)作為新的全局最優(yōu)位置。

其中：j= 1,2,…,d。新產(chǎn)生的個體Xˉ必然是二次曲線的極小值點。

2.4 改進(jìn)算法IDOA的流程

結(jié)合了上述兩個改進(jìn)方法后，IDOA 算法的步驟為：

步驟1：使用精英反向?qū)W習(xí)策略對野狗種群進(jìn)行初始化，隨機生成N個野狗個體的位置，初始化研究問題維度dim、最大迭代次數(shù)tmax；

步驟2：根據(jù)目標(biāo)函數(shù)計算每只野狗個體的適應(yīng)度值，個體之間相互比較適應(yīng)度值，記錄當(dāng)前種群的最優(yōu)值個體的位置；

步驟3：通過策略一、二、三更新野狗的位置；

步驟4：再通過策略四計算野狗的存活率，當(dāng)存活率值survival( )i≤0.3 時，通過式（9）更新存活率低的野狗；

步驟5：計算新野狗的適應(yīng)度值，再次比較當(dāng)前種群野狗個體之間的適應(yīng)度值，找出全局最優(yōu)值；

步驟6：引入二次插值策略，按照式（13）更新個體位置，計算并比較野狗個體的適應(yīng)度值，更新最佳位置；

步驟7：判斷算法是否達(dá)到終止條件（達(dá)到最大迭代次數(shù)），若達(dá)到，則跳轉(zhuǎn)步驟7，否則轉(zhuǎn)至步驟2；

步驟8：輸出問題最優(yōu)值。

3 實驗仿真與結(jié)果分析

3.1 實驗設(shè)計

在仿真實驗中，式（4）的空間譜函數(shù)P(θ,φ)即為實驗的目標(biāo)函數(shù)。在高斯白噪聲條件下進(jìn)行，采用3陣元線性陣，角度搜索范圍為（-90°，90°），陣元間距為半波長，種群規(guī)模為50，快拍數(shù)為512，信噪比SNR=10 dB，最大迭代次數(shù)tmax=100，傳統(tǒng)網(wǎng)格的搜索步長Δ=0.1，信號源數(shù)為M=1。

由于MUSIC 算法的計算過程中消耗時間最多、計算量最大的部分是譜峰搜索部分，故本文提出將IDOA算法應(yīng)用在MUSIC算法的譜峰搜索部分中。下面將通過仿真實驗將改進(jìn)后算法與傳統(tǒng)二維MUSIC 算法在精度、時間上的表現(xiàn)進(jìn)行對比。

3.2 實驗結(jié)果

本文算法的譜峰搜索結(jié)果如圖1所示，對比MUSIC 算法和改進(jìn)后算法對不同方位入射角的波達(dá)方向估計結(jié)果參見表1。其中，設(shè)定入射角與算法搜索結(jié)果之間差值的絕對值即為下表所示的誤差。

表1 不同方位的波達(dá)方向估計結(jié)果比較單位：（°）

圖1 不同方位的譜峰搜索圖

傳統(tǒng)MUSIC 算法與本文改進(jìn)后算法的搜索結(jié)果分別用(θ1,φ1)和(θ2,φ2)表示，兩種算法的測量誤差分別用(Δθ1,Δφ1)和(Δθ2,Δφ2)表示。

由實驗結(jié)果可知，本文算法與原算法相比搜索精度得到了提高，且搜索誤差均在0.2°以內(nèi)，搜索誤差小，故使用IDOA 算法優(yōu)化二維MUSIC算法的譜峰搜索部分是可行的、有效的。

下面進(jìn)行時間復(fù)雜度分析。對于傳統(tǒng)網(wǎng)格搜索方法，當(dāng)以二維角度搜索時，主要是最大角度的維度與搜索步長影響著其時間復(fù)雜度，其公式如下：

其中：(θmax-θmin)和(φmax-φmin)分別代表著方位角和俯仰角的搜索范圍；Δθ和Δφ分別是方位角與俯仰角的搜索步長。則通過式（14）可知傳統(tǒng)網(wǎng)格搜索法的時間復(fù)雜度為O(3.24 × 106)。對于本文的IDOA 算法，其時間復(fù)雜度由種群數(shù)量與最大迭代次數(shù)tmax決定，則可知IDOA 算法的時間復(fù)雜度為O(5 × 103)。由此可以看出，使用IDOA 算法能夠大大降低譜峰搜索的時間復(fù)雜度。比較MUSIC 算法和本文優(yōu)化后算法進(jìn)行譜峰搜索所用時間，結(jié)果如表2所示。

表2 譜峰搜索用時比較

由表2 數(shù)據(jù)可以看出，在此次仿真實驗中，采用傳統(tǒng)MUSIC 算法的用時基本在2 s 左右，而本文改進(jìn)后算法搜索所耗費的時間基本穩(wěn)定在0.2 s 左右，節(jié)省了約88%的運行時間，說明基于IDOA改進(jìn)的MUSIC譜峰搜索方法，大大縮短了搜索時長，提高了譜峰搜索的速度，增強了算法的尋優(yōu)能力。

4 結(jié)語

本文針對傳統(tǒng)MUSIC 算法存在實時性差、計算復(fù)雜的缺陷，提出將改進(jìn)野狗算法應(yīng)用在傳統(tǒng)二維MUSIC 算法的譜峰搜索部分。實驗結(jié)果證明，改進(jìn)后算法在提升原算法的定位精度的同時，還降低了計算復(fù)雜度，減少了計算量與搜索時長，改進(jìn)后算法的整體性能更優(yōu)，在實際生活中能夠有更廣闊的應(yīng)用前景。本文已經(jīng)初步驗證了改進(jìn)野狗算法對于提升聲源定位性能的有效性，今后的工作方向主要是擴展改進(jìn)野狗優(yōu)化算法的應(yīng)用領(lǐng)域。