一種改進型煙花重構算法及其在沖擊波測試領域中的應用

張家慧，王英志，李新格，沈亮

（1.長春理工大學 電子信息工程學院，長春 130022；2.北京控制工程研究所，北京 100190）

近幾年，由 Candès、Donoho和 Tao等人提出了一種全新的信號采集和處理理論——壓縮感知理論（Compressed Sensing，CS）［1-2］。該理論指出：只要信號是稀疏的或在某個變換域是稀疏的，就可以用一個與變換基不相關的觀測矩陣將變換所得的高維信號投影到一個低維空間上，然后通過求解一個優化問題從這些少量但包含足夠重構信息的投影中以高概率重構出原信號［3］。壓縮感知理論突破了傳統的采樣定理，使用更低的采樣率對信號進行隨機采樣和壓縮，節約系統資源，在處理海量復雜信號時具有極大優勢，廣泛應用于各工程領域中。沖擊波信號屬于瞬態信號，具有時域持續時間短，有明顯的開端和結束節點等特點，信息相對集中，即在整個采集過程中，信息密度較低，可以認為存在某稀疏域能對沖擊波信號進行稀疏表示。因此，本文將沖擊波信號應用于壓縮感知理論中檢測重構算法性能。

壓縮感知理論的研究內容主要可分為：信號稀疏表示、觀測矩陣建立以及重構算法設計。重構算法設計是整個信號處理過程的關鍵，所以本文圍繞重構算法展開研究。目前，常用的重構算法主要有凸優化類算法、組合優化類算法以及匹配追蹤類算法等［4］，其中匹配追蹤類算法計算量較小，重建效果好，易于實現，應用范圍最廣。但在使用匹配追蹤類算法重構信號時，由于其貪婪特性，雖然在局部搜索時能快速收斂，但缺少全局搜索機制，算法易陷入局部極值解。在沖擊波測試領域，對沖擊波信號的重構效果要求較高，需要提升重構算法的求解精度。考慮到信號重構過程是一個l0范數最小化問題，而智能優化算法是建立在生物智能或物理現象基礎上的隨機搜索算法，在沒有集中控制且不提供全局模型的前提下，對計算數據的不確定性有很強的適應能力，可以更好地解決最優化問題。鑒于此，本文將搜索能力強的煙花算法引入到壓縮感知技術中，提出一種改進型煙花重構算法，減小算法對信號的重構誤差，優化算法在同類型算法中的運行效率，提升算法在沖擊波測試領域中的實用性。

1 壓縮感知與重構算法結構

1.1 壓縮感知數學模型

壓縮感知理論的核心思想是對具有稀疏性的信號進行觀測，降低觀測過程中的冗余信息，從而實現以較少數據對原信號的高概率重構。

壓縮感知理論應用的必要條件是信號稀疏，若信號x是稀疏的，可以對信號直接進行觀測。設Φ∈RM×N，是觀測矩陣，其觀測過程為：

其中，y是M×1維觀測信號，且M<

若是信號x非稀疏，需先對x進行稀疏表示，設Ψ∈RM×N，是標準正交基，θ∈RN×1，是稀疏度為K的稀疏信號，則信號x的稀疏表示過程為：

結合式（1）和式（2）得到非稀疏信號觀測過程為：

其中，Α=ΦΨ，是傳感矩陣。

當接收到y時，若A滿足有限等距性質（Re?stricted Isometry Property，RIP），只要觀測數滿足M=O(Klog(N/K))，就能精準重構出原始稀疏信號。重構模型表示為：

除此之外，還有通過將l0范數松弛為lp（p≤1）范數或基于貝葉斯框架等方法實現信號重構。

1.2 智能優化重構算法

