模擬退火遺傳算法在DOA估計(jì)技術(shù)中的應(yīng)用

賈偉娜，劉順蘭

Jia Wei-na，Liu Shun-lan

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

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

1 引言

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

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

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

2 陣列模型

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

式（1）中，X(t)為陣列的M×1維快拍數(shù)據(jù)矢量，N(t)為陣列的M×1維噪聲數(shù)據(jù)矢量，S(t)為P×1維的信號(hào)數(shù)據(jù)矢量，為M×P維陣列方向矩陣，其中第i個(gè)信號(hào)的導(dǎo)向矢量為[]T表示矩陣轉(zhuǎn)置。

若假設(shè)P＜M，噪聲為理想高斯白噪聲，功率為2σ，且各陣元間噪聲、噪聲與信號(hào)之間相互獨(dú)立，則陣列輸出的協(xié)方差矩陣為

式（2）中，Rs為信號(hào)協(xié)方差矩陣，I為單位矩陣。

對(duì)R進(jìn)行特征分解，考慮到信號(hào)源相干或非相干的情況，Rs的秩P′會(huì)小于等于信源個(gè)數(shù)P，則有

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

3 加權(quán)子空間擬合（WSF）算法

加權(quán)子空間擬合相當(dāng)于子空間之間的擬合，既接收數(shù)據(jù)的子空間與實(shí)際信號(hào)導(dǎo)向矢量組成的子空間之間的擬合。文獻(xiàn)[3]中給出了 WSF準(zhǔn)則一般表達(dá)式

文獻(xiàn)[3]中指出，當(dāng)加權(quán)矩陣W滿足下式時(shí)，Θ估計(jì)的方差最小。即

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

4 模擬退火遺傳算法

4.1 遺傳算法

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

圖1 遺傳算法的運(yùn)算過程示意

然而實(shí)踐應(yīng)用中，遺傳算法在運(yùn)算過程中很快收斂到局部最優(yōu)解，并且運(yùn)算后期在最優(yōu)解附近左右擺動(dòng)，收斂較慢[9]。

4.2 模擬退火算法

模擬退火算法（SA）是一種基于金屬退火機(jī)理的隨機(jī)尋優(yōu)算法，通過隨機(jī)搜索技術(shù)從概率意義上找出目標(biāo)函數(shù)的全局最小點(diǎn)。在尋優(yōu)過程中，當(dāng)前解xold經(jīng)隨機(jī)擾動(dòng)產(chǎn)生新解xnew，新解的接受概率由Meteopolis準(zhǔn)則確定，即

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

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

此外，實(shí)際應(yīng)用中常采用指數(shù)降溫方法來實(shí)現(xiàn)對(duì)溫度的控制，即

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

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

圖2 模擬退火算法流程圖

4.3 模擬退火遺傳算法在DOA估計(jì)中的應(yīng)用

遺傳算法的局部搜索能力較弱，但搜索過程中整體把握能力較強(qiáng)；而模擬退火算法有較強(qiáng)的局部搜索能力，但對(duì)整個(gè)搜索空間的狀況知之甚少，不利于搜索過程朝著最有希望的區(qū)域進(jìn)行。若將兩者相結(jié)合，互相取長補(bǔ)短，可得到一種性能優(yōu)良的新的全局搜索算法。因此利用模擬退火遺傳算法可以有效搜索出滿足式（7）的到達(dá)角，即選取作為算法的適應(yīng)度?？紤]到模擬退火算法一般用來求解最小值，而此處需要求解最大值，所以Metropolis準(zhǔn)則的表達(dá)式需要做出相應(yīng)的改變，即令

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

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

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

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

（5）選擇。采用比例選擇方法，從當(dāng)代群體中選擇優(yōu)良個(gè)體遺傳到下一代。

（6）自適應(yīng)交叉概率和變異概率

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

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

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

（8）最優(yōu)保存策略。計(jì)算經(jīng)交叉、變異后個(gè)體的適應(yīng)度值，與前一代中個(gè)體適應(yīng)度值進(jìn)行比較，將適應(yīng)度值最高的個(gè)體保留到下一代群體中。

（9）終止條件的判斷。若已經(jīng)達(dá)到設(shè)定的最大遺傳代數(shù)，則迭代過程終止，輸出最優(yōu)解；若不滿足終止條件，溫度更新 Ti+1=kTi，并轉(zhuǎn)至第（4）步并繼續(xù)進(jìn)行迭代尋優(yōu)過程。

5 計(jì)算量分析

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

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

由式（14）可知，WSF算法的運(yùn)算量隨著信源個(gè)數(shù)的增加以幾何級(jí)數(shù)增長。當(dāng)信源數(shù)P較大時(shí)，有

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

6 仿真分析

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

仿真 1：隨機(jī)方法和佳點(diǎn)集方法產(chǎn)生的初始種群分布對(duì)比。為了便于比較，將初始種群規(guī)模設(shè)為300。仿真結(jié)果分別如圖3、圖4所示。

圖3 隨機(jī)產(chǎn)生的初始種群分布

圖4 佳點(diǎn)集產(chǎn)生的初始種群分布

對(duì)比圖3、圖4可以看出，佳點(diǎn)集法比隨機(jī)法產(chǎn)生初始種群分布要均勻、沒有重疊點(diǎn)、種群有較好的多樣性，有利于算法的快速收斂和全局優(yōu)化。

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

圖5 信號(hào)源1估計(jì)均方誤差

圖6 信號(hào)源2估計(jì)均方誤差

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

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

7 結(jié)論

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

[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]金勇，程云志，周柯.基于遺傳算法的寬帶目標(biāo)波束空間DOA估計(jì)[J].傳感器與微系統(tǒng)，2008，27(7):53-56

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

[10]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社，2001:17-35

[11]張玲，張鈸.佳點(diǎn)集遺傳算法[J].計(jì)算機(jī)學(xué)報(bào)，2001，24(9):917-922