呂冠男，劉海鵬，盧建宏

（昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650000）

0 引言

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

壓縮感知理論表明，當(dāng)一個(gè)信號(hào)具有稀疏性，就可以用一個(gè)與原信號(hào)不相關(guān)的測量矩陣，以遠(yuǎn)低于奈奎斯特采樣率采集到的信號(hào)測量值進(jìn)行壓縮采樣，再用重構(gòu)算法恢復(fù)出原始信號(hào)。壓縮感知具有所需采樣點(diǎn)少、數(shù)據(jù)儲(chǔ)存量低等特點(diǎn)，在信號(hào)采集[4]、雷達(dá)探測、數(shù)據(jù)通信[5]等領(lǐng)域被廣泛研究。

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

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

1 算法描述

1.1 麻雀搜索算法

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

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

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

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

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

（4）發(fā)現(xiàn)捕食者的麻雀會(huì)發(fā)出報(bào)警信號(hào)，當(dāng)警報(bào)值過大，麻雀們會(huì)離開危險(xiǎn)區(qū)域進(jìn)入安全區(qū)域。

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

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

1.2 黃金正弦算法

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

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

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

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

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

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

1.3 改進(jìn)麻雀算法

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

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

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

2 實(shí)驗(yàn)部分

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

2.1 算法收斂速度比對(duì)

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

圖2 收斂速度對(duì)比實(shí)驗(yàn)

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

2.2 圖像重構(gòu)實(shí)驗(yàn)對(duì)比

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

圖3 高斯隨機(jī)矩陣

圖4 麻雀算法矩陣

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

圖5 改進(jìn)麻雀算法矩陣

（1）PSNR 主要用來衡量圖像重構(gòu)質(zhì)量的性能，定義為：

（2）RE 為相對(duì)誤差，定義為：

（3）UAV 為平均互相關(guān)系數(shù)，即絕對(duì)值大于或等于Gram 矩陣非對(duì)角元素的平均值，用以評(píng)價(jià)矩陣的整體相關(guān)性，定義為：

當(dāng)t=0 時(shí)，可獲得一個(gè)絕對(duì)項(xiàng)的簡單平均值，gij表示Gram 矩陣的第i行j列的值。Gram 矩陣可表示為：

性能指標(biāo)對(duì)比如表1、表2 所示。

表1 OMP 算法重構(gòu)圖像數(shù)據(jù)對(duì)比

表2 LAOMP 算法重構(gòu)圖像數(shù)據(jù)對(duì)比

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

3 結(jié)語

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