在使用智能優化算法實現壓縮感知重構過程時，可以使用直接對式（4）的最小化問題進行全局尋優的方法［5-7］：以被測信號長度N作為個體的維度，使用重構誤差公式作為適應度函數，個體位置表示為0或1的二進制形式，通過算法的全局尋優能力獲得信號非零元素位置信息，再利用最小二乘法獲得非零元素位置的幅值。這種重構算法擁有全局搜索能力，可以求得算法的近似最優解，相較于只能尋求到次優解的重構算法，擁有更高的精確度，能以更大概率恢復出原始信號。

雖然這種方法理論上可以求出問題的近似最優解，但僅在N較小時可行，N增大時，算法尋優能力減弱，實際應用能力較差。本文基于此提出一種新型重構算法，相較于前述算法，以信號稀疏度K作為算法維度，［1，N］作為算法解空間，信號中非零位置索引集作為算法的解，算法的結構框圖如圖1所示。

圖1 新型重構算法的結構框圖

由圖1知，本文的重構算法由前置算法和智能優化重構算法組合形成。信號重構時，觀測信號y和傳感矩陣A輸入重構算法中。通過前置算法，得到從A中挑選出的最匹配y或y殘差的列向量索引組成原子最終構造集F，將F傳輸至智能優化重構算法中，得到算法的維度和一個可行解，補全算法的初始參數后，通過算法全局尋優得到重構信號并輸出。其中，因為信號稀疏度不能先驗，無法確定算法維度，而稀疏度自適應匹配追蹤（Sparsity Adaptive Matching Pur?suit，SAMP）算法雖然可以求解稀疏度，但算法步長固定，易產生過估計現象，影響重構效果。本文結合文獻［8］中的雙閾值變步長思想和文獻［9］中的算法回溯思想得到一種改進型SAMP算法，減小對信號稀疏度的估計誤差，在算法運行結束時將F提供給基于智能優化的重構算法。而重構算法則使用全局尋優能力求得近似最優解，提升重構算法精確度。重構算法的適應度函數仍為信號的重構誤差公式，被測信號稀疏度K為算法維度，信號非零元素位置表示個體位置，F的大小表示算法維度K，F自身可表示一個可行解。

本文提出的新型重構算法，相較于文獻［5-7］中的方法，算法維度K<

2 煙花重構算法及改進算法

煙花算法（Firework Algorithm，FWA）是一種基于非生物種群的智能優化算法。算法模擬自然界中煙花爆炸過程進行數學建模，引入隨機因素和選擇策略，形成一種求解復雜優化問題最優解的并行式全局概率搜索算法。煙花算法一般由爆炸算子、變異算子、映射操作和選擇策略四部分組成，其中，爆炸算子是FWA中的重要組成部分，包括對爆炸幅度、爆炸強度和位移操作的計算。雖然FWA提出的時間較晚，但由于算法具有良好的全局搜索方法和局部優化方法，在解決復雜優化問題上很有優勢，因此本文使用FWA對信號重構過程進行優化。

2.1 煙花重構算法

為了方便表示，本文將基于FWA得到的重構算法命名為煙花重構算法（Firework Reconstruc?tion Algorithm，FWRA）。根據1.2節中本文提出的重構算法結構，FWRA的具體步驟如下所示：

輸入：測量矩陣Ф，測量信號y，前置算法求解得到的原子最終構造集F。

初始化：解空間范圍Bound∈[1,N]；煙花個體維度Dim=K；初始煙花數量Seednum；第一個煙花X1=F；火花總數Sonnum；算法最大迭代次數Maxiteration。

步驟一：解空間Bound內，隨機生成（Seednum-1）個煙花。

步驟二：適應函數為：

根據式（6）計算煙花的適應度值，其中，適應度值fitness越小表示信號的重構效果越好；反之，表示信號的重構效果越差。

步驟三：根據離散化的爆炸算子產生爆炸火花。

步驟四：為了保證種群的多樣性，對任意數量火花進行離散高斯變異操作，產生高斯變異火花。

