結合遺傳算法的匹配追蹤算法的性能分析﹡

高麗貞

0 引言

匹配追蹤[1]( MP, Marching Method)是譜分解算法的一個重要分支。MP算法的原理簡單，便于實現。但是MP算法在每一次求精的分解過程中，需要在超完備展開函數集合中找最優原子，是一個非常耗時的過程。因而，龐大的計算量成為MP算法在實際應用中的瓶頸。

近年來，不少學者發展了很多 MP算法的改進算法[2-5]，均具有一定的實際意義。其中，遺傳算法[6](GA，Genetic Algorithm)是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。文中采用遺傳算法來減少匹配追蹤算法的計算量，得到了相同的匹配結果，顯著提高了計算效率。

1 算法的原理及其實現步驟

1.1 MP算法的原理

加法信號模型表示自然信號，在信號處理與數據分析等領域一直得到非常廣泛的應用。該模型用公式可以表示為：

式中，f(t)表示信號，hn(t)表示信號的基函數，an表示基對應的系數。即，信號被分解為加權的基函數的迭加形式。

匹配追蹤算法實際上是上述式(1)的近似求解方法。令 H表示 Hilbert空間，定義 H中的原子庫D = ( ei)i∈I，且滿足ei= 1。其中， ei是通過對一個簡單窗函數 g (t)∈ L2(R)的時間平移、頻率調制和尺度變換，而生成一個過完備時頻原子庫，式子表述為：

式中，任意的 0s＞ 為尺度變換參數，ξ為頻率調制參數，u為時移參數。

令信號fH∈，為了盡可能逼近f，MP算法首先從過完備子庫中選擇最為匹配的一個原子0e，即滿足：

這樣，信號經過第一步分解，得到如下形式：

式中， R1f表示信號 f由原子 e0表示后，所產生的殘差(誤差)。顯然 e0和 R1f正交，因此，

為了使得逼近誤差的能量最小，必須選擇 e0使得最大。在無窮維或者高維的情況下，由于計算復雜度的限制，通常無法找到的最大值，只可能選擇在一定意義上的近似最佳原子 e0，使得

式中，0＜α＜1為優化因子。接下來，不斷地對產生的殘差進行與f同樣的分解操作。也就是MP過程是一個不斷地將殘差投影到原子庫中一個最匹配它的向量熵，從而繼續對它進行分解。假定將上述分解過程已經執行到了 n+1階，由于 en與 Rn+1f正交，那么

此時，信號f可以表示為以下求和形式：

類似的，能量可表示為：

1.2 GA算法的原理

遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。每個個體實際上是染色體帶有特征的實體。初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（Generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼，可以作為問題近似最優解。

遺傳算法作為一種高效并行的全局搜索方法，其一般步驟包括：

（1）創建一個隨機的初始狀態

初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代。

（2）評估適應度

對每一個解(染色體)指定一個適應度的值，根據問題求解的實際接近程度來指定(以便逼近求解問題的答案)。

（3）繁殖(包括子代突變)

帶有較高適應度值的那些染色體更可能產生后代(后代產生后也將發生突變)。后代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為“雜交”。

（4）下一代

如果新的一代包含一個解，能產生一個充分接近或等于期望答案的輸出，那么問題就已經解決了。如果情況并非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。

1.3 結合GA算法的MP算法

結合GA算法的MP算法執行步驟與MP算法基本一致，需要改變的是：將原子的參數組和信號或信號殘差與原子的內積的絕對值分別作為GA算法中的染色體和適應度函數，進而利用GA算法在過完備庫中尋找最佳匹配原子，該過程如圖1所示。

圖1 GA算法尋找最佳匹配原子程序流程

2 MP算法及其結合GA算法的仿真實例

文中全部仿真利用MATLAB實現。程序選取從較有代表性的原始圖像(如圖 2所示)中抽取出來的一維數據作為一維輸入信號。分別使用編寫的 MP算法代碼和GA-MP算法代碼進行30次分解（即將輸入信號分解為30個原子）的測試實驗，運行結果和分析討論如下（如圖3、圖4、圖5、圖6、圖7、圖8、圖9和圖10所示）。

圖2 原始圖像

圖6 和圖10分別是MP算法和GA-MP算法執行30次分解以后所得的最終結果。可見，兩種算法的重建信號較好地近似表示了輸入信號，且使用這兩種方法所重建的信號在直觀上相差無幾。

圖3 原始信號

圖5 MP分解后的殘差信號

圖4 MP算法選中的最優原子

圖6 重建信號

圖7 原始信號

圖9 GA-MP算法分解后的殘差信號

圖8 GA-MP算法選中的最優原子

圖10 重建信號

圖11 是兩種算法歷次分解所耗費的CPU時間比較圖。其中，橫坐標表示迭代次數，縱坐標表示CPU時間。圖11證明了結合GA算法的MP算法可以大大提高原始MP算法的計算速度，并且隨著分解次數的增加，GA-MP算法效率高的優點越明顯。因此，GA算法可以很好地消除MP算法在實際應用中的瓶頸之限。

圖11 兩種算法各次分解所耗費的CPU運行時間比較

3 結語

MP算法由于其具有原理簡單、便于編程等優點，已經成為目前最常用的信號稀疏分解和譜分解方法。但是，該算法通常需要很大的計算量，使得它在實際應用中對處理器等設備的要求非常高，而且無法對數據進行實時處理。文中介紹了用遺傳算法實現匹配追蹤分解的方法，通過仿真證明了這種方法可以搜索到最佳匹配信號結構的參數，并且計算時間有大幅的降低。目前，不少學者發展了很多遺傳算法的改進算法[7-9]，下一步的工作是結合改進遺傳算法實現MP算法來彌補遺傳算法易出現局部最優解的缺陷。

[1] MALLAT S,ZHANG Z.Matching Pursuits With Timefrequency Dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3377-3415.

[2] 范虹,孟慶豐.用混合編碼遺傳算法實現匹配追蹤算法[J].西安交通大學學報,2005,39(03):295-299.

[3] 高強,張發啟.遺傳算法降低匹配追蹤算法計算量的研究[J].振動、測試與診斷,2003,23(03):165-167.

[4] LIU Q, WANG Q, WU L. Dictionary with Tree Structure for Matching Pursuit Video Coding[J].Electronics Letters,2000,36(15):1266-1268.

[5] 高飛,玉振明.匹配追蹤分解算法的簡化實現[J].廣西大學梧州分校學報,2002,12(01):35-37.

[6] 陳國良,莊鎮泉.遺傳算法及其應用[M].北京:人民郵電出版社,1996.

[7] 邱柳欽.改進遺傳算法在MF-TDMA資源規劃中的研究[J].通信技術,2013,45(04):117-120.

[8] 余意,陳宇拓,李鍵紅.基于 TSP問題的混合遺傳算法研究[J].信息安全與通信保密,2009(03):101-103.

[9] 朱祥賢,潘汗懷,呂明.基于改進遺傳算法的傳感器非線性校正[J].通信技術,2009,42(03):156-158.