祁 浩，劉洲洲

（1.西北工業(yè)大學電子信息學院，西安710072；2.西安航空學院，西安710077）

基于量子免疫克隆的壓縮感知數據重構算法?

祁 浩1，劉洲洲2

（1.西北工業(yè)大學電子信息學院，西安710072；2.西安航空學院，西安710077）

提出了一種基于量子免疫克隆的壓縮感知數據重構算法（Q-CSDR）。算法先提出了一種能夠提高數據重構概率的自適應分幀方法，然后利用量子克隆免疫算法的優(yōu)化組合性能實現數據的精確重構。實驗結果表明，Q-CSDR算法能夠根據原始信號稀疏度自動調節(jié)壓縮比率，具有重構速度快，重構精度高，能夠適應于高稀疏度數據重構等優(yōu)點。該算法已應用于秦始皇帝陵博物院野外文物安防系統。經實際檢驗，收到了良好效果。

量子免疫克??；壓縮感知；數據重構；稀疏度

1 引 言

壓縮感知（Compressed Sensor，CS）［1］是近幾年來數據和信號處理的研究熱點之一，它使用線性變換將具有一定稀疏度的信號投影到一個低維空間上，并通過使用非線性方式對數據進行重構。壓縮感知的優(yōu)點在于其突破了奈奎斯特采樣定理和香農理論的限制，能夠以遠小于經典采樣方法獲取的數據量重構出高質量的原始信號，與傳統壓縮方法相比，壓縮感知具有采樣數量少、采樣數據小等優(yōu)點。

數據重構算法是壓縮感知過程中的一個重要環(huán)節(jié)，其關鍵問題在于如何快速、準確的從已知低維數據中恢復出高維數據。目前壓縮感知數據重構算法主要分為兩類［2］：第一類算法是基于最小化l1范數的算法，包括基追蹤算法（Basis Pursuit，BP）［3］，線性規(guī)劃算法（Linear Programming，LP）［4］等，這類算法具有重建精度高的優(yōu)點，但其算法的復雜度較高，且執(zhí)行效率低，實用性較差；第二類是基于最小化l0范數的方法，即貪婪算法，包括正交匹配追蹤算法（Orthogonal Matching Pursuit，OMP）［5］、子空間追蹤算法（Subspace Pursuit，SP）［6］、壓縮采樣匹配追蹤算法（Compressive Sampling Matching Pursuit，Co-SaMp）［7］、迭代硬閾值算法（Iterative Hard Thresholding，IHT）［8］、基于感知字典的迭代硬閾值算法（Sending Dictionary-based Iterative Hard Thresholding，SDIHT）［9］、基于混沌量子免疫克隆算法的正交匹配算法（Orthogonal Matching Pursuit based on Quantum-inspired immune clonal，OMP-QICA）［10］、基于遺傳算法的壓縮感知重構算法［11］等，這類算法主要通過迭代更新當前估計來優(yōu)化信號恢復情況，在原始信號稀疏度較小的情況下具有很好的重構精度及重構速度，但對于稀疏度較高的原始信號其算法的性能卻有明顯下降。針對此問題，本文提出了基于量子克隆免疫算法的壓縮感知數據重構算法（Quantum-inspired immune clonal based Compressed sensor data reconstruction，Q-CSDR）。Q-CSDR算法利用量子克隆免疫算法的快速搜索性能以及快速收斂能力實現了對原始數據的精確重構，使用自適應長度分幀方法減少l1范數最小化問題的冗余解，提高了高稀疏度條件下數據的重構精度。實驗結果表明，該算法具有重構精度高、重構性能穩(wěn)定等優(yōu)點。

2 壓縮感知與數據重構

設X∈RN為長度為N的一維信號，壓縮感知過程可以用公式（1）來表示，Φ為M*N維的觀測矩陣（M＜＜N）：Y＝ΦX。通過觀測矩陣對x進行觀測，可以將原始信號壓縮為長度為M的一維信號，實現數據壓縮。如何利用已有的感知數據Y重構出原始信息，并要求重構信號盡可能逼近原始信號，是壓縮感知理論框架中最關鍵的操作之一。壓縮感知信號重構問題實際上是個求解欠定方程組的過程，數學表達過程如公式（1）所示：

