利用人工魚群算法實現基于ＭＰ的信號稀疏分解
2009-01-01 00:00:00舒維杰袁志剛尹忠科
計算機應用研究 2009年1期
(西南交通大學 信息科學與技術學院， 成都 610031)
摘 要：人工魚群算法（AFSA）是一種新的智能優化算法，具有魯棒性強、全局收斂性好，及對初值的不敏感性等特點。將人工魚群算法運用到信號的稀疏分解中，可快速尋找匹配追蹤(MP)過程中每一步分解的最佳原子。此方法提高了信號稀疏分解的速度，算法的有效性為實驗結果所證實。
關鍵詞：信號處理； 稀疏分解； 匹配追蹤； 人工魚群算法
中圖分類號：TN911.72 文獻標志碼：A
文章編號：10013695(2009)01006602
Signal MPbased sparse decomposition withartificial fishswarm algorithm
SHU Weijie， YUAN Zhigang， YIN Zhongke
(School of Information Science Technology， Southwest Jiaotong University， Chengdu 610031， China)
Abstract:Artificial fishswarm algorithm is a new kind of intelligence optimization algorithm. It has a strong robustness and good global astringency， and it is also proved to be insensitive to initial values. This paper applied the artificial fishswarm algorithm to signal sparse decomposition to fast search for approximately optimal atom at each step of matching pursuit. The method improves the speed of signal sparse decomposition and the validity of this algorithm is proved by experimental results.
Key words：signal processing; sparse decomposition; matching pursuit (MP); artificial fishswarm algorithm (AFSA)
Mallat等人[1]總結前人研究成果，于1993年提出了信號在過完備庫（overcomplete dictionary）上分解的思想。通過信號在過完備庫上的分解，用來表示信號的基可以自適應地根據信號本身的特點靈活選取。分解的結果將可以得到信號的一個非常簡潔的表達（即稀疏表示，sparse representation），而得到信號稀疏表示的過程稱為信號的稀疏分解。由于信號稀疏表示的優良特性，信號稀疏表示已經被應用到信號處理的許多方面，如信號去噪[1]、信號編碼[2]和識別[3]等。信號的稀疏分解在信號處理中的實際應用目前很難被推廣而實現產業化，阻礙信號稀疏分解研究及應用發展的關鍵因素之一是信號稀疏分解的計算量十分巨大，計算時間在現有條件下令人無法忍受。針對此問題，本文采用MP的方法進行信號的稀疏分解，在MP的每一步中利用人工魚群算法（AFSA）快速實現在過完備庫中選取最佳原子。利用提出的方法較好地解決了信號稀疏分解計算量大這一難題。
1 基于MP的信號稀疏分解
假設研究的信號為f，信號長度為N。若將信號分解在一組完備正交的基上，則這組基的數目應為N。由于基的正交性，基在由信號所組成的空間中的分布是稀疏的，從而信號的能量在分解以后將分散分布在不同的基上。這種能量分布的分散最后將導致用基的組合表示信號時表達的不簡潔性，即信號表示不是稀疏的。非稀疏的表示不利于某些方面的信號處理，如識別和壓縮等。為了得到信號的稀疏表示，基的構造必須使得基在信號組成的空間中足夠密。由此，基的正交性將不再被保證，所以此時的基也不再是真正意義上的基了，而改稱為原子。由這些原子組成的集合是過完備的，因而被稱為過完備庫（overcomplete dictionary of atoms）。信號在過完備庫上的分解結果一定是稀疏的[1]。
設D={gγ}γ∈Γ為用于進行信號稀疏分解的過完備庫，gγ為由參數組γ定義的原子。 用不同的方法構造原子，參數組γ所含有的參數及參數個數也不一樣。原子gγ的長度與信號本身長度相同，但原子應作歸一化處理，即‖gγ‖=1。Γ為參數組γ的集合。由庫的過完備性可知，參數組γ的個數應遠大于信號長度，即若用P表示過完備庫D={gγ}γ∈Γ中原子的個數，則P應遠大于信號長度N。MP方法分解信號過程如下[1]：
首先從過完備庫中選出與待分解信號最為匹配的原子gγ0，其滿足以下條件
｜〈f，gγ0〉｜=supγ∈Γ｜〈f，gγ〉｜
（1）
信號因此可以分解為在最佳原子gγ0上的分量和殘余兩部分，即為
f=〈f，gγ0〉gγ0+R1f（2）
其中：R1f是用最佳原子對原信號進行最佳匹配后的殘余。對最佳匹配后的殘余可以不斷進行上面同樣的分解過程，即
Rkf=〈Rkf，gγk〉gγk+Rk+1f（3）
其中gγk滿足：
｜〈Rkf，gγk〉｜=supγ∈Γ｜〈Rkf，gγ〉｜（4）
由式（2）（3）可知，經過n步分解后，信號被分解為
f=∑n-1k=0〈Rkf，gγk〉gγk+Rnf
（5）
其中：Rnf為原信號分解為n個原子的線性組合后，用這樣的線性組合表示信號所產生的誤差。由于每一步分解中所選取的最佳原子滿足式（4），分解的殘余Rnf隨著分解的進行迅速地減小。已經證明[1]，在信號滿足長度有限的條件下（對數字信號而言，這是完全可以而且一定滿足的），‖Rnf‖隨n的增大而指數衰減為0。信號可以分解為
f=∑∞k=0〈Rkf，gγk〉gγk
（6）
事實上，由于‖Rnf‖的衰減特性，一般而論，用少數的原子（與信號長度相比較而言）就可以表示信號的主要成分，即
f≈∑n-1k=0〈Rkf，gγk〉gγk
（7）
其中n< 基于MP的稀疏分解，算法易于理解，是目前信號稀疏分解的最常用方法。但與其他的信號稀疏分解方法一樣，其存在的關鍵問題是計算量十分巨大。在基于MP的信號稀疏分解中，每一步都要完成信號或信號分解的殘余在過完備庫中的每一個原子上的投影計算。按式（4）所要求，每一步分解實際上要進行的內積計算〈Rkf，gγ〉是一個在很高維（N維）空間的內積計算，而且要進行很多次（P次），這是MP信號稀疏分解計算量巨大的根本原因所在。式（4）所代表的問題，即MP每一步分解所需解決的問題，實際上是一個最優化問題，直接的求解方法是全局搜索，這將非常費時。對此問題，利用人工魚群算法可以很好地快速解決。 2 人工魚群算法 人工魚群算法[4，5]是一種新的智能優化算法——基于模擬魚群行為的隨機搜索優化算法，主要是利用了魚的覓食、聚群和追尾行為，從構造單條魚的底層行為做起，通過魚群中各個體的局部尋優，從而達到全局尋優的目的。 2.1 相關定義 人工魚個體的狀態可以表示為向量X=(x1，x2，…，xn)。其中xi(i=1，2，…，n)為欲尋優的變量。人工魚當前所在位置的食物濃度表示為Y=f(x)。其中Y為目標函數。人工魚個體之間的距離表示為di，j=‖Xi-Xj‖。Visual、step和δ分別表示人工魚的視野范圍、最大移動步長和擁擠度因子；try_number 表示人工魚每次覓食時最大的試探次數。 2.2 行為描述 1)覓食行為(prey) 設人工魚的當前狀態為Xi，在其視野范圍內(即di，j≤visual)隨機選擇一個狀態Xj。如果Yj＞Yi(以極大值尋優為例)，則向該方向前進一步；反之，再重新選擇狀態Xj，判斷是否滿足前進條件。反復 try_number 后，如果仍不滿足前進條件，則隨機移動一步，上面的過程可表示為 Xinext=Xi+random(step)(Xj-Xi)/di，j Yj＞Yi Xinext=Xi+random(step)else （8） 其中random(step)表示[0，step]間的隨機數。以下各式中的符號含義與此相同。 2)聚群行為(swarm) 設人工魚的當前狀態為Xi，探索其視野范圍內(即di，j≤visual)伙伴的數目nf。如果nf≠0，按式(9)探索可感知的伙伴的中心位置： Xc=∑nfi=1Xi/nf（9） 計算該中心位置的食物濃度Yc。如果Yc/nf＞δYi，表明伙伴中心附近有較多的食物并且不太擁擠，則執行式(10)；否則執行覓食行為。 Xinext=Xi+random(step)(Xc-Xi)/di，j Yj＞Yi（10） 如果nf=0也執行覓食行為。 3)追尾行為(follow) 設人工魚的當前狀態為Xi，探索其視野范圍內(即di，j≤visual)伙伴的數目nf。如果nf≠0，則探索當前可感知的伙伴中狀態最優的伙伴Xmax。如果Ymax/nf＞δYi，表明伙伴Xmax的附近有較多的食物并且不太擁擠，則執行式(11)；否則執行覓食行為。 Xinext=Xi+random(step)(Xmax-Xi)/di，j Yj＞Yi（11） 如果nf=0也執行覓食行為。 4)公告板 最優值的獲取方式采用跟蹤記錄最優個體狀態的方式，引入公告板用來記錄最優狀態。人工魚個體在尋優過程中，每次行動完畢都檢驗自身狀態與公告板的狀態，如果自身狀態優于公告板狀態，就將公告板的狀態改寫為自身狀態，使得公告板記錄下歷史最優的狀態。 2.3 行為選擇 根據所要解決問題的性質，對人工魚當前所處的環境進行評價，從而選擇一種合適的行為。一般情況下，可以應用進步最快的原則或進步即可的原則來選擇合適行為。 3 基于AFSA的信號MP稀疏分解 由于基于MP的信號稀疏分解的每一步， 實際上是解由式(4)所表示的最優化問題， 所以在過完備庫中選取最佳匹配原子的過程可轉換為利用人工魚群算法近似求函數最優化問題。其中，原子的參數組γ(s，u，v，w)作為待尋優參數，信號或信號殘余與原子的內積的絕對值｜〈Rkf，gγ〉｜作為目標函數。 在本文中首先隨機產生一組原子參數組作為人工魚群，然后分別模擬魚的覓食、聚群和追尾行為，用公告板來記錄人工魚的歷史最優狀態，其最后結果即為最優原子的參數組γ(s，u，v，w)，并把它作為MP問題每一步的最優解。 MP+AFSA的實現步驟如下： a)輸入人工魚群的群體規模N、最大迭代次數M、人工魚的可視域visual、人工魚的最大移動步長step、擁擠度因子δ。 b)設置初始迭代次數num=0，在控制變量可行域內隨機生成N個人工魚個體，形成初始魚群。 c)計算初始魚群各人工魚個體當前位置的食物濃度值Y=｜〈Rkf，gγ〉｜并比較大小，取Y為最大值者進入公告板，將此魚賦值給公告板。 d)各人工魚分別模擬追尾行為和聚群行為，選擇行動后Y值較大的行為實際執行，缺省行為方式為覓食行為。 e)各人工魚每行動一次后，檢驗自身的Y值與公告板的Y值。如果優于公告板，則以自身取代之。 f)中止條件判斷。判斷num是否已達到預置的最大迭代次數M，如果是，則輸出計算結果(即公告板的Y值)；否則num+=1，轉d)。 4 實驗結果與分析 實驗中采用長度為256、取值為[0，255]的實際信號，過完備庫中原子的構造方法依照文獻[3]的方法。當信號長度為256時，庫的大小含有126 490個原子，以滿足庫的過完備性。由于信號稀疏分解的速度依賴于計算條件(硬件條件和軟件條件)，給出實際的稀疏分解時間是沒有太大參考意義的（幾乎沒有文獻給出信號稀疏分解的計算時間）。把基于MP的信號稀疏分解的速度設為1，在表1中給出了本文算法的速度是基于MP信號稀疏分解的速度的倍數。 圖1中給出了實際的信號及利用不同方法稀疏分解為30個原子后重建的信號。可以看出，重建信號較好 地近似表示了原信號。本文所使用的方法由于基于人工魚群算法，而此方法作為一種智能優化算法，所求結果實際具有一定的隨機性，重建信號不穩定，質量稍差一些。基于全局搜索的MP稀疏分解重建信號較本文方法重建的信號更接近于原始信號，但兩種方法重建的信號差別很微小，對稀疏分解結果的實際應用沒有影響。 表1 信號稀疏分解相對速度比較 算法計算速度/倍 基于MP的信號稀疏分解1 MP+AFSA的信號稀疏分解78* *注：由于智能算法本身的隨機性，這里的倍數為平均值。 5 結束語 基于 MP 的信號稀疏分解的每一步實驗中用30個原子即可表示原始信號，也足以說明這種表示的稀疏性。同時，用30個原子即可表示原信號主要特征，表明這種稀疏表示為進行信號處理（如壓縮、識別等）提供了極其有利的條件。本文利用人工魚群算法在重建信號的速度上比MP算法有了很大的提高，為解決信號稀疏分解計算量大這一難題提供了新的思路，但在重建信號的質量上還有待改進。 參考文獻： ［1］MALLAT S，ZHANG Zhifeng. Matching pursuit with timefrequency dictionaries[J]. IEEE Trans on Signal Processing，1993，41(12):33973415. [2]張文耀.基于匹配跟蹤的低位率語音編碼研究[D].北京：中國科學院研究生院（軟件研究所），2002. [3]ARTHUR P L，PHILIPOS C L．Voiced/unvoiced speech discrimination in noise using Gabor atomic decomposition[C]//Proc ofIEEE International Conference on Acoustics，Speech， and Signal Processing. 2003:820828. [4]李曉磊，邵之江，錢積新. 一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，2002，22(11):3238. [5]李曉磊，錢積新. 基于分解協調的人工魚群優化算法研究[J].電路與系統學報，2003，8(1):16.