步驟五：計算適應度值，并找到種群中的適應度值最小的煙花或火花，其代表的空間位置為當代最優適應度值Pbest，與群體最優適應度值Xbest作比較，若Pbest更小則取代Xbest，替換相應可行解。

步驟六：判斷是否達到算法最大迭代次數Maxiteration，若未達到則應用選擇策略在當前種群內選擇煙花進行下一次迭代，否則算法結束。

輸出：Xbest和相應的可行解。

FWRA算法的流程圖如圖2所示。

圖2 煙花重構算法流程圖

2.2 對煙花重構算法的改進

為了進一步提升FWRA的算法性能，本文從兩方面對算法進行改進：一方面是利用F中原子個數不變時，原子索引具有一致性的特點，將算法改為非數值優化的求解方式，有利于減小信號的重構誤差；另一方面是對算法中的重要算子進行改進。算法的爆炸強度、爆炸幅度和選擇策略公式在解決信號重構問題時存在缺陷，為避免計算資源的浪費，本文在保留爆炸強度特點的同時，消除公式中極小常數對爆炸火花數量的影響，自適應爆炸幅度平衡全局和局部搜索，并使用耗時更少的輪盤賭選擇策略，提升算法的精確度和運行效率。為了將改進后的FWRA與FWRA作區分，將改進后的FWRA命名為IFWRA（Improved FWRA）。

（1）非數值優化方法

在相同的實驗條件下，不同的重構算法F中原子數固定時，選取的原子索引不變。即若已知測量信號y和原始信號的稀疏度K，在傳感矩陣A中僅有唯一一組列向量可以成功匹配出原始信號，不存在其它列向量組合可以再重構出原始信號［10-11］。因而，在通過前置算法已知稀疏度K和一組原子索引的情況下，僅通過對固定解元素排列組合的方式進行求解。而在非數值優化下的FWRA，仍然保留了爆炸算子、變異算子、選擇策略，但由于解元素不能超出解空間范圍，需要重新設計爆炸算子和變異算子的計算公式并舍棄映射規則。

在爆炸算子中，規定每代所有煙花的爆炸幅度都相同，并使用兩元素優化（2-opt）局部搜索方法進行位移操作，2-opt操作過程如圖3所示。

圖3 2-opt局部搜索操作

得到新可行解的適應度值f（Xg），與原解f（Xi）相比，若適應度值更小，則可以保留下來，若適應度值更大，也有可能被一定概率接受，設接受差解的概率為Pa，即：

其中，ρ為控制參數，由式（7）知，如果兩個適應度值越相近，控制參數ρ越小，則接受的概率越高。這樣的設定是為了使算法有一定的幾率接受局部改變，同時減少一些無意義的改變。如果生成的火花與煙花相距太遠，兩個適應度值相差過大，那么該操作基本無效。參數ρ控制接受概率Pa的大小，防止其過大或過小。

在變異算子中，使用一種介于2-opt和3-opt之間的2h-opt局部搜索策略，優化解中的局部點，且變異算子中不考慮定義接收差解的概率，以強化算法的搜索方向，2h-opt操作過程如圖4所示。

圖4 2h-opt局部搜索操作

（2）精簡爆炸強度

FWRA的爆炸強度公式如下：

其中，m0表示預設火花總量最大值；fmax表示最大適應度值，?表示數量級約為1e-15的極小常數。

使用FWRA解決信號重構問題時，算法的適應度值f（Xi）的數量級也在1e-15左右，此時爆炸強度公式中存在的極小常數?不能忽略，致使每次煙花爆炸產生的火花數量都比預分配值多，最后分配到的火花總量遠大于預設的火花總量最大值，嚴重影響算法的運行效率。為了避免?的影響，本文提出一種精簡爆炸強度公式如下：

其中，m表示更新后的火花總量最大值。