其中對于向量x，其lp范數定義為：

在實際重構過程中一般允許存在一定的誤差，所以上式可表示成公式（3），其中ε為極小常量：

壓縮感知重構最關鍵的問題在于，公式（1）和公式（3）均是數值不穩(wěn)定的NP-完全問題，在求解過程中需要窮舉原始信號x中非零元素位置的種可能組合。

3 基于量子免疫克隆的壓縮感知數據重構算法

量子免疫克隆算法（Quantum-inspired immune clonal algorithm，QICA）［12-13］是目前的研究熱點之一，是解決NP-完全問題的高效算法，具有很好的優(yōu)化組合性能。QICA將量子搜索機制和免疫算法克隆選擇原理相結合，利用量子編碼的疊加性構造抗體，利用克隆操作產生原始種群和克隆子群實現種群擴張，使搜索空間擴大，提高了局部搜索能力；同時借助全干擾交叉操作避免陷入局部最優(yōu)。

QICA采用了多狀態(tài)量子比特編碼方式和通用的量子旋轉門操作，引入動態(tài)調整旋轉角機制和量子交叉［14］。QICA算法的核心思想是，先使用量子位和量子疊加態(tài)生成具有極大隨機性的變量值，并利用遍歷對解空間的所有變量值進行優(yōu)化搜索，再通過交叉和量子門旋轉避免局部最優(yōu)，最后，通過線性變換將獲得的最優(yōu)解還原到原優(yōu)化空間中。

雖然量子克隆免疫算法具有很好的優(yōu)越性，但原始信號的非零元素位置組合數量巨大，降低了算法的運算速度，因此將量子克隆免疫算法應用于壓縮感知需要解決的最關鍵問題是減少解空間中的冗余解，提高信號重構概率，在對信號壓縮前需要對其進一步進行分幀處理。

3.1 分幀方法

假設信號采集端采集的原始信號長度為N，稀疏度為K，根據非零元素的個數將原始信號分為frame＝ceil（K／n）個幀，n為每個幀內包含的非零元素個數，ceil（·）為向上取整函數。自適應分幀方法為：從原始信號的第一位起，記錄非零元素的個數m，當m為第τ*n＋1個非零元素時，將其劃分為下一幀的起始元素。其中τ為正整數，其取值范圍為［0，frame-1］。舉例說明：

假設原始信號的稀疏向量x為：

0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0

則當n＝2時，可分成如下六個幀：

0 0 0 1 1｜1 0 1 0｜1 0 1 0 0｜1 0 0 0 1 0｜1 1 0｜1 0 0 1 0 0 0。

其原始信號長度為30，稀疏度K＝40。

這種分幀方法的特點是除第一幀外，其余所有幀的起始位均為非零元素。與傳統的固定長度分幀方法相比，這種自適應長度的分幀方法減少了重構過程中非零元素個數的排列組合可能性，提高了原始信號的重構概率。

3.2 理論分析

假設信號采集端采集的原始信號長度為N，信號稀疏度為K，則原始信號中的非零元素的可能位置有種可能，設其幅值均勻分布在［rangemin， rangemax］上，則根據概率論相關知識可知：其重建概率：

以原始信號為例，表1顯示未分幀及分幀后的原始信號x中非零元素的位置組合數量。

表1 分幀前后非零元素位置組合數量

可以看出，隨著分幀內非零元素n變大，原始信號中非零元素位置的組合數量也隨之迅速增大。n＝1時非零元素位置組合僅有4種，其精確重構的概率最大，但應用于實際過程中會因為分幀長度過短導致幀數量增加，分幀數量增加會導致通信包數量急劇增加，造成網絡擁塞，使分幀方法的實用性降低。當n取值過大時，雖然能夠減少通信包數量，降低通信開銷，但也會造成非零元素位置組合數量急劇增加，降低了數據的重構概率，因此表1僅列出了n＝1～4的非零元素位置組合數量。

