基于魚群算法的獨立成分分析算法研究

張玉潔，李志明，宋廣宇，凌加浠

中國地質(zhì)大學 數(shù)理學院，武漢 430074

基于魚群算法的獨立成分分析算法研究

張玉潔，李志明，宋廣宇，凌加浠

中國地質(zhì)大學 數(shù)理學院，武漢 430074

1 引言

人工魚群算法[1]（AFSA）是由李曉磊等人基于動物行為具有盲目性、自治性、突現(xiàn)性、并行性和適應性等特點，提出的一種群體智能優(yōu)化算法。主要利用了魚的聚群、追尾、隨機和覓食行為，從單條人工魚的行為開始進行研究，通過魚群中每個個體在搜索空間中尋找食物所處的地方后，共享搜索結(jié)果，從而群體在整個搜索域中判斷全局最優(yōu)的過程。該算法收斂速度較快，對初值的選擇不敏感，簡單易操作，且具有避免陷入局部極值的良好能力。

獨立成分分析（ICA）是在源信號和傳輸通道先驗知識甚少的情況下，根據(jù)源信號的統(tǒng)計獨立性，僅由觀測信號推斷出各個獨立的源信號及傳輸通道的過程。ICA是20世紀90年代后期發(fā)展起來的一種新的信號處理的方法，由Herault和Jutten開創(chuàng)[2]。目前對ICA問題的研究已經(jīng)涉及到信號處理、神經(jīng)網(wǎng)絡、人工智能、醫(yī)學分析、圖像處理等領(lǐng)域[3]。

ICA從提出到現(xiàn)在僅有二十幾年的時間，卻得到非常快的發(fā)展，各種算法紛紛涌現(xiàn)。ICA的算法基本形式可歸結(jié)如下：

ICA算法=目標函數(shù)+優(yōu)化算法

也即，圍繞源信號的先驗知識（如統(tǒng)計獨立性）提出各種判斷準則，構(gòu)造一個以W為自變量的目標函數(shù)J(W)，然后結(jié)合各種優(yōu)化算法來尋找分離矩陣W。如極大似然方法[4]、非線性PCA方法[5]、Infomax方法[6]、FastICA方法[7-8]、自然梯度方法[9-11]等。

本文首次將AFSA這種優(yōu)化算法應用于ICA，該方法以負熵極大化為優(yōu)化目標，利用人工魚群在整個分離矩陣空間中的聚群、追尾、覓食和隨機移動等行為達到搜索最佳分離矩陣的目的。

2 線性ICA問題的描述

假設瞬時線性ICA模型[2]：

其中Z(t)=(z1(t)，z2(t)，…，zM(t))T是M維觀測信號，S(t)= (s1(t)，s2(t)，…，sM(t))T是M維未知的、零均值的、相互獨立的源信號，且si(t)，i=1，2，…，M中至多只有一個高斯信號。A∈RM×M是一個未知的列滿秩的常數(shù)矩陣。

ICA的目的就是通過觀測信號Z(t)尋找M×M分離矩陣W，再由分離矩陣和觀測信號恢復出相互獨立的源信號S(t)：

在不考慮排列順序和幅度[2]前提下，Y(t)=(y1(t),y2(t),…,yN(t))T為S(t)的估計。

3 AFSA簡介

人工魚模型包括兩個方面：變量和魚群行為函數(shù)。在一個n維的空間中，有L條人工魚組成一個群體，向量X=(x1，x2，…，xn)表示當前狀態(tài)下的人工魚，其中xi(i=1，2，…，n)為尋優(yōu)參數(shù)；Φ=f(X)為人工魚在位置X時對應的的食物濃度；Step表示移動步長；Visual為人工魚的視野范圍；表示第i和第j個人工魚個體之間的距離；δ為擁擠因子；Trynumber表示人工魚在每次迭代中的最大試探次數(shù)。

AFSA首先初始化一群人工魚，通過不斷的迭代，搜索最優(yōu)解。在每次迭代過程中，人工魚通過隨機移動、覓食、聚群及追尾等行為來自我更新，具體過程如下所示。