式（9）將適應度值差值分為零值與非零值兩種情況分配火花，解決了公式無效化問題。同時，為了避免最優解煙花個數不唯一時火花總數遠超預設值的情況，對m進行非實時更新，使生成的火花總量接近預設值。同時，相較于式（8）中最優煙花下分配到的火花數量過度，易產生重復解，浪費資源的情況。本式按比例合理分配火花數量，在保證算法搜索能力的前提下提升算法的運行效率，節約算法資源。

（3）自適應爆炸幅度

在算法離散優化過程中，由于局部函數內空間差異性較大，比較一次迭代是否產生更優解沒有意義，因為當群體陷入局部收斂時，往往需要經多次變化才有機會跳出局部極值，這需要多次的迭代和計算代價。參考動態搜索煙花算法（dynFWA）中的爆炸幅度公式［12］，本文提出一種新的自適應爆炸幅度公式，用式（7）中控制參數ρ表示，設若連續15代不改變，則減小ρ，反之，則增大ρ，如式（10）所示：

其中，C+表示增大因子；C-表示縮小因子；Num為記錄煙花的解連續不改變的次數。

在群體最優適應度值Xbest比當代最優適應度值Pbest小時，爆炸產生更優值，擴大爆炸幅度加強全局搜索；在Xbest連續15次比Pbest大時，煙花陷入局部最優，減小爆炸幅度，加強局部搜索，讓煙花有更大可能跳出局部極值。

（4）精英-輪盤賭選擇策略

FWRA中基于歐式距離度量的選擇策略，在每一代構建群體中任意兩點間歐式距離矩陣，消耗算法的運行時間，且在離散化算法中保留優秀解的能力差，不適合使用。因此，除了繼續應用精英選擇策略，保留每代最優解，對其它個體采取輪盤賭的選擇方式，提高優秀解被選擇的概率，但不排除掉全部差解。定義煙花或火花Xi被選擇的概率為：

由式（11）得到除最優個體的選擇概率后，再根據輪盤賭策略選擇子代。由定義可知，適應度值越小的個體有越大的概率被選擇進入下一次迭代中，適應度值越大的個體性能雖然較差，但有利于發展種群的多樣性，所以也存在著小概率的入選機會。

2.3 改進型煙花重構算法

結合FWRA，可得IFWRA的具體步驟如下：

輸入：測量矩陣Ф，測量信號y，前置算法求解得到的原子最終構造集F。

初始化：解元素固定為F中的原子索引；煙花個體維度Dim=K；初始煙花數量Seednum；第一個煙花X1=F；火花總數Sonnum；算法最大迭代次數Maxiteration。

步驟一：使用固定的解元素，隨機生成（Seednum-1）個煙花。

步驟二：根據式（6）計算煙花的適應度值。

步驟三：首先使用式（9）計算每個煙花產生的火花數量，再使用式（10）自適應爆炸幅度，接著使用2-opt方法進行位移操作，最后結合式（7）得到爆炸火花。

步驟四：對任意數量火花使用2h-opt方法進行局部點變異操作，產生變異火花。

步驟五：計算適應度值，找到種群中當代最優適應度值Pbest，與群體最優適應度值Xbest作比較，若Pbest更小則取代Xbest，并替換相應可行解。

步驟六：判斷是否達到算法最大迭代次數Maxiteration，若未達到則結合式（11）的精英-輪盤賭選擇策略生成下一代煙花，否則算法結束。

輸出：Xbest和相應的可行解。

IFWRA的算法流程圖如圖5所示。

圖5 IFWRA算法流程圖

IFWRA基于FWRA，使用非數值優化方法固定算法解空間，去除爆炸強度公式中極小常數導致的實際火花總量冗余影響，自適應煙花的爆炸幅度防止算法陷入局部最優，并使用耗時更少的精英-輪盤賭選擇策略，有效提升了算法的重構性能。相較于FWRA，IFWRA對信號的重構誤差更低，算法運行效率更高。

3 算法性能測試

