模擬退火遺傳算法在DOA估計技術中的應用

賈偉娜，劉順蘭

Jia Wei-na，Liu Shun-lan

杭州電子科技大學通信工程學院，浙江 杭州 310018

School of communication Engineering，Hangzhou Dianzi University，Hangzhou Zhejiang 310018，China

1 引言

波達方向（Direction of Arrival，DOA）估計技術利用傳感器陣列接收的信號對目標的方位進行估計，其算法的優劣直接影響著 DOA估計的性能。早期的常規 DOA估計方法分辨不出同一個波束寬度內的空間目標。為了提高 DOA估計的分辨率，很多學者對此進行了研究并提出了一系列高分辨DOA估計算法，如MUSIC算法[1]、ESPRIT算法[2]、WSF算法[3]等。其中WSF算法具有思想簡單、估計性能優越的特點，尤其是在低信噪比、小快拍數據情況下，該算法比子空間分解算法（如MUSIC、ESPRIT）性能好得多，并且在相干信源情況下仍能有效估計[4]。但WSF算法涉及到非線性多維搜索，真實角度的搜索是非常耗時的。這是該算法在實際應用中遇到的瓶頸問題。為了解決該問題，目前已經提出有交替投影、高斯-牛頓等搜索算法，其中高斯-牛頓算法[3]是一種常用算法，但是這類搜索算法涉及到參數初始值的選取，且初始值選擇的好壞直接影響著算法的性能。

遺傳算法（Genetic Algorithm，GA）[5]是一種借鑒生物的自然選擇和遺傳進化機制的全局優化自適應概率搜索算法，適于求解復雜的優化問題，具有很強的魯棒性。近年來，遺傳算法在方位估計中得到了應用。文獻[6]在無噪的條件下，通過遺傳算法求解信號參數。文獻[7]將遺傳算法引入到DOA估計中，提出了一種快速DOA估計的新方法—基于最大似然的DOA估計遺傳算法。文獻[8]將遺傳算法應用在目標波束空間 DOA估計中，提出了一種基于寬帶目標波束空間DOA估計的新方法。但是基本遺傳算法存在局部搜索能力較差和后期搜索遲鈍等問題[9]。模擬退火算法（Simulated Annealing，SA）[10]是一種基于熱力學退火機理的隨機組合優化算法，具有較強的局部尋優能力。若將模擬退火思想應用到遺傳算法中去，能克服遺傳算法易陷入局部最優的缺點，并使搜索朝著全局最優化方向進行。

本文研究模擬退火遺傳算法在 DOA估計技術中的應用，利用模擬退火遺傳算法解決子空間擬合（WSF）的 DOA估計中非線性多維搜索的問題。計算機仿真結果表明：基于模擬退火遺傳算法的DOA估計方法在低信噪比條件下比基本遺傳算法、高斯-牛頓算法有更高的分辨概率，更小的均方誤差。

2 陣列模型

為了便于分析，本文以均勻線陣為例。假設有P個遠場窄帶信號入射到空間某陣列上，陣列天線由M個陣元組成，陣元間距為d。則陣列輸出表示為

式（1）中，X(t)為陣列的M×1維快拍數據矢量，N(t)為陣列的M×1維噪聲數據矢量，S(t)為P×1維的信號數據矢量，為M×P維陣列方向矩陣，其中第i個信號的導向矢量為[]T表示矩陣轉置。

若假設P＜M，噪聲為理想高斯白噪聲，功率為2σ，且各陣元間噪聲、噪聲與信號之間相互獨立，則陣列輸出的協方差矩陣為

式（2）中，Rs為信號協方差矩陣，I為單位矩陣。

對R進行特征分解，考慮到信號源相干或非相干的情況，Rs的秩P′會小于等于信源個數P，則有

式（3）中，Us=[e1，e2，…，eP′]為信號子空間，UN=[eP′+1，eP′+2，…，eM]為噪聲子空間，Σs=diag(λ1，λ2，…，λP′)為信號特征值組成的對角陣，噪聲特征值組成的對角陣為ΣN=diag(λP′+1，λP′+2，…，λM)。

3 加權子空間擬合（WSF）算法

加權子空間擬合相當于子空間之間的擬合，既接收數據的子空間與實際信號導向矢量組成的子空間之間的擬合。文獻[3]中給出了 WSF準則一般表達式

文獻[3]中指出，當加權矩陣W滿足下式時，Θ估計的方差最小。即

最后，將式（5）、（6）代入式（4）中化簡可得WSF算法最終表達式為

4 模擬退火遺傳算法

4.1 遺傳算法

遺傳算法（GA）模擬生物自然選擇和遺傳進化中發生的復制、交叉、變異等現象，以編碼空間代替問題的可行解空間，以適應度函數作為個體評價依據，從任一初始種群開始，通過隨機的選擇、交叉和變異操作，產生更適應環境的子代群體，使得群體朝著最有希望的區域進化，通過這樣的迭代過程不斷繁衍進化，最后收斂到最適應環境的群體，繼而可求出問題的最優解。圖1是遺傳算法的運算過程示意圖。