（1）隨機行為：魚在其視野內(nèi)隨機地尋找食物。

（2）公告板：記錄當次迭代中最優(yōu)人工魚所處位置Xbest及對應的食物濃度Φbest。每個人工魚在移動的過程中，完成一次迭代后，就將自身所處地方的食物濃度與公告板中記錄進行比較，如果優(yōu)于公告板記錄，則用自身所處位置及食物濃度更新公告板中的記錄，否則，公告板不變。當整個算法的迭代結(jié)束后，最優(yōu)值即是公告板上的結(jié)果。

（3）覓食行為[12]：隨機移動的魚主要向著食物多的方向移動。人工魚當前位置Xi，在其視野范圍內(nèi)隨機選擇一個位置Xj：

其中i，j=1，2，…，n，rand為[0，1]之間的隨機數(shù)。分別計算并比較Xi與Xj所對應的Φi與Φj，如果，Φj＞Φi，則Xi直接移動到Xj，反之，重新按式（3）隨機選擇Xj，判斷是否滿足前述的條件，反復嘗試Trynumber次之后，如果仍不滿足，則Xi按式（4）隨機移動一步。

（4）聚群行為[1]：大量的魚在游動過程中都會自然地聚集成群進行集體活動，同時避免過度擁擠。人工魚當前位置為Xi，搜索目前鄰域內(nèi)dij＜Visable的伙伴數(shù)目nf，并計算中心位置-X，若-X所對應的函數(shù)值-Φ滿足-Φ/nf＞δΦi且Φi＜-Φ，表示伙伴中心位置較優(yōu)，食物濃度高，則Xi按式（5）移動一步，否則進行覓食。

（5）追尾行為[1]：當某條魚發(fā)現(xiàn)食物時，附近的魚會尾隨而來，從而導致更遠地方的魚也跟過來。設人工魚當前位置為Xi，搜索當前視野范圍內(nèi)對應函數(shù)值最優(yōu)的伙伴Xb，如果最優(yōu)值Φb滿足Φb/nf＞δΦi且Φi＜Φb，則表明Xb的周圍不太擁擠，Xi按（6）移動一步，否則進行覓食。

本文研究的是函數(shù)最大值的問題，先進行聚群、追尾等行為（也可先執(zhí)行追尾行為，再執(zhí)行聚群行為等），然后比較這些行為后每個個體所對應的函數(shù)值，選擇函數(shù)值最大者對應的行為來執(zhí)行。最終，大量人工魚會聚集最優(yōu)值的極值區(qū)域周圍，從而達到搜索全局最值的目的。

4 基于AFSA的ICA算法

利用源信號之間的獨立性，許多學者提出了不同的目標函數(shù)。本文采用負熵極大化作為評價準則[13]。

負熵的定義：

其中，pG(Y)與p(Y)表示具有相同均值和協(xié)方差矩陣的高斯密度函數(shù)。

目標函數(shù)為：

然而直接按式（7）估計負熵需要先估計概率密度函數(shù)，數(shù)值計算既繁瑣又不穩(wěn)健。文獻[13]提出用Edgeworth展開逼近yi的概率密度函數(shù)，則目標函數(shù)化為：

其中，κ3(i)=m3(i)，κ4(i)=m4(i)-3，mk(i)=E[(yi)k]。通過最大化式（9）得到分離矩陣W，進而得到源信號的估計。

為了簡化計算，提高算法的精確度，一般在進行分離之前需要先對觀測信號進行預處理。白化是一種常用的預處理方法[3]，即對混合信號Z做線性變換Ω(t)=VZ(t)，使得變換后的新信號Ω(t)的各個成分之間互不相關(guān)，具體作法為：對數(shù)據(jù)Z的協(xié)方差矩陣RZ=E{ZZT}進行特征值分解，U為以RZ的特征向量為列構(gòu)成的矩陣，D是以RZ的特征值為對角元素的對角矩陣，則V=D-1/2UT。

由魚群算法來確定分離矩陣W主要分為以下幾步：