本文使用高斯稀疏信號作為測試信號，檢驗IFWRA的算法性能。IFWRA作為新型重構算法，在測試時，使用FWRA比較IFWRA中改進方法的有效性，蟻群重構算法（Ant Colony Reconstruc?tion Algorithm，ACRA）檢驗IFWRA的搜索能力，匹配追蹤類算法中的SAMP算法對照IFWRA近似最優解的高精確性。其中，所有新型組合算法均使用相同前置算法，避免影響智能優化算法的搜索能力，使用均方根誤差表示重構誤差，設計實驗一。

實驗一：信號長度N=256的高斯稀疏信號作為被測信號進行實驗，測量數M=128，稀疏度K=15∶5∶60，測量矩陣為伯努利隨機矩陣，每個K值測試CNT=50次，分別使用IFWRA、FWRA、ACRA和SAMP（S=8）算法對信號進行重構，觀察算法對信號的重構誤差和運行效率。其中，FWRA和IFWRA中部分初始參數為：Seednum=5；Sonnum=50；Maxiteration=500；X1=F。ACRA 中部分初始參數為：蟻群數量Antnum=50；Maxiteration=500；第一只螞蟻位置A1=F。

由圖6可知，IFWRA的重構誤差在稀疏度K從15到60的變化過程中始終最低，重構誤差均值為5.982 4e-16，比次優的ACRA低約18.72%。IFWRA相較于FWRA，能避免算法陷入局部最優，擁有更高的搜索能力，重構誤差比FWRA算法低約38.93%。而SAMP算法的重構誤差在同類型匹配追蹤類算法中較低，但相較于組合算法最高，誤差均值為1.941 0e-15，IFWRA的重構誤差相較于SAMP算法低約69.18%。

圖6 算法重構誤差與稀疏度K的關系

選取K=15和K=30時的 IFWRA、ACRA和FWRA每代最優解均值進行比較，觀察智能優化算法的全局尋優能力。

從圖7、圖8中K=15和K=30顯示的算法最優適應度值曲線的變化情況來看，IFWRA在三種智能優化算法中全局尋優能力最強。IFWRA和ACRA的曲線收斂速度較快，最優適應度值也一直遠低于FWRA。而IFWRA的曲線相較于ACRA始終最低，證明IFWRA搜索能力最強。

圖7 K=15時，算法最優適應度值與迭代次數的關系

圖8 K=30時，算法最優適應度值與迭代次數的關系

由圖6可知，SAMP算法的重構誤差數量級在1e-15左右，而組合算法的重構誤差數量級在1e-16左右，可見，SAMP算法無法滿足對信號高精度重構的要求。且新型重構算法以犧牲部分算法運行時間為代價，尋求更小的重構誤差，相較于SAMP算法，在運行效率上稍顯劣勢。所以，考慮到實際應用性與公平性，不再使用SAMP算法作對比。

由圖9可知，在新型重構算法中，IFWRA的運行效率始終最高，平均運行時間為13.789 9 s，相較于平均運行時間為30.406 9 s的FWRA，運行效率提升約54.65%。ACRA耗時最長，平均運行時間為63.737 1 s，IFWRA相較于ACRA的運行效率提升約78.36%。ACRA算法復雜度約為O（D4），其中D表示算法維度，而IFWRA與IFWRA算法整體計算結構不變，算法復雜度均約為O（T2），其中T表示算法粒子數，所以ACRA的運行時間隨K（K=D）增大呈四次冪遞增，FWRA和IF?WRA的運行時間雖然也隨K的增大而增加，但由于T基本無變化，算法的時間運行曲線增長速率較慢，所以ACRA僅在K=15和20時相較于FWRA稍具優勢，當K>20后，算法運行時間迅速增大。而IFWRA相較于FWRA，算法運行時產生的火花總數更低，且使用了耗時更小的選擇策略，算法計算量更少，運行效率更高。

圖9 算法運行時間與稀疏度K的關系

4 應用結果

