基于蟻群算法的改進(jìn)ICA算法

鄧均明，吳法文，陳西宏，徐宇亮

(空軍工程大學(xué)導(dǎo)彈學(xué)院，陜西 三原 713800)

0 引言

獨立分量分析［1］是近年來從盲源分離(Blind Source Separation，BSS)發(fā)展起來的一種新的信號分析與處理方法。這種方法通過計算分離變量非高斯性大小，判斷分離變量是否相互獨立。典型的算法有擴(kuò)展Infomax算法、FastICA算法等［2］。這些算法對隱含在數(shù)據(jù)中的獨立分量的提取都具有很好的效果。但是，這些算法普遍存在一個問題，就是目標(biāo)函數(shù)中非線性函數(shù)選取的好壞對分離結(jié)果有很大影響。蟻群算法由意大利學(xué)者Colorni A，Dorigo M和Maniezzo V于1992年首先提出來。這種算法對復(fù)雜的優(yōu)化問題具有很強的解決能力，對問題定義要求相對較低，發(fā)現(xiàn)較好解的能力很強，穩(wěn)健性好，易于計算機實現(xiàn)且易于與其他算法結(jié)合［3－4］。所以，針對獨立分量分析典型算法存在依賴非線性函數(shù)選取的缺陷，本文提出了一種應(yīng)用蟻群算法對其目標(biāo)函數(shù)進(jìn)行優(yōu)化的方法。通過仿真實驗及結(jié)果比較，驗證了基于蟻群算法的改進(jìn)ICA的有效性和優(yōu)越性。

1 獨立分量分析的基本原理

標(biāo)準(zhǔn)獨立分量分析的基本原理如圖1所示。s為源信號，A為混合矩陣，將s中的各個分量進(jìn)行混合，x是測得的混合信號，B是獨立分量分析算法中的分離矩陣，y是對x經(jīng)過獨立分量分析所分離的獨立信號。寫成數(shù)學(xué)表達(dá)式即為:x=As，y=Bx。ICA所解決的主要問題就是在源信號s和混合矩陣A未知的情況下，僅根據(jù)測得的混合信號x，求出一個分離矩陣B，使x經(jīng)過分離后所得輸出y是s的最優(yōu)估計。因此，獨立分量分析實質(zhì)上是一個優(yōu)化問題，即根據(jù)一個判斷獨立性最優(yōu)的判據(jù)尋找B，使y中各分量盡可能地相互獨立。所以，ICA的問題包括2個部分，首先是選擇一個判斷分離的信號是否相互獨立的判據(jù)，其次是采用一定的算法來實現(xiàn)這個目標(biāo)。判斷獨立性最優(yōu)的判據(jù)有很多種，其中主要有互信息極小化判據(jù)、信息極大化判據(jù)、極大似然判據(jù)、直接用高階統(tǒng)計量作獨立性判據(jù)、負(fù)熵最大化判據(jù)等［5－6］。

圖1 ICA基本原理圖

2 FastICA算法

FastICA算法是由芬蘭學(xué)者Hyvarinen等人首先提出，由于這種算法具有收斂速度快、收斂有保證、簡單方便等優(yōu)點而被廣泛應(yīng)用。在這種算法中，又以采用負(fù)熵作為衡量分量獨立性判據(jù)最為常用。

2.1 FastICA預(yù)處理

為了方便后續(xù)獨立分量的提取過程，提高算法的收斂性，簡化算法的計算，在運行FastICA算法之前，需要對測試信號進(jìn)行預(yù)處理，即去均值和白化過程。去均值是使觀測信號成為零均值變量，以簡化ICA算法。其處理過程可通過式(1)來實現(xiàn)

對測試信號進(jìn)行白化處理，就是使白化后的分量不相關(guān)，且方差為1。信號經(jīng)過白化處理后，使得ICA算法收斂更快，并能獲得更好的穩(wěn)定性和減少需要估計的參數(shù)個數(shù)。對測試信號進(jìn)行白化處理，即尋找一個變換矩陣W，對測試到的信號x進(jìn)行線性變換，表達(dá)式如

經(jīng)過變換后的信號z要滿足其協(xié)方差矩陣E{zzT}等于1。變換矩陣W可以通過對混合信號x的協(xié)方差進(jìn)行特征值分解來得到。

2.2 基于負(fù)熵的Fast ICA算法

根據(jù)中心極限定理，獨立隨機變量分量的和比原來隨機變量中的任何一個分量更接近于服從高斯分布，只要各獨立的隨機分量具有有限的均值和方差，不論為何種分布，該隨機分量之和都近似服從高斯分布。因此，可以在分離過程中測量分離量的非高斯性，非高斯性越大的信號分離得越完全。