圖1 遺傳算法的運算過程示意

然而實踐應用中，遺傳算法在運算過程中很快收斂到局部最優解，并且運算后期在最優解附近左右擺動，收斂較慢[9]。

4.2 模擬退火算法

模擬退火算法（SA）是一種基于金屬退火機理的隨機尋優算法，通過隨機搜索技術從概率意義上找出目標函數的全局最小點。在尋優過程中，當前解xold經隨機擾動產生新解xnew，新解的接受概率由Meteopolis準則確定，即

式（8）中，Δ=f(xnew)-f(xold)為目標函數增量，Ti為當前溫度值。

使用上述準則優勢在于：當新解為更優解（即Δ＜0）時，以概率1完全接受新解為當前最優解；而當新解為惡化解（即Δ≤0）時，以概率接受惡化解為當前最優解，避免運算過程中陷入局部最優，并且隨著溫度參數Ti的減小，惡化解的接受概率也逐漸減小，最終收斂于全局最優解。

此外，實際應用中常采用指數降溫方法來實現對溫度的控制，即

式(9)中，Ti表示當前溫度，T0為初始溫度，k為溫度下降系數。

圖2給出了模擬退火算法的流程。但是模擬退火算法雖能擺脫局部最優，從而收斂到全局最優。但是這是以較高的初始溫度、較慢的降溫速率和較低的終止溫度為代價的，再加上搜索過程中對整體的把握能力不夠，所以該算法收斂到全局最優解是非常耗時的。在實際應用過程中，由于速度和時間的限制，很難保證優化結果為全局最優點。

圖2 模擬退火算法流程圖

4.3 模擬退火遺傳算法在DOA估計中的應用

遺傳算法的局部搜索能力較弱，但搜索過程中整體把握能力較強；而模擬退火算法有較強的局部搜索能力，但對整個搜索空間的狀況知之甚少，不利于搜索過程朝著最有希望的區域進行。若將兩者相結合，互相取長補短，可得到一種性能優良的新的全局搜索算法。因此利用模擬退火遺傳算法可以有效搜索出滿足式（7）的到達角，即選取作為算法的適應度。考慮到模擬退火算法一般用來求解最小值，而此處需要求解最大值，所以Metropolis準則的表達式需要做出相應的改變，即令

本文首先對遺傳算法的初始種群進行改進，并使用格雷編碼，然后將模擬退火思想融入到遺傳算法中，設計出模擬自適應交叉概率、變異概率，并且按照Metropolis準則來判斷是否接收交叉、變異等操作后產生的新解。算法主要流程如下：

（1）參數的初始化。設定遺傳種群規模N，初始化溫度T0，陣元數M，信源數P等。

（2）編碼。采用格雷編碼方法。

（3）初始種群的產生。初始種群的特性對計算結果和計算效率有著重要影響。在無法預知最優解所在區域的情況下，要實現全局最優解，初始種群在解空間中應盡量分散。文獻[11]中指出，若要取一定的點數，用佳點集法比用隨機法的偏差小得多，從而更有利于算法的快速收斂。本文采用佳點集均勻設計的方法來設計初始種群，即在解空間內（即P維歐氏空間內），利用佳點集均勻設計的方法產生N個染色體作為初始種群，具體產生方法如下[11]：

（5）選擇。采用比例選擇方法，從當代群體中選擇優良個體遺傳到下一代。

（6）自適應交叉概率和變異概率

交叉概率 Pc和變異概率Pm的選擇直接影響著算法的收斂特性，交叉運算是產生個體的主要方法，而變異運算只是產生新個體的輔助方法，二者分別決定了算法的全局和局部的搜索能力。遺傳算法計算過程中，可將進化過程分為漸進和突變兩個階段：漸進階段強交叉，弱變異，強化選擇算子；突變階段弱交叉，強變異，弱化選擇算子，這樣有利于提高計算速度和效率[9]。文中的 Pc和Pm依據模擬退火的思想按照以下公式進行自適應的調整：

式（12）、（13）中，T′為遺傳算法當前進化代數的倒數，Rini為遺傳迭代次數。在進化初期T′較高，Pc較大，Pm較小，算法側重全局搜索，快速收斂到最優解附近區域；隨著進化代數的增加，T′逐漸減小，Pc漸進減少，而Pm漸進增加，算法側重局部搜索，避免算法收斂到局部最優解，從而提高算法的計算速度和效率。

（7）交叉和變異。隨機選取兩個個體Bi和Bj進行交叉、變異，產生新個體Bi′、，計算 f(Bi)和和，然后融入模擬退火思想，并按照式（10）的Metropolis準則來判斷是否接受新個體。

（8）最優保存策略。計算經交叉、變異后個體的適應度值，與前一代中個體適應度值進行比較，將適應度值最高的個體保留到下一代群體中。

