邱新建，李慶華，薛鳳鳳，彭安洪

1.新疆大學(xué)信息科學(xué)與工程學(xué)院智能信號處理實驗室，烏魯木齊 830046

2.中國人民解放軍68203部隊

3.空軍工程大學(xué)電訊工程學(xué)院，西安 710077

基于量子免疫進(jìn)化的空時多維參數(shù)估計

邱新建1，2，李慶華1，薛鳳鳳3，彭安洪1

1.新疆大學(xué)信息科學(xué)與工程學(xué)院智能信號處理實驗室，烏魯木齊 830046

2.中國人民解放軍68203部隊

3.空軍工程大學(xué)電訊工程學(xué)院，西安 710077

1 引言

人工免疫算法的概念是1996年在日本舉行的免疫系統(tǒng)國際會議上首次提出的，國內(nèi)，西安電子科技大學(xué)的焦李成教授已經(jīng)將其發(fā)展成為了一個完備的理論體系，并且不斷提出新的免疫算法。人工免疫進(jìn)化算法的應(yīng)用研究是其中一個重要的研究方向，目前它在目標(biāo)優(yōu)化、機器人控制、神經(jīng)網(wǎng)絡(luò)設(shè)計等領(lǐng)域已有著廣泛的應(yīng)用，而在多維參數(shù)估計領(lǐng)域研究還較少。文獻(xiàn)[1]將免疫算法用于解決頻率估計和方位角的估計的問題，文獻(xiàn)[2]用免疫進(jìn)化算法解決高斯—牛頓算法的二維搜索問題。多維參數(shù)估計是空間譜估計理論應(yīng)用中的一個重要課題，精典的參數(shù)估計大多是針對方位的一維信號參數(shù)（方位角）的估計，當(dāng)然也很容易推廣到二維（方位角和俯仰角）甚至多維（頻率、方向角及俯仰角），但此時計算量、數(shù)值穩(wěn)定性等問題就顯現(xiàn)了出來，如多維MUSIC算法，以及基于高階累積量的MUSIC算法都存在這一問題。ESPRIT算法雖然使DOA估計算法的計算量降了下來，但是它在低信噪比的情況下性能欠佳，往往達(dá)不到實際應(yīng)用的要求。本文通過理論分析將高效的量子免疫進(jìn)化算法與多維參數(shù)估計問題結(jié)合起來，使得算法的性能得到了很大的提高。

2 量子免疫進(jìn)化算法

量子免疫進(jìn)化算法[3-6]主要是一種借鑒自然界生物免疫系統(tǒng)的克隆選擇和親和力成熟原理的人工算法，克隆選擇對應(yīng)著一個親和力成熟的過程，即對抗原親和力較低的個體在克隆選擇機制作用下，經(jīng)歷增殖復(fù)制和變異操作，使其親和力逐步提高而“成熟”。新個體的產(chǎn)生主要由克隆選擇、增殖和高頻變異來完成。

2.1 個體的編碼

本文采用量子染色體編碼，假如共用了n個量子染色體，每個染色體采用m位量子編碼，則用前m/2位表示方位角而后m/2位表示俯仰角，每一位量子編碼包含一對量子比特幅度，表示為量子染色體可以轉(zhuǎn)化成二進(jìn)制染色體，產(chǎn)生一個在0和1之間的均勻分布的隨機數(shù)λ，若λ＜|2，則二進(jìn)制染色體取0，否則取1。

2.2 克隆選擇、增殖、高頻變異

克隆選擇就是對各個染色體進(jìn)行克隆增殖，增殖的數(shù)量與該染色體與抗原的親和力值有關(guān)，親和力值越高的染色體擁有越多的增殖副本，并根據(jù)它們的親和力值進(jìn)行變異，為了保存親和力值較高的副本，親和力值越高，變異概率越小。

2.3 算法終止條件