由信息論理論可知:在所有等方差的隨機變量中，高斯分布的隨機變量具有最大的信息熵，因而可以利用熵來度量非高斯性大小。設(shè)隨機變量y的密度函數(shù)為Py(x)，熵的定義為

為了獲得非高斯性的一個非負(fù)數(shù)度量，常采用熵的修正形式——負(fù)熵。把任意概率密度函數(shù)和具有相同協(xié)方差陣的高斯分布隨機變量間的散度作為該函數(shù)的非高斯程度度量，稱為負(fù)熵，用公式表示為

式中:ygauss為與y具有相同方差的高斯分布隨機變量。當(dāng)y的非高斯性越強，J(y)的值就越大，所以J(y)可以作為非高斯性的測度。但在計算時需要知道y的概率密度，這在實際中是很難辦到的。為此，Hyvarinen A提出了一種如下式的近似負(fù)熵的方法來進(jìn)行非高斯性度量

式中:E{}為期望;G{}為非線性函數(shù)。將y=bTx代入式(5)，并對其進(jìn)行一系列處理，由于x經(jīng)過白化后變成z，所以最后得到該算法的迭代公式

式中:g()為G()的導(dǎo)數(shù)。FastICA算法的優(yōu)點在于:采用牛頓法，收斂性好，而且迭代過程中無須引入調(diào)節(jié)步長等人為設(shè)置的參數(shù)。但是，F(xiàn)astICA算法存在著依賴于非線性函數(shù)選取的問題，分離效果很大程度上取決于非線性函數(shù)G{}的選取是否恰當(dāng)。然而在實際應(yīng)用中，源信號的性質(zhì)在信號被分離前是無從得知的，選擇一個恰當(dāng)?shù)姆蔷€性函數(shù)比較困難。為了降低分離效果對非線性函數(shù)選取的依賴性，引入對函數(shù)沒有特殊要求的蟻群算法，替代牛頓法，以式(5)為目標(biāo)函數(shù)，對其進(jìn)行優(yōu)化求解。

3 基于蟻群算法的改進(jìn)ICA

20世紀(jì)50年代中期，人們從生物進(jìn)化的機理中受到啟發(fā)，提出了許多用來解決復(fù)雜優(yōu)化問題的新方法。其中，蟻群算法就是對螞蟻群落食物采集過程的模擬［7］。該方法已經(jīng)用來求解TSP問題、指派問題、車間調(diào)度問題等，并取得了一系列較好的實驗結(jié)果。相比于基于梯度應(yīng)用的優(yōu)化算法，蟻群算法對非線性目標(biāo)函數(shù)沒有特殊要求，易與其他算法結(jié)合，穩(wěn)健性強且易于并行實現(xiàn)

3.1 改進(jìn)ICA的算法分析

3.1.1 確定目標(biāo)函數(shù)

以負(fù)熵的近似表達(dá)式(5)式為目標(biāo)函數(shù)。由于ygauss是與y具有相同均值和協(xié)方差矩陣的高斯變量，這項可以忽略不計，式(5)的優(yōu)化問題可以轉(zhuǎn)化對E{G(y)}進(jìn)行優(yōu)化。將經(jīng)過預(yù)處理的y=bTz帶入其中，最終的目標(biāo)函數(shù)為E{G(bT·z)}。由y=Bx可知，分離信號間的獨立性不受分離矩陣B中各行元素的大小、行向量的次序符號的影響。因此，可以將分離矩陣各元素的取值范圍限定在［－1，1］間。

3.1.2 優(yōu)化目標(biāo)函數(shù)

蟻群算法是通過路徑上留下的信息素和城市距離來尋找最優(yōu)路徑。在離散空間中，蟻群算法的信息留存、增減和最優(yōu)解的選取，都是以離散的點狀分布求解方式進(jìn)行。而在連續(xù)空間中的尋優(yōu)問題求解中，則以區(qū)域性方式表示。每個區(qū)域內(nèi)螞蟻的信息量分布函數(shù)對整個解空間所在區(qū)域皆有影響，影響程度隨其距離的增加而遞減。為了避免產(chǎn)生由初始分布不均造成早熟停滯的現(xiàn)象，將蟻群在解空間內(nèi)作均勻分布。蟻群向各單蟻所在子區(qū)域總信息量最大的方向運動。

把分離矩陣B的元素b看成螞蟻，在解空間內(nèi)作初始分布。將b在［－1，1］范圍內(nèi)分成N等份，在N個子區(qū)間的中部各放置一個單蟻，每個單蟻擁有隨自己位置變化的移動子區(qū)間。螞蟻從第i個區(qū)域轉(zhuǎn)移到第j個區(qū)域的概率Pij為