（9）終止條件的判斷。若已經達到設定的最大遺傳代數，則迭代過程終止，輸出最優解；若不滿足終止條件，溫度更新 Ti+1=kTi，并轉至第（4）步并繼續進行迭代尋優過程。

5 計算量分析

根據文獻[8]計算復雜度的方法，若定義M維矩陣相乘的計算量為Δ，則可以推出 WSF算法、基于遺傳算法求解WSF問題的計算復雜度分別為

式（14）、（15）中，range為角度搜索范圍，q為步長，Rini為遺傳迭代次數。

由式（14）可知，WSF算法的運算量隨著信源個數的增加以幾何級數增長。當信源數P較大時，有

由于遺傳算法的運算量主要由初始種群個數和迭代次數決定的，所以在相同N和Rini情況下，文中的模擬退火遺傳算法的計算復雜度與基本遺傳算法的計算復雜度差距并不算大。

6 仿真分析

仿真環境：均勻線陣陣元數為 16，陣元間距為半波長，假設有2個遠場窄帶不相干信號源，入射角度分別為-2°和2°，快拍數為 1000，噪聲為零均值、單位方差的高斯白噪聲，且信號與噪聲之間相互獨立。遺傳算法中參數設置分別為：N=40，Rini=150，Pc=0.6，Pm=0.001。模擬退火遺傳算法中參數設置分別為：T0=100000，ρ=0.9。高斯—牛頓法中參數設置分別為：最大循環次數 100，誤差容限0.001，μ=1，采用二分法確定每次迭代中的μ值，即μ=μ2。

仿真 1：隨機方法和佳點集方法產生的初始種群分布對比。為了便于比較，將初始種群規模設為300。仿真結果分別如圖3、圖4所示。

圖3 隨機產生的初始種群分布

圖4 佳點集產生的初始種群分布

對比圖3、圖4可以看出，佳點集法比隨機法產生初始種群分布要均勻、沒有重疊點、種群有較好的多樣性，有利于算法的快速收斂和全局優化。

仿真2：遺傳算法、模擬退火遺傳算法和高斯-牛頓算法性能比較。信噪比為-10dB～10dB，獨立進行100次Monte-Carlo實驗，各算法對2個信號源方位的均方誤差、分辨成功概率如圖5、圖6、圖7所示。

圖5 信號源1估計均方誤差

圖6 信號源2估計均方誤差

圖7 3種算法的分辨成功概率

由圖5、圖6可以看出，模擬退火遺傳算法的估計均方誤差最小，并隨著信噪比的增大，均方誤差趨近于 0。若定義算法的分辨門限為分辨成功概率超過90%時所對應的信噪比值，通過圖7可以看出，模擬退火遺傳算法的分辨門限為-8dB，高斯-牛頓算法的分辨門限為-3dB左右，而基本遺傳算法的成功分辨概率始終低于90%。

7 結論

子空間擬合算法雖有較好的估計性能，但由于算法涉及到非線性多維搜索，角度搜索非常耗時，限制了該類算法在實際中的應用。而本文提出的基于模擬退火遺傳算法的子空間擬合實現算法具有很強的抗早熟能力，并且在收斂速度和估計精度方面性能比較理想。除此之外，模擬退火遺傳算法還可用在MUSIC等其他DOA估計算法和目標波束空間DOA估計中，因此具有廣闊的應用前景。

[1]Schmidt R O.Multiple emitter location and signal parameter estimation [J].IEEE Trans.on AP,1986,34(3):276-280

[2]Roy R, Kailath T.ESPRIT-estimation of signal parameters via rotational invariance techniques [J].IEEE Trans.on ASSP,1989,37(7):984-995

[3]Viberg M, Ottersten B, Kailath T.Detection and estimation in sensor arrays using weighted subspace fitting [J].IEEE Trans.on SP,1991,39(11):2436-2449

[4]Krim H, Viberg M.Two decades of array signal processing research [J].IEEE Trans.on SP,1996,13(4) :67-94

[5]Agoston E E, Rober T H, Zbigniew H M.Parameter control in evolutionary algorithms [J].IEEE Trans.Evolutionary Computation,1999,3(2):124-141

[6]Karamalis P, Marousis A, Kanatas A.Direction of arrival estimation using genetic algorithms[C].Vehicular Technology Conference, Rhodes, 2001:162-166

[7]Li M, Lu Y.Genetic algorithm based maximum likelihood doa estimation [C].International Rader Conference(RADER2002), 2002:502-506

[8]金勇，程云志，周柯.基于遺傳算法的寬帶目標波束空間DOA估計[J].傳感器與微系統，2008，27(7):53-56

[9]雷英杰，張善文，李續武，等.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社，2005

[10]王凌.智能優化算法及其應用[M].北京：清華大學出版社，2001:17-35

[11]張玲，張鈸.佳點集遺傳算法[J].計算機學報，2001，24(9):917-922