（1）白化觀測信號Z得到Ω，使其滿足E{ΩΩT}=I。

（2）初始化魚群算法參數(shù)和人工魚狀態(tài)。

（3）按式（9）計算每條人工魚所對應的負熵，并更新公告板。

（4）每條人工魚按一定的條件執(zhí)行覓食、聚群、追尾行為，并更新自己的狀態(tài)。

（5）判斷是否達到最大迭代次數(shù)，若達到最大迭代次數(shù)則執(zhí)行步驟（6）；否則執(zhí)行步驟（3）。

（6）選取全局最優(yōu)位置構(gòu)成分離矩陣W，Y=WZ則是源信號的估計。

5 模擬實驗

為了驗證算法的有效性，對以下信號進行計算機仿真實驗。源信號為：

仿真實驗中隨機選取混合矩陣，樣本點數(shù)N=5 000，人工魚規(guī)模L=20，重復嘗試次數(shù)Trynumber=10，Visual=0.25，Step=0.05，迭代次數(shù)為100，進行了50次Monte Carlo實驗。圖1給出了源信號與分離信號的波形圖，其中橫坐標表示樣本點個數(shù)（選擇前800個數(shù)據(jù)點），縱坐標是樣本的幅度。從圖中可以清楚看出除了在順序和幅度上有一些差別外，分離后的信號在波形上與源信號保持了很好的一致性，混合信號得到了較好的分離。

圖2給出了目標函數(shù)J全局平均最大值的進化曲線。從中可以看出隨著人工魚群的移動，目標函數(shù)不斷優(yōu)化，負熵在不斷增加。在30次后就基本保持不變，迭代可以停止，此時函數(shù)值所對應的人工魚所處位置即為分離矩陣的估計。

圖2 函數(shù)J全局平均最大值的進化曲線

為了進一步描述算法的有效性，本文采用分離信號與源信號之間的信噪比作為性能指標[14]：

其中，yi是si對應的分離信號。50次Monte Carlo實驗的平均信噪比結(jié)果為[33.767 5，31.425 2]。

最后將魚群算法與自然梯度法進行盲源分離進行比較，其結(jié)果如表1。

表1 魚群算法與自然梯度法進行盲源分離的比較

從表1中可以看出，魚群算法用于盲源分離與自然梯度法相比較，其算法精度更高，且收斂速度更快。主要原因在于自然梯度法是一個局部最優(yōu)算法，有可能取得局部極值，導致算法失敗。并且當源信號幅度隨時間快速變化時，會使自然梯度算法數(shù)值上不穩(wěn)定。

6 結(jié)論

本文首次將魚群算法引入到獨立成分分析中，提出了一種基于人工魚群優(yōu)化的獨立成分分析算法。用Edgeworth展開式得到基于負熵的目標函數(shù)，通過人工魚尋優(yōu)，得到全局最優(yōu)解。計算機仿真實驗驗證了算法的有效性。人工魚群算法目前還處于起步階段，算法還不完善，在實驗中發(fā)現(xiàn)視野與步長對算法的各種行為和收斂性能有較大影響，下一步將考慮自適應調(diào)整步長與視野的人工魚群算法，并將其應用于ICA中，以期獲得更為理想的效果。

[1]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐，2002，22（11）：32-38．

[2]Herault J，Jutten C.Blind separation of sources，Part I：an adaptive algorithm based on neuromimetic architecture[J].Signal Processing，1991，24（1）：1-10.

[3]Hyvarinen A，Oja E.Independent component analysis：algorithms and applications[J].Neural Networks，2000，13（4/5）：411-430.

[4]Pearlmutter B，Parra L.A context-sensitive generalization of ICA[C]//ProceedingsoftheInternationalConferenceon Neural Information Processing，1996：151-157.

[5]Oja E.The nonlinear PCA learning rule in independent component analysis[J].Neural Computing，1997，17（1）：25-45.

[6]Park H，Oh S，Lee S.A modified infomax algorithm for blind signal separation[J].Neurocomputing，2006，70（1/3）：229-240.

