基于量子免疫進化的空時多維參數估計

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

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

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

3.空軍工程大學電訊工程學院，西安 710077

基于量子免疫進化的空時多維參數估計

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

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

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

3.空軍工程大學電訊工程學院，西安 710077

1 引言

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

2 量子免疫進化算法

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

2.1 個體的編碼

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

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

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

2.3 算法終止條件

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

3 陣列信號分析

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

圖1 陣列模型圖

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

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

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

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

4 算法基本步驟

步驟1初始化種群，設置染色體的個數、維數、克隆數目、變異幅度、進化代數等參數，按量子染色體編碼規則編碼，并將量子染色體轉化為二進制染色體。

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

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

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

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

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

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

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

步驟8隨機生成新抗體，轉入步驟2繼續迭代。

5 仿真實驗

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

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

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

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

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

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

圖4 收斂性能比較圖

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

表1 運行時間比較s

6 結論

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

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

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

[3]吳秋逸，焦李成，魏峻，等.量子協同免疫動態優化算法[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].工程數學學報，2006，23（2）：241-246.

[7]張賢達.現代信號處理[M].北京：清華大學出版社，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

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

量子計算；免疫進化算法；多維參數估計；譜估計；空時信號處理

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.

國家自然科學基金（No.60971130）。

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

2012-01-20

2012-07-19

1002-8331（2013）19-0210-03