基于蟻群算法的改進ICA算法

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

(空軍工程大學導彈學院，陜西 三原 713800)

0 引言

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

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

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

圖1 ICA基本原理圖

2 FastICA算法

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

2.1 FastICA預處理

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

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

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

2.2 基于負熵的Fast ICA算法

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

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

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

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

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

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

3 基于蟻群算法的改進ICA

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

3.1 改進ICA的算法分析

3.1.1 確定目標函數

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

3.1.2 優化目標函數

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

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

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

通過螞蟻的轉移，求取各區域的目標函數值，比較其大小，從中選取最優的作為一次迭代結果，并帶入更新方程和轉移概率方程。當所有螞蟻選擇完一遍后，在求出的最優區域附近重新定義解空間，縮小取值范圍，并重復上面的計算并比較，直至預先給定的精度。

3.2 改進ICA的算法步驟

采用基于蟻群算法的改進ICA算法步驟如下:

1)對混合信號進行預處理，去均值和白化，得到z;

2)確定目標函數;

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

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

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

6)對每只螞蟻按轉移概率Pij進行轉移，并計算目標函數值，選取最優解;

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

8)若迭代次數Nc小于規定的最大循環次數，轉向步驟6)，否則縮小變量的取值范圍，轉步驟4)。

4 仿真及結果分析

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

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

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

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

選取同一非線性函數，再采用FastICA算法對混合信號進行分離，圖5為對應的分離信號波形。

圖2 3個源信號波形圖

圖3 混合后的信號波形圖

圖4 改進ICA算法的分離信號波形圖

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

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

5 小結

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

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

［2］葉婭蘭.獨立分量分析算法及其在生物醫學中的應用研究［D］.成都:電子科技大學，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］.電視技術，2009，33(4):57－59.

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

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

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