算法終止一般分為達(dá)到設(shè)定最大進(jìn)化次數(shù)時停止和改進(jìn)量小于閾值時停止兩種。達(dá)到最大進(jìn)化次數(shù)停止就是當(dāng)算法達(dá)到了提前設(shè)定的進(jìn)化次數(shù)時就停止，改進(jìn)量小于閾值時停止就是當(dāng)前一代染色體與下一代染色體與親和力值的差值小于一個設(shè)定的ε時，算法停止。

3 陣列信號分析

設(shè)信號接收陣列為平面陣，陣列模型如圖1所示。

圖1 陣列模型圖

圖1中子陣X位于x軸上，子陣Y位于y軸上，兩個子陣的結(jié)構(gòu)是完全相同的，均為等距離均勻線陣，且陣元數(shù)均為M。以原點處的陣元為參考點，空間信號照射到平面陣上的俯仰角用φ表示，方位角用θ表示。根據(jù)時域延遲與空域延遲的相通性與特殊性，兩者在一定的條件下可以相互的轉(zhuǎn)換，則第i個信號到第m個陣元與第i個信號到參考陣元相比，時延為：

現(xiàn)設(shè)線陣為X，陣源數(shù)為M，沿x軸以間距d從原點依次排開，將X陣輸出的數(shù)據(jù)記為X1(t)?，F(xiàn)將X1(t)再進(jìn)行τ個單位的延遲，延遲后的數(shù)據(jù)記為Z1(t)，則有：

由(Cx11，Cz1x1)組成一個矩陣束，根據(jù)矩陣束的秩與廣義特征值分解的關(guān)系可得e-j2πfiτ(i=1，2，…，N)是此矩陣束的廣義特征值[7]，設(shè)其值為tfi，則有：

根據(jù)信號子空間擬合理論，可得空時二維譜估計的譜可由下式求得：

4 算法基本步驟

步驟1初始化種群，設(shè)置染色體的個數(shù)、維數(shù)、克隆數(shù)目、變異幅度、進(jìn)化代數(shù)等參數(shù)，按量子染色體編碼規(guī)則編碼，并將量子染色體轉(zhuǎn)化為二進(jìn)制染色體。

步驟2親和力值的計算，將陣列接收的信號組成流型矩陣A1，將步驟1得到的二進(jìn)制染色體轉(zhuǎn)化成十進(jìn)制，估計協(xié)方差矩陣?，然后按式（10）計算所有抗體對抗原的親和力函數(shù)值P。

步驟3克隆繁殖，對初始抗體種群中的每一個抗體都復(fù)制個，K為設(shè)定的克隆數(shù)目，并排列成一個抗體集合。

步驟4高頻變異，對克隆產(chǎn)生的子抗體按照式（11）進(jìn)行變異，同時父抗體也參與變異操作，并且對變異結(jié)果進(jìn)行挑選，對不在原定義域內(nèi)的新抗體進(jìn)行排除。

其中，p=(1/β)e-F，r為上一代抗體，p反比于親和力值，β用來控制變異幅度。

步驟5抗體選擇，對所有符合條件的新抗體計算其親和力函數(shù)值，比較父抗體和各個變異子抗體的親和力值，并用最大值代替父抗體，形成新的父抗體。

步驟6抑制操作，分別計算每一個抗體種群中抗體之間的相似度，刪除相似度小于閾值的一個，保留另外一個。

步驟7如果滿足終止條件，則輸出所有抗體和其親和力值，輸出抗體所在位置即為三個待估計信號的位置；否則轉(zhuǎn)入步驟8。

步驟8隨機生成新抗體，轉(zhuǎn)入步驟2繼續(xù)迭代。

5 仿真實驗

實驗以MATLAB 2010b為平臺，在CPU Penium-4 2.93 GHz，RAM 512 MB配置的PC機上進(jìn)行。實驗采用16元均勻面陣，陣元間距為半個波長，有3個獨立的信號源，平均信噪比設(shè)置為-15 dB，快拍數(shù)為100，實驗次數(shù)為10次，方位角、俯仰角、和信號頻率分別為（30°，35°，2 GHz），（50°，45°，6 GHz），（60°，55°，10 GHz）。染色體數(shù)目設(shè)置為65，維數(shù)為22，克隆數(shù)目K=65，初始變異幅度將步驟7中的終止條件設(shè)置為前后兩次親和度函數(shù)值的變化量小于某個給定的數(shù)，即|F1-F2|＜ε（本文ε取為0.01），同時將進(jìn)化次數(shù)設(shè)置為30代，算法達(dá)到最大進(jìn)化次數(shù)或者滿足終止條件都將停止運行。為了說明本文算法的有效性，將本文算法與二維MUSIC算法[8]進(jìn)行全面的比較。