[7]Zhu X，Ye J，Zhang X.A fixed-point nonlinear PCA algorithm for blind source separation[J].Neurocomputing，2005，69（1/3）：264-272.

[8]Hyvarinen A，Oja E.Simple neuron models for independent component analysis[J].Neural Computation，2000，7（6）：671-687.

[9]Amari S.Natural gradient works efficiently in learning[J].Neural Computation，1998，10（2）：251-276.

[10]Amari S，Chen T，Cichocki A.Stability analysis of adaptive blind source separation[J].Neural Networks，1997，10（8）：1345-1351.

[11]Amari S，Cardoso J F.Blind source separation—Semiparametric statistical approach[J].IEEE Trans on Signal Processing，1997，45（11）：2692-2700.

[12]王聯(lián)國，洪毅，施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學報，2009，21（23）：7483-7502.

[13]Girolami M.An alternative perspective on adaptive independent component analysis algorithm[J].Neural Computation，1998，10（8）：2103-2114.

[14]Lee T W，Girolami M，Bell A J，et al.A unifying information theoretical framework for independent component analysis[J]. Computers and Mathematics with Application，2000，31（11）：1-21.

ZHANG Yujie,LI Zhiming,SONG Guangyu,LING Jiaxi

School of Mathematics and Physics,China University of Geosciences,Wuhan 430074,China

Independent Component Analysis（ICA）which requires a little prior knowledge（such as independent）of signals is widely applied.The goal of ICA is to find a separation matrix so that each component of the output signal by transforming is independent.The key of ICA is to construct a target function,and then obtain the separation matrix by maximize（or minimize）the target function.This paper proposes an ICA algorithm based on Artificial Fish Swarm Algorithm（AFSA）.With the target function of maximum negentropy,it can obtain the separation matrix through foraging,cluster and tracing behavior of artificial fishes and updating artificial fish position.Compare with natural gradient,AFSA has the high accuracy and fast convergence rate.Experimental results are provided to evaluate the performance of the proposed algorithm.

Artificial Fish Swarm Algorithm（AFSA）;Independent Component Analysis（ICA）;negentropy

獨立成分分析（ICA）只需要知道源信號較少的先驗知識（如統(tǒng)計獨立性等），僅由觀測信號便能恢復出源信號的特性，因而得到了廣泛應用。ICA的目的是尋找變換矩陣，使輸出信號經(jīng)變換后各成分之間盡可能的統(tǒng)計獨立，其關(guān)鍵是建立一個目標函數(shù)，使得最大化（或最小化）目標函數(shù)的解便是所要找的變換矩陣。首次將人工魚群算法（AFSA）與ICA相結(jié)合，提出了基于AFSA的獨立成分分析算法。以負熵極大化作為目標函數(shù)，通過人工魚的覓食，聚群和追尾行為，更新人工魚的位置，得到全局最優(yōu)解，從而得到分離矩陣。與自然梯度法相比，魚群算法精度更高，收斂速度更快，仿真實驗表明了將魚群算法應用于獨立成分分析的可行性和有效性。

人工魚群算法；獨立成分分析；負熵

A

TN911.72

10.3778/j.issn.1002-8331.1110-0594

ZHANG Yujie,LI Zhiming,SONG Guangyu,et al.New independent component analysis method based on fish swarm algorithm.Computer Engineering and Applications,2013,49（13）：187-190.

國家自然科學基金（No.11026145，No.61102103，No.61071188）；湖北省自然科學基金（No.2010CDB04205，No.2009CDB077）；中央高校基本科研業(yè)務費專項資金（No.CUGL090252，No.CUG090112，No.CCNU10A01013）。

張玉潔（1981—），女，博士，講師，主要研究方向為時頻分析和信號處理；李志明，男，博士，講師；宋廣宇，男，碩士研究生；凌加浠，男，碩士研究生。E-mail：zhangyujie@cug.edu.cn

2011-11-03

2012-01-18

1002-8331（2013）13-0187-04

CNKI出版日期：2012-03-21http://www.cnki.net/kcms/detail/11.2127.TP.20120321.1735.049.html