式中:τij為第j個區(qū)域的吸引強度;?ij為第i區(qū)域與j區(qū)域目標(biāo)函數(shù)的差值;α，β分別表達(dá)τij和?ij的重要性，為非負(fù)數(shù);ρ表示強度的持久性系數(shù)，一般取0.5～0.9;Q為一正常數(shù);f為目標(biāo)函數(shù)值。

通過螞蟻的轉(zhuǎn)移，求取各區(qū)域的目標(biāo)函數(shù)值，比較其大小，從中選取最優(yōu)的作為一次迭代結(jié)果，并帶入更新方程和轉(zhuǎn)移概率方程。當(dāng)所有螞蟻選擇完一遍后，在求出的最優(yōu)區(qū)域附近重新定義解空間，縮小取值范圍，并重復(fù)上面的計算并比較，直至預(yù)先給定的精度。

3.2 改進(jìn)ICA的算法步驟

采用基于蟻群算法的改進(jìn)ICA算法步驟如下:

1)對混合信號進(jìn)行預(yù)處理，去均值和白化，得到z;

2)確定目標(biāo)函數(shù);

3)估計b的取值范圍:這里b值范圍是－1≤b≤1;

4)在定義域內(nèi)將b分成N等份，將所有螞蟻在解空間內(nèi)作均勻分布;

5)初始化迭代次數(shù)Nc，給τij賦值，給出ρ，Q的值;

6)對每只螞蟻按轉(zhuǎn)移概率Pij進(jìn)行轉(zhuǎn)移，并計算目標(biāo)函數(shù)值，選取最優(yōu)解;

7)按更新方程修改吸引強度，即Nc←Nc+1;

8)若迭代次數(shù)Nc小于規(guī)定的最大循環(huán)次數(shù)，轉(zhuǎn)向步驟6)，否則縮小變量的取值范圍，轉(zhuǎn)步驟4)。

4 仿真及結(jié)果分析

為了驗證改進(jìn)ICA算法的有效性以及相比FastICA算法的優(yōu)越性，嘗試了多個非線性函數(shù)對其進(jìn)行仿真。下面的例子為分離效果差距最明顯的一個。

選取3個獨立信號:正弦波、方波和白噪聲，如圖2所示。

將源信號經(jīng)過混合矩陣A混合，混合后的信號波形圖如圖3所示。

首先，采用基于蟻群算法的改進(jìn)ICA算法對混合信號進(jìn)行分離。取 Q=100，ρ=0.7，N=20，Nc=50 分離后的信號波形如圖4所示。

選取同一非線性函數(shù)，再采用FastICA算法對混合信號進(jìn)行分離，圖5為對應(yīng)的分離信號波形。

圖2 3個源信號波形圖

圖3 混合后的信號波形圖

圖4 改進(jìn)ICA算法的分離信號波形圖

圖5 FastICA算法的分離信號波形圖

由于獨立分量分析存在不確定性，兩種算法的分離信號的順序和幅度都有所改變。對兩種分離信號波形圖進(jìn)行比較，可以看出，基于蟻群算法的改進(jìn)ICA其分離效果明顯優(yōu)于FastICA算法的分離效果。

5 小結(jié)

介紹了獨立分量分析的基本原理和典型算法FastICA算法。針對FastICA算法的缺點，提出了一種基于蟻群算法的改進(jìn)ICA算法，以降低對目標(biāo)函數(shù)中非線性函數(shù)選取的依賴性，提高分離效果的可靠性。用仿真信號的分離實驗對改進(jìn)ICA算法的可行性和有效性進(jìn)行了驗證，下一步將研究獨立分量分析在測試信號處理中的應(yīng)用。

［1］ROBERTS S，EVERSON R.Independent component analysis:principles and practice［M］.Cambridge，UK:Gambridge University Press，2001.

［2］葉婭蘭.獨立分量分析算法及其在生物醫(yī)學(xué)中的應(yīng)用研究［D］.成都:電子科技大學(xué)，2008.

［3］DORIGO M，MANIEZZO V，COLORNY A.The ant system:optimization by a colony of coorperating agents［J］.IEEE Transactions on SMC，1996，26(1):29－41.

［4］柴井坤，魏圓圓，曲立國.基于改進(jìn)蟻群算法的組播路由算法研究［J］.電視技術(shù)，2009，33(4):57－59.

［5］楊福生，洪波.獨立分量分析的原理與應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

［6］HYVARINEN A，OJA E.Independent component analysis:algorithms and applications［J］.Neural Networks，2000，13(4－5):411－430.

［7］高尚，楊靜宇.群智能算法及其應(yīng)用［M］.北京:中國水利水電出版社，2006.