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

高麗貞

0 引言

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

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

1 算法的原理及其實現(xiàn)步驟

1.1 MP算法的原理

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

式中，f(t)表示信號，hn(t)表示信號的基函數(shù)，an表示基對應(yīng)的系數(shù)。即，信號被分解為加權(quán)的基函數(shù)的迭加形式。

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

式中，任意的 0s＞ 為尺度變換參數(shù)，ξ為頻率調(diào)制參數(shù)，u為時移參數(shù)。

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

這樣，信號經(jīng)過第一步分解，得到如下形式：

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

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

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

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

類似的，能量可表示為：

1.2 GA算法的原理

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

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

（1）創(chuàng)建一個隨機(jī)的初始狀態(tài)

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

（2）評估適應(yīng)度

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

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

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

（4）下一代

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

1.3 結(jié)合GA算法的MP算法

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

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

2 MP算法及其結(jié)合GA算法的仿真實例

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

圖2 原始圖像

圖6 和圖10分別是MP算法和GA-MP算法執(zhí)行30次分解以后所得的最終結(jié)果?？梢姡瑑煞N算法的重建信號較好地近似表示了輸入信號，且使用這兩種方法所重建的信號在直觀上相差無幾。

圖3 原始信號

圖5 MP分解后的殘差信號

圖4 MP算法選中的最優(yōu)原子

圖6 重建信號

圖7 原始信號

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

圖8 GA-MP算法選中的最優(yōu)原子

圖10 重建信號

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

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

3 結(jié)語

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

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

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

[3] 高強(qiáng),張發(fā)啟.遺傳算法降低匹配追蹤算法計算量的研究[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] 高飛,玉振明.匹配追蹤分解算法的簡化實現(xiàn)[J].廣西大學(xué)梧州分校學(xué)報,2002,12(01):35-37.

[6] 陳國良,莊鎮(zhèn)泉.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996.

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

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

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