基于麻雀算法的壓縮感知觀測矩陣優(yōu)化方法

呂冠男，劉海鵬，盧建宏

（昆明理工大學 信息工程與自動化學院，云南 昆明 650000）

0 引言

奈奎斯特采樣定理定義：當采樣頻率大于原始信號頻率的兩倍，就能從離散數字信號中恢復出原始信號。若按采樣定理來采樣，會使得采樣信息量過大，導致存儲空間的浪費。直到2006 年，壓縮感知理論（Compressed Sensing，CS）[1-3]問世，這個問題才得到較為有效的解決。

壓縮感知理論表明，當一個信號具有稀疏性，就可以用一個與原信號不相關的測量矩陣，以遠低于奈奎斯特采樣率采集到的信號測量值進行壓縮采樣，再用重構算法恢復出原始信號。壓縮感知具有所需采樣點少、數據儲存量低等特點，在信號采集[4]、雷達探測、數據通信[5]等領域被廣泛研究。

觀測矩陣的特性決定了壓縮感知理論是否可行，也決定了是否能夠實現對信號的高概率重構，是壓縮感知理論十分重要的一個部分。觀測矩陣主要分為確定性矩陣和隨機矩陣兩大類。確定性矩陣包括循環(huán)矩陣、托普利茨矩陣等，隨機矩陣包括高斯矩陣[6-7]、伯努利矩陣等。目前，大部分觀測矩陣還存在一些不足，如托普利茲觀測矩陣的重構性能較差等。觀測矩陣需要滿足有限等距準則[8]（Restricted Isometry Property，RIP），該準則表明，感知矩陣的性能與觀測矩陣和稀疏矩陣之間的互相關性成反比，即矩陣間的互相關性越小，那么這個感知矩陣的性能就越好。

相比于確定性測量矩陣，隨機測量矩陣具有所需測量數少、重建性能好的優(yōu)點。但是隨機測量矩陣由于計算的復雜性，使得儲存量比確定性測量矩陣大，且矩陣重建的不確定性更高。因此，本文針對隨機測量矩陣的缺點，提出將智能算法融入隨機測量矩陣優(yōu)化算法中，以此解決最優(yōu)相關性的問題。

1 算法描述

1.1 麻雀搜索算法

由前文可知，隨機矩陣優(yōu)化算法并不能很好地解決最優(yōu)相關性的問題，而麻雀搜索算法[9]（Sparrow Search Algorithm，SSA）具有較好的全局尋優(yōu)特性。將SSA 應用到觀測矩陣的優(yōu)化中，可以使觀測矩陣與稀疏矩陣的互相關系數降低，以此來提高信號的重構精度。

SSA 算法具有尋優(yōu)能力強、收斂速度快等特點。以麻雀種群的覓食、警戒行為為基礎建立麻雀算法數學模型的規(guī)則如下：

（1）發(fā)現者，負責搜索到具有豐富食物的區(qū)域，為所有的加入者提供覓食方向；

（2）加入者，跟隨一個發(fā)現者，在覓食過程中，加入者跟隨提供最好食物的發(fā)現者，在此發(fā)現者周圍覓食；

（3）麻雀群體中的發(fā)現者和加入者是隨時間變化的，但是比重不會發(fā)生改變；

（4）發(fā)現捕食者的麻雀會發(fā)出報警信號，當警報值過大，麻雀們會離開危險區(qū)域進入安全區(qū)域。

由此可見，SSA 中的麻雀可以分為發(fā)現者和加入者。發(fā)現者繼續(xù)尋找食物，加入者跟隨發(fā)現者覓食，且每一只麻雀隨時都在對捕食者進行警戒。

盡管SSA 具有較好的全局尋優(yōu)特性，但是SSA與其他基于種群的優(yōu)化算法一樣，都是隨機地生成種群，這會使得在算法運行過程中，確定第一代發(fā)現者所耗的時間偏長。如果能改進算法，縮短第一批發(fā)現者的確定時間，就能在節(jié)約時間的同時減少算法迭代次數。另外，SSA 的位置更新方式會使算法陷入局部最優(yōu)，使得全局搜索能力受損。而黃金正弦算法（Gold-SA）[10]通過隨機生成每個維度的均勻分布來掃描搜索空間，相較于其他算法具有一定優(yōu)勢。將黃金正弦算法加入到SSA 中，能進一步加強SSA 的全局尋優(yōu)能力，還能更快地確定第一代發(fā)現者，減少算法運行時間。

1.2 黃金正弦算法

于2017 年提出的黃金正弦算法與其他基于種群的算法一樣，最初的種群也是隨機生成的。但此算法的目的是生成每個維度均勻分布的初始種群，以此來達到更好的搜索效果。算法的表達式為：

式中：Vi表示第i個個體的初始值，ub是搜索空間的上限值，lb是搜索空間的下限值。

Gold-SA 算法引入了黃金分割系數x1和x2來更新位置，以此縮小搜索空間，使個體趨近最優(yōu)值的速度更快。黃金分割系數如下：

傳感器接收到一次指令后都會輸出一串數據量很大的數據，如何快速接收并且不遺漏數據是一個需要解決的關鍵問題，針對數據量大的問題，選擇在內存中開辟兩塊容量為300的臨時緩存區(qū)，當有數據傳來時，先進行存儲，當存儲完了之后再進行數據處理，這樣便避免了數據丟失的問題.