3.3 信號重構過程

根據量子免疫克隆理論，我們將壓縮感知信號重構過程分為以下四個過程。

3.3.1 權值抗體初始化

量子免疫克隆算法是基于量子計算和遺傳算法組成的，其抗體的編碼方式采用量子比特編碼。一個抗體中量子位的狀態(tài)是不確定的，可以為0或1，其狀態(tài)表示為公式（5）：

其中α，β表示相應狀態(tài)出現概率的兩個復數，其關系為α2＋β2＝1。

具有m個量子比特位的抗體可以描述為公式（6）：

其中t表示種群代數。結合信號重構的應用實際，m表示分幀長度。規(guī)模為n的量子種群表示為：，Q（t）即為信號重構的解空間。

3.3.2 抗體編碼

這里摒棄經典量子理論的坍塌觀測解碼方法，對公式（6）中的量子位采用文獻［8］進行實數編碼，其規(guī)則如下：

frame為原始信號的分幀數量，xi表示當前幀中第i個位置元素的幅值大小。

在進行實數編碼后，算法按照當前分幀的非零元素數量按下列方法，將其權值置為0；

1.若是第一分幀，則按照非零元素個數隨機生成位置估計；

2.若不是第一分幀，則估計幀中第一位設為非零元素，其余非零元素位置隨機生成。

3.3.3 抗體種群克隆

公式中，mi為種群中第i個抗體的克隆規(guī)模，nc是與克隆規(guī)模相關且大于種群規(guī)模N的常數，本算法中設置為種群規(guī)模的1.2倍，f（qi）為第i個抗體的適應度。

3.3.4 抗體種群更新

量子克隆免疫算法中，量子抗體通過量子旋轉門和全局交叉來實現更新操作。采用的量子旋轉門如公式（9）：

在利用量子旋轉門進行更新的基礎上，為了構造更加健壯的交叉操作，避免算法陷入局部最優(yōu)，算法采用了全干擾交叉操作。假設一個種群包含5個長度為8的抗體，其具體交叉方法見表2。

表2 全干擾交叉操作

3.4 算法步驟及流程

算法流程圖如圖1所示。

圖1 算法流程圖

算法具體過程如下：

1.將原始信號進行分幀處理，記錄分幀長度、幀序列號、稀疏度等信息。

2.種群初始化。設置算法相關參數，包括種群規(guī)模sizepop，算法最大迭代次數maxgen或適應度值下限ε，各幀稀疏度sparseratio，并根據壓縮前后幀長通過查表確定觀測矩陣Φ。

3.根據預置參數初始化種群，種群中每個抗體的稀疏度均為sparseratio。

4.將公式（4）計算得到的輸出y與目標輸出target帶入公式（10）計算適應度，這里設目標輸出為n維向量：

5.對原有種群進行克隆及更新操作，計算新種群的適應度值，保留新種群中前sizepop個最優(yōu)個體組成下一代種群。

6.若沒有達到算法停止條件，則記錄當前最優(yōu)個體及最優(yōu)結果，然后轉向步驟3，若達到停止條件，則輸出最優(yōu)個體及最優(yōu)適應度值。

7.若還有分幀需要構建，則轉向步驟1，反之轉向步驟8。

8.將恢復的各幀按幀序列號組合即完成信號重建過程。

4 實驗及分析

試驗場地選擇在秦始皇帝陵博院K9801號坑旁，使用無線傳感器作為信號采集設備對監(jiān)測區(qū)域內的微地震信號進行采集。采集到的信號在傳感器節(jié)點本地進行濾波、降噪等處理后，再通過分幀和壓縮后傳輸至遠端服務器。為使對比結果明顯可靠，在現場布置兩類傳感器：一類是傳輸壓縮信號的傳感器，一類是傳輸未壓縮信號的傳感器。

4.1 自適應長度分幀結果分析

從分析結果可以看出，信號的恢復精度實際上受幀內非零元素個數影響較大，算法的復雜度則受幀長度影響。根據以上結果，對原始信號采取自適應的分幀方法進行處理。實驗結果如圖2所示。