圖2為本文算法與二維MUSIC算法的均方根誤差（RMSE）隨信噪比的變化曲線，圖3為估計方差隨信噪比的變化曲線。

圖2 參數(shù)估計的RMSE隨信噪比的變化曲線圖

從圖2可以看出，本文算法對方位角和俯仰角估計的均方根誤差在大于5 dB后都比二維MUSIC算法小，并且本文算法隨著信號比的升高性能迅速的改善，而二維MUSIC改變不大，高信噪比時均方根誤差是本文算法的2～3倍，同時頻率估計的誤差比大部分角度估計都小。從圖3可以得到本文算法估計值的方差都較小，說明本文算法估計值的散布范圍小，這正是由于二維MUSIC算法對快拍數(shù)、信噪比敏感造成的，快拍數(shù)下降或者低信噪比時，二維MUSIC算法中使用的協(xié)方差矩陣的特征分解將受到很大的擾動，而特征分解運算對擾動又十分敏感，這就造成估計的均方根誤差大，估計值散布大。對比說明本文算法有很強的抗噪性能和穩(wěn)健性。

圖3 參數(shù)估計的方差隨信噪比的變化曲線圖

圖4所示為文獻(xiàn)[2]中的算法與本文算法的收斂性能比較。本文算法收斂比文獻(xiàn)[2]算法稍慢，但本文算法搜索到了更高的親和力值，且親和力值的范圍大，這說明文獻(xiàn)[2]算法存在“早熟”現(xiàn)象，收斂到了局部最優(yōu)，并未搜索到全局最優(yōu)；本文算法搜索范圍大，并且逐步收斂到全局最優(yōu)，這說明本文以式（10）作為親和力評價函數(shù)的可行性，它局部極值點少，包絡(luò)平坦，能使優(yōu)化算法發(fā)揮更好的性能。

圖4 收斂性能比較圖

對文獻(xiàn)[2]算法、二維MUSIC算法以及本文算法，在信噪比為20 dB的情況下（其余條件不變）進(jìn)行10次Monte-Carlo仿真實驗。表1所示為文獻(xiàn)[2]算法與本文算法運行時間的比較結(jié)果，可以看出二維MUSIC算法的運行時間最長，文獻(xiàn)[2]算法次之。這主要是因為二維MUSIC算法采用全方位逐次搜索，計算量自然大，文獻(xiàn)[2]算法和本文算法均是向最優(yōu)方向有目的的搜索，所以計算量要小，同時本文算法還優(yōu)于文獻(xiàn)[2]算法，這充分體現(xiàn)了本文算法的高效性。

表1 運行時間比較s

6 結(jié)論

將量子免疫進(jìn)化算法與多維參數(shù)估計結(jié)合起來，有效地拓展了量子進(jìn)化算法的應(yīng)用范圍，通過理論推導(dǎo)和仿真分析，證明了算法的優(yōu)越性，避免了特征分解和窮盡搜索等算法存在的穩(wěn)健性差，運算時間長（窮盡搜索的單次運行時間高達(dá)8 200.4 s[1]）等缺點。但本文算法親和力函數(shù)的選擇從本質(zhì)上講還是屬于子空間擬合類算法，怎么樣才能尋找到更合理的親和力函數(shù)是一個問題。同時，從圖2可以看出二維MUSIC算法方位角和俯仰角估計的誤差基本相當(dāng)，本文算法對兩個角度估計的誤差雖然都很低，但在低信噪比時卻相差很大，這說明二維MUSIC算法對兩個角度的估計是互不影響的，而本文算法由于將兩個角度的編碼放在同一個染色體上所以每一對方位角和俯仰角之間是有影響的。今后，對以上這兩個問題將進(jìn)一步研究。