式中：a和b為黃金分割比例初始搜索值，一般a=-π，b=π，。Gold-SA 算法通過下式進行位置更新：

此算法的基本流程是：先初始化參數，再設置黃金正弦相關參數；計算適應度值、計算黃金分割率，更新位置，計算適應度值，更新最佳位置并記錄；判斷迭代是否結束，結束得到最優(yōu)位置則結束算法，不然重復前面的步驟。

1.3 改進麻雀算法

本文的算法將Gold-SA 算法應用在SSA 發(fā)現者和加入者的確定步驟中，使“搜索”和“開發(fā)”更加均衡，縮小了搜索空間的同時還能減小陷入局部最優(yōu)的概率，獲得更好的全局特性。加入改進麻雀算法優(yōu)化觀測矩陣的流程如圖1 所示。

圖1 優(yōu)化觀測矩陣流程圖

如圖1 所示，整個過程中，首先要初始化稀疏矩陣Ψ、隨機高斯矩陣Φ，然后進行特征分解，再計算出待優(yōu)化矩陣Γ，之后通過改進麻雀算法找到最佳位置，最后求出與最佳位置對應的最佳測量矩陣并輸出。

2 實驗部分

以下仿真結果均在Matlab R2017a 環(huán)境下得到。

2.1 算法收斂速度比對

算法收斂速度的快慢在很大程度上影響算法的運行時間，收斂速度越快，運行時間越短。因此，為了驗證本文改進的麻雀算法比原始麻雀算法的運行速度更快，首先做了改進麻雀算法與傳統(tǒng)麻雀算法的收斂速度對比實驗。實驗循環(huán)次數為50 次，結果如圖2 所示。

圖2 收斂速度對比實驗

在圖2 中可以清晰地看到，相比于傳統(tǒng)的SSA算法，本文提出的改進算法有更快的收斂速度。當迭代次數為190 次時，本算法基本完成了對目標函數的逼近，而傳統(tǒng)的SSA 算法在500 次迭代完后依然離目標較遠。由此可見，本文提出的改進SSA 算法相比于傳統(tǒng)的SSA 算法而言，大大減少了迭代次數，縮短了算法運行時間。

2.2 圖像重構實驗對比

之前的實驗只是簡單地證明了本文提出的改進算法相比于傳統(tǒng)的SSA 算法具有更快的收斂速度，在這一部分，給出通過兩種算法分別構造出的測量矩陣結合OMP 算法、LAOMP 算法重構出的二維圖像直觀視覺效果對比圖。采樣率選擇0.5，實驗10 次取平均值，結果如圖3 所示。

圖3 高斯隨機矩陣

圖4 麻雀算法矩陣

圖3～圖5 中，子圖（a）、（b）、（c）分別代表原始圖片、OMP 算法重構出來的圖片和LAOMP 算法重構出的圖片。僅從圖片上看，區(qū)別不是很明顯，但本文的改進算法還是比傳統(tǒng)的麻雀算法求解的矩陣和高斯隨機矩陣重構出的圖片要清晰一點。為了使實驗更具有說服力，下面對實驗的各項數據進行對比，實驗數據如表1、表2 所示，以重構圖像的峰值信噪比（Peak Signal to Noise Ratio，PSNR）、平均互相關系數（UAV）、運行時間（TIME）、相對誤差（Relative Error，RE）作為算法優(yōu)劣的評判標準，定義如下。

圖5 改進麻雀算法矩陣

（1）PSNR 主要用來衡量圖像重構質量的性能，定義為：

（2）RE 為相對誤差，定義為：

（3）UAV 為平均互相關系數，即絕對值大于或等于Gram 矩陣非對角元素的平均值，用以評價矩陣的整體相關性，定義為：

當t=0 時，可獲得一個絕對項的簡單平均值，gij表示Gram 矩陣的第i行j列的值。Gram 矩陣可表示為：

性能指標對比如表1、表2 所示。

表1 OMP 算法重構圖像數據對比

表2 LAOMP 算法重構圖像數據對比

由表1、表2 可知，采樣率為0.5 時，無論是采用OMP 算法還是LAOMP 算法，本文算法構造的矩陣比傳統(tǒng)麻雀算法和高斯隨機矩陣重構出來的圖像的峰值信噪比更高，運行的時間更短，重構誤差也最小。本文算法構造的觀測矩陣與稀疏矩陣的互相關系數為0.054 3，而高斯隨機矩陣與稀疏矩陣的互相關系數為0.070 5，傳統(tǒng)麻雀算法為0.060 1，同樣表明用本算法構造的感知矩陣的性能要比其他兩種算法好。

3 結語

本文就利用隨機矩陣構造觀測矩陣并不能解決最優(yōu)相關性問題進行改進，引入麻雀搜索算法加強全局尋優(yōu)性，使得觀測矩陣與稀疏矩陣的互相關系數降低，以此提高信號的重構精度。再將黃金正弦算法應用在SSA 發(fā)現者和加入者的確定步驟中，使“搜索”和“開發(fā)”更加均衡，降低了由于SSA 隨機生成種群而造成的尋優(yōu)時間過長造成的影響，減少了算法迭代次數的同時，也使算法保持原有的尋優(yōu)能力。經過二維圖像重構仿真對比和算法收斂速度實驗對比，發(fā)現該算法相比于隨機矩陣和傳統(tǒng)SSA 具有更快的運行速度和信號恢復能力。下一步的工作計劃是尋找新的智能種群算法與SSA 結合，以求進一步降低互相關系數。