圖2 n＝2時的數據恢復結果

當n＝2時，原始數據共分為22個幀，信號壓縮比為200：59，近乎達到3：1。考慮通信中，每幀數據包需要額外增加兩個字節(jié)原始幀長度和稀疏度信息，因此實際數據壓縮比率為162：400＝0.405。重建信號的精度為100%。

如圖3所示，當n＝3時，原始數據共分為15個幀，信號壓縮比為200：59，約為3：1。考慮通信中，每幀數據包需要額外增加兩個字節(jié)原始幀長度和稀疏度信息，因此實際數據包長度壓縮比率為148：400＝0.37。重建信號的精度為98%。

圖3 n＝3時的數據重構結果

如圖4所示，當n＝4時，原始數據共分為12個幀，信號壓縮比為200：66，約為3.3：1?？紤]通信中，每幀數據包需要額外增加兩個字節(jié)原始幀長度和稀疏度信息，因此實際數據包長度壓縮比率為156：400＝0.39。重建信號的精度為87%。

圖4 n＝4時的數據重構結果

由上述實驗結果可以看出，自適應條件下的數據重構精度較好，而且n越大恢復精度越低。從傳輸角度來看，n越大分幀數越少，產生的通信開銷越少，n越小則重構概率越高、恢復精度越高。

4.2 不同稀疏度條件下實驗結果分析

針對實驗過程中采集的25組長度為200的數據進行壓縮和重建，實驗結果如圖5所示。

圖5 不同稀疏度條件下的試驗結果

可以看出，Q-CSDR算法在各種稀疏度條件下均保持了較好的數據恢復精度，性能比較穩(wěn)定。算法在較高稀疏度條件下也具有較好的恢復精度，但代價是增加了通信開銷和數據壓縮比：n＝2時的數據恢復精度最好，其壓縮比和n＝3和n＝4時相差不多，其通信開銷則高于后兩種分幀方式。因此適用于對信號恢復精度要求很高、但對網絡壽命要求較低的系統環(huán)境。n＝3時數據壓縮比率最低，其通信開銷小于n＝2，其數據精度則介于n＝3和n＝4之間，適用于對數據精度和網絡壽命都有一定要求的系統環(huán)境。n＝4時，數據恢復精度較差，但其通信開銷最小，適用于對數據精度要求不高，但對網絡壽命要求較高的系統環(huán)境。此外，算法對稀疏度接近45的原始信號仍保持較高的重構概率，這也是由于減少了解空間數量，減少了估計信號的非零元素排列可能帶來的影響。

4.3 同類算法對比分析

圖6中顯示的是在各稀疏度條件下，不同算法的性能對照（不考慮通信開銷）。

圖6 同類算法實驗結果對比

可以看出在稀疏度較小的條件下，各類算法都具有較好的數據恢復精度。而在稀疏度大于30后，OMP算法的數據恢復性能急劇下降，SDIHT及BIHT算法在稀疏度大于40后也出現了明顯的下降趨勢，而Q-CSDR算法在稀疏度大于45后出現明顯下降，特別是n＝2時的Q-CSDR算法在稀疏度50時仍能保持90%的恢復概率，這也說明了分幀長度對于數據恢復精度的影響還是很明顯的。

綜上所述，Q-CSDR算法在稀疏度較大的前提下數據重構性能較其他幾種算法好，但其缺點在于壓縮時分幀長度無法預知，需要針對各個長度預設不同長度的觀測矩陣，因此其觀測矩陣字典需要的存儲空間較多。從實驗結果分析來看，n＝2時的通信開銷較大，單從網絡系統節(jié)能角度考慮并不是最優(yōu)選擇。因此在實際應用中采用了n＝3的QCSDR算法。

5 結束語