[1]牛奕龍，陳志菲，孫進(jìn)才，等.估計聲信號二維參數(shù)的免疫量子克隆算法[J].數(shù)據(jù)采集與處理，2010，25（1）：33-38.

[2]欒鵬程，吳瑛.改進(jìn)遺傳算法在DOA搜索中的應(yīng)用[J].電光與控制，2006，13（3）：65-68.

[3]吳秋逸，焦李成，魏峻，等.量子協(xié)同免疫動態(tài)優(yōu)化算法[J].模式識別與人工智能，2009，22（6）：863-868.

[4]Han K H，Kim J H.Quantum-inspired evolutionary algorithms with a new termination，H gate，and two-phase scheme[J]. IEEE Transactions on Evolutionary Computation，2004，8（6）：156-168.

[5]Jiao Licheng，Li Yangyang，Gong Maogou，et al.Quantuminspried immune clonal algorithm for global optimization[J]. IEEE Trans on System，Man and Cybernetics，2008，38（5）：1234-1253.

[6]楊淑媛，焦李成，劉芳.量子進(jìn)化算法[J].工程數(shù)學(xué)學(xué)報，2006，23（2）：241-246.

[7]張賢達(dá).現(xiàn)代信號處理[M].北京：清華大學(xué)出版社，2002：522-524.

[8]High resolution 2-D DOA estimation using second-order partialdifferential of MUSIC spectrum[C]//Proceedings of the IEEE InternationalSymposiumonCircuitsandSystems，2008：1152-1155.

QIU Xinjian1，2,LI Qinghua1,XUE Fengfeng3,PENG Anhong1

1.Intelligent Signal Processing Lab,College of Information Science and Engineering,Xinjiang University,Urumqi 830046,China
2.Unit 68203 of PLA,China
3.Telecommunications Engineering Institute,Air Force Engineering University,Xi’an 710077,China

Using the relationship of the time-equivalent between the array signal processing and the airspace,to based on the plane array,using singular value decomposition and the generalized eigenvalue decomposition of array covariance matrix,the frequency of the

signal can be estimated.A function of antigen and antibody affinity is proposed by analyzing the array model.It can estimate the pitch angle and azimuth signal using the characteristics of the evolution of immune.Thus the multidimensional array signal parameter estimation can be completed.The numerical stability,noise immunity and time consuming of multi-dimensional parameters estimation can be improved.The computer simulation shows that the proposed algorithm is effective. Key words：quantum computation;immune evolutionary algorithm;multi-dimensional parameter estimation;spectrum estimation;space-time signal processing

利用陣列信號處理時域與空域等效的關(guān)系，以平面陣為基礎(chǔ)，采用陣列協(xié)方差矩陣的奇異值分解和廣義特征值分解估計接收信號的頻率，通過分析陣列模型，提出一種抗原和抗體的親和力函數(shù)；利用量子免疫進(jìn)化的特性，估計出信號的俯仰角和方位角，從而完成陣列信號的多維參數(shù)估計，改善了多維參數(shù)估計的抗噪性能、數(shù)值穩(wěn)定性和運行時間。通過計算機仿真，證明了該算法的有效性。

量子計算；免疫進(jìn)化算法；多維參數(shù)估計；譜估計；空時信號處理

A

TP18

10.3778/j.issn.1002-8331.1201-0182

QIU Xinjian,LI Qinghua,XUE Fengfeng,et al.Space-time multi-dimensional estimation using quantum immune evolutionary algorithm.Computer Engineering and Applications,2013,49（19）：210-212.

國家自然科學(xué)基金（No.60971130）。

邱新建（1984—），男，博士研究生，主要研究方向智能信號處理，模式識別；李慶華（1987—），女，碩士生；薛鳳鳳（1986—），女，博士生，講師；彭安洪（1985—），男，博士生。E-mail：tonggong0412@163.com

2012-01-20

2012-07-19

1002-8331（2013）19-0210-03