基于魚群算法的獨(dú)立成分分析算法研究

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

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

基于魚群算法的獨(dú)立成分分析算法研究

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

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

1 引言

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

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

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

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

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

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

2 線性ICA問(wèn)題的描述

假設(shè)瞬時(shí)線性ICA模型[2]：

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

ICA的目的就是通過(guò)觀測(cè)信號(hào)Z(t)尋找M×M分離矩陣W，再由分離矩陣和觀測(cè)信號(hào)恢復(fù)出相互獨(dú)立的源信號(hào)S(t)：

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

3 AFSA簡(jiǎn)介

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

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

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

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

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

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

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

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

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

4 基于AFSA的ICA算法

利用源信號(hào)之間的獨(dú)立性，許多學(xué)者提出了不同的目標(biāo)函數(shù)。本文采用負(fù)熵極大化作為評(píng)價(jià)準(zhǔn)則[13]。

負(fù)熵的定義：

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

目標(biāo)函數(shù)為：

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

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

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

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

（1）白化觀測(cè)信號(hào)Z得到Ω，使其滿足E{ΩΩT}=I。

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

（3）按式（9）計(jì)算每條人工魚所對(duì)應(yīng)的負(fù)熵，并更新公告板。

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

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

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

5 模擬實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，對(duì)以下信號(hào)進(jìn)行計(jì)算機(jī)仿真實(shí)驗(yàn)。源信號(hào)為：

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

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

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

為了進(jìn)一步描述算法的有效性，本文采用分離信號(hào)與源信號(hào)之間的信噪比作為性能指標(biāo)[14]：

其中，yi是si對(duì)應(yīng)的分離信號(hào)。50次Monte Carlo實(shí)驗(yàn)的平均信噪比結(jié)果為[33.767 5，31.425 2]。

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

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

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

6 結(jié)論

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

[1]李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐，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)國(guó)，洪毅，施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學(xué)報(bào)，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

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

人工魚群算法；獨(dú)立成分分析；負(fù)熵

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.

國(guó)家自然科學(xué)基金（No.11026145，No.61102103，No.61071188）；湖北省自然科學(xué)基金（No.2010CDB04205，No.2009CDB077）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金（No.CUGL090252，No.CUG090112，No.CCNU10A01013）。

張玉潔（1981—），女，博士，講師，主要研究方向?yàn)闀r(shí)頻分析和信號(hào)處理；李志明，男，博士，講師；宋廣宇，男，碩士研究生；凌加浠，男，碩士研究生。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