提出了基于量子免疫克隆的數據恢復算法。將量子免疫克隆與壓縮感知數據恢復算法結合起來，在提高運算效率的前提下保證了數據恢復精度，并提出了自適應分幀方法。結果表明，算法能夠在稀疏度較高的條件下精確的恢復出原始數據，并減小傳輸的數據量。本算法已經應用于秦始皇帝陵博物院野外文物安防系統中，經實際檢驗收到了良好效果，今后的工作將是如何降低數據恢復算法復雜度，減少觀測矩陣的儲存空間。

［1］Cands E，Romberg J，Tao T.Satable singal recovery form incomplete and inaccurate measurements［J］.Communications on Pure and Applied Mathematics，2006，59（8）：1207-1223.

［2］楊海蓉，張成，等.壓縮傳感理論與重構算法［J］.電子學報，2011，39（1）：142-148.

［3］Chen B S，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33-61.

［4］Cands E J，Tao T.Decoding by linear programming［J］.IEEE Transactions on Information Theory，2005，51（12）：4203-4215.

［5］Tropp J A，Gilbert A C.Singal recovery from random measurements via orthogonal matching pursuit［J］.IEEE transactions on Information Theory，2007，52（12）：4655-4666.

［6］DaiW，Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction［J］.IEEE Transactions on Information Theory，2009，55（5）：2230-2249.

［7］Needell D，Tropp J A.CoSaMP：Iterative signal recovery form incomplete and inaccurate samples［J］.Applied and Computational Harmonic Analysis，2008，26（3）：301-321.

［8］Blumensath T，Davies M E.Iterative hard thresholding for compressed sensing［J］.Applied and Computational Harmonic Analysis，2009，27（3）：265-274.

［9］李佳，王強，沈毅，李波，等.壓縮感知中測量矩陣與重建算法的協同構造［J］.電子學報，2013，41（1）：29-34.

［10］王娟.量子免疫克隆算法研究及在壓縮感知重構中的應用［D］.南京：南京郵電大學，2012.

［11］朱豐，張群，柏又青，馮有前，張維強，等.一種新的基于遺傳算法的壓縮感知重構方法及其在SAR高分辨距離像重構中的應用［J］.控制與決策，2011，27（11）：1669-1675.

［12］Thong TDo，Gan Lu，Nguyen，Tran D.Sparsity adaptive matching pursuit algorithm for practical compressed sensing.Asilomar Conference on Signals，Systems and Computers［J］.Pacific Grove，California，2008（10）：581-587.

［13］劉亞新，趙瑞珍，胡紹海，姜春暉.用于壓縮感知信號重建的正則化自適應匹配追蹤算法［J］.電子與信息學報，2010，32（11）：2713-2717.

［14］Licheng Jiao，Yangyang Li.Quantum-inspired Immune Clonal Optimization［C］.Neural Networks and Brain，2005.ICNN＆B‘05.International Conference on.2005：461-466.

Algorithm of Com pressed Sensor Data Reconstruction Based on Quantum-inspired Immune Clon

QIHao1，LIU Zhou-zhou2
（1.School of Electronics and Information，Northwest Polytechnical University，Xi’an 710072，China；2.Xi’an Aeronautical University，Xi’an 710072，China）

An algorithm of compressed sensor data reconstruction，called Q-CSDR，based on the algorithm of quantum-inspired immune clon，is proposed in this paper.Q-CSDR can increase the probability of data reconstruction through framing the data adaptively.Because of its excellent performance，Q-CSDR uses the algorithm to accurately reconstruct the data.The experiment results show that，according to the sparsity of the original data，the algorithm can automatically adjust compression ratio，raise the accuracy of data reconstruction and adaptwell to high sparsity data reconstruction.It is used in the field security system of Emperor Qinshihuang｀smausoleum sitemuseum with good performance.

Quantum-inspired Immune Clonal Algorithm；Compressed Sensor；Data Reconstruction；Sparsity

10.3969／j.issn.1002-2279.2014.05.011

TP24

：A

：1002-2279（2014）05-0034-06

國家科技支撐計劃（批準號：2010BAK67B09，2012BAK14B01）

祁浩（1982-），男，甘肅蘭州人，博士研究生，主研方向：從事無線傳感器網絡、智能信息處理等方面的研究。

2014-06-11