在實際應用中，準確測量沖擊波信號主要是為了合理規劃武器裝備與測試環境，降低武器測試風險［13］。所以，對沖擊波信號進行信號重構時不要求實時性，反而更重視精確性。本文截取50 psi量程傳感器實測沖擊波信號，進行精確截取、降頻等預處理，得到信號長度N=4 096的沖擊波時域信號，再使用離散小波矩陣對信號進行表示，得到小波域沖擊波信號［14］。沖擊波的時域和小波域圖形如圖10所示。

圖10 50 psi實測沖擊波信號小波基稀疏結果

由圖10可知，圖10（a）中的時域沖擊波信號是非稀疏信號，但圖10（b）中的小波域沖擊波信號波形具有稀疏性，表明離散小波變換可以實現沖擊波信號的稀疏化。

本文為了驗證IFWRA在沖擊波測試領域的應用性，以沖擊波信號為測試信號，比較IFWRA和其他同類型重構算法對信號的重構誤差和運行效率，設計實驗二。

實驗二：截取一組50 psi量程傳感器實測沖擊波信號作為被測信號進行實驗，信號長度N=4 096，測量數M=2 048，稀疏字典為離散小波變換矩陣，測量矩陣為伯努利隨機矩陣，對信號進行CNT=50次測試，分別使用IFWRA、FWRA、ACRA對信號進行重構，觀察算法的重構誤差和運行效率。其中，FWRA和IFWRA部分初始參數：Seednum=5；Sonnum=50；Maxiteration=500；X1=F。ACRA中初始參數為：Antnum=50；Maxiteration=500；A1=F。

結合表1和圖11—圖13可知，IFWRA可應用于沖擊波測試領域中實現對信號的重構，且在同類型組合算法中，IFWRA算法性能最優。IF?WRA在圖11中的誤差曲線相較于圖12和圖13中的算法誤差曲線整體波動最小，表明重構誤差最小，為1.148 8e-18，相較于次優的ACRA減小8.15%，相較于FWRA減小38.88%。IFWRA的算法運行效率也最高，算法運行時間為116.650 2 s，相較于次優的ACRA提升32.34%，相較于FWRA提升37.53%。分析圖9知，ACRA僅在K較小時存在算法耗時低于FWRA的情況，表明本文選取的50 psi沖擊波信號在小波域上稀疏性能好，稀疏度K極小。

表1 算法的運行時間和對信號的重構誤差

圖11 使用IFWRA對沖擊波信號進行重構

圖12 使用ACRA對沖擊波信號進行重構

圖13 使用FWRA對沖擊波信號進行重構

IFWRA與其它重構算法在對比實驗中算法性能依舊最佳，實驗結果雖然與實驗一相仿，但意義不同。實驗一是為了驗證IFWRA的算法性能，證明對IFWRA改進方法的有效性。而實驗二主要是為了驗證IFWRA的實用性。當IFWRA以實測沖擊波信號為測試信號仍實現精確重構時，肯定了IFWRA的應用范圍，證明IFWRA的研究技術較為成熟，已經可以應用于工程實踐中。同時，實驗二也為壓縮感知技術在以沖擊波為代表的瞬態信號領域的應用提供研究和參考價值，意義更重大。

5 結論

本文提出了一種改進型煙花重構算法，在使用煙花算法的全局尋優能力優化信號重構過程的基礎上，從算法的求解方式和算子缺陷兩方面對算法進行改進：將算法改為非數值優化求解方式，固定解空間，增強算法搜索能力；精簡爆炸強度，自適應爆炸幅度和使用基于精英-輪盤賭的選擇策略，有效節約算法計算資源。使用高斯稀疏信號和50 psi量程常感器實測沖擊波信號，將本文算法與同類型和傳統重構算法進行對比，測試結果表明：在算法對信號的重構誤差比較上，本文算法始終優于其他對比算法；在算法運行效率的比較上，本文算法的運行效率在同類型算法中始終最高。