佘喜萍,田玉玲
(太原理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,山西 太原030024)
目前在網(wǎng)絡(luò)故障診斷技術(shù)的研究工作中,人工神經(jīng)網(wǎng)絡(luò) (ANN)的應(yīng)用最為普遍,但該算法存在一些缺點,通過積極吸取國外先進(jìn)理念和技術(shù),來提高網(wǎng)絡(luò)領(lǐng)域的智能診斷技術(shù)。
在人工神經(jīng)網(wǎng)絡(luò)模型中,BP網(wǎng)絡(luò)是一種特殊的多層感知機,通常采用梯度下降法迭代優(yōu)化權(quán)值來減小誤差函數(shù),將網(wǎng)絡(luò)實際輸出與目標(biāo)輸出的均方誤差 (MSE)定義為誤差函數(shù)。但是,梯度下降法也有一些不足之處,如:局部最優(yōu),對權(quán)值的初值敏感,不能處理非微誤差函數(shù)[1]。
為了克服這些缺點,在過去幾十年已經(jīng)用計算智能技術(shù)方法進(jìn)行訓(xùn)練權(quán)值,尤其在生物啟發(fā)算法領(lǐng)域,如遺傳算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法、分布估計算法和人工免疫算法。這些算法基于種群搜索策略,能夠成功處理復(fù)雜而龐大的搜索空間。
在這些算法中,人工免疫系統(tǒng) (AISs)的特性被廣泛地利用,即:種群大小的動態(tài)控制;探測或開發(fā)搜索空間的有效機制,能夠發(fā)現(xiàn)和保存局部最優(yōu),并且采樣和隨機插入新個體能夠保持種群多樣性[2]。
盡管在解決一般問題上表現(xiàn)出高性能,但是也有許多免疫啟發(fā)算法共有的缺點:隨著問題規(guī)模和復(fù)雜度的增加,算法的性能與適當(dāng)選擇設(shè)計參數(shù)密切相關(guān),如變異率。
為彌補AISs的缺點,研究者們提出采用概率模型來實現(xiàn)高性能的人工免疫系統(tǒng)?;谠撍枷?,已經(jīng)改進(jìn)一些算法并且成功應(yīng)用于不同優(yōu)化問題上。例如:貝葉斯人工免疫系 統(tǒng) (BAIS)[3]和 多 目 標(biāo) 貝 葉 斯 人 工 免 疫 系 統(tǒng)(MOBAIS)[4],在離散域分別對應(yīng)單目標(biāo)和多目標(biāo)優(yōu)化,高斯 人 工 免 疫 系 統(tǒng) (Gaussian artificial immune system,GAIS)[5]和多目標(biāo)高斯人工免疫系統(tǒng) (MOGAIS)[6]在連續(xù)域分別對應(yīng)單目標(biāo)和多目標(biāo)優(yōu)化。這些算法不僅能夠處理構(gòu)造模塊而且有著上述AISs的優(yōu)點。
本文提出采用GAIS算法訓(xùn)練BP網(wǎng)絡(luò)的權(quán)值和偏差來解決連續(xù)域中的單目標(biāo)問題。由于高斯網(wǎng)絡(luò)能夠正確捕捉變量之間的關(guān)系,因此,本文利用高斯網(wǎng)絡(luò)概率模型。
近年來提出用免疫啟發(fā)算法來解決連續(xù)優(yōu)化問題,概率模型替代變異和克隆操作來產(chǎn)生新抗體。由于高斯網(wǎng)絡(luò)能夠極大地表示變量之間的關(guān)系,本文中的算法采用高斯網(wǎng)絡(luò),故稱之為高斯人工免疫系統(tǒng) (GAIS)。該算法用一個候選解集 (抗體)實現(xiàn),這樣的解集能夠根據(jù)問題增加或減小。
GAIS算法如下:
(1)初始化抗體種群;
(2)種群估計;
(3)選擇最佳抗體;
(4)每迭代p 次建立一個高斯網(wǎng)絡(luò);
(5)采樣新抗體;
(6)抑制親和力小于閾值的抗體;
(7)消除相似抗體;
(8)隨機插入新抗體;
(9)如果不滿足停止條件,則返回 (2),否則,算法結(jié)束,得出最優(yōu)解集。
GAIS中,隨機產(chǎn)生初始種群。從當(dāng)前種群挑選最佳解(抗體),根據(jù)這些抗體建立高斯網(wǎng)絡(luò)。從網(wǎng)絡(luò)中采樣一些新抗體插入到種群中,消除相似的和親和力低的抗體。為保持種群多樣性,隨機生成少量抗體并插入到種群中,更好地搜索種群空間。
為了減少計算代價、降低運行時間,每p 次迭代重建網(wǎng)絡(luò)結(jié)構(gòu) (p>1),每迭代一次重新計算網(wǎng)絡(luò)的聯(lián)合概率。
GAIS不僅保持種群多樣性,還實現(xiàn)多峰優(yōu)化,根據(jù)待解問題動態(tài)調(diào)整種群大小,最重要的特性是,能夠識別和處理構(gòu)造模塊。該算法就同一問題運行多次后,搜索過程更具魯棒性。此外,候選解大量減少直到BP網(wǎng)絡(luò)達(dá)到某一性能水平。
該算法中提到兩個方法,一個是根據(jù)選出來的抗體建立高斯網(wǎng)絡(luò) (即:高斯網(wǎng)絡(luò)的學(xué)習(xí));另一個是如何利用高斯網(wǎng)絡(luò)產(chǎn)生新抗體。
GAIS最基本的兩個任務(wù)是高斯網(wǎng)絡(luò)的學(xué)習(xí)和采樣。對于一個給定的潛在解集,學(xué)習(xí)高斯網(wǎng)絡(luò),相當(dāng)于估計它們的聯(lián)合分布。根據(jù)已建立的高斯網(wǎng)絡(luò)采樣新實例作為新候選解。
高斯網(wǎng)絡(luò)是概率圖模型,通常用于連續(xù)域,來估計變量的概率依賴性[7]。高斯網(wǎng)絡(luò)通常用一組變量集合X={X1,X2,…,Xn}表示,它是有向非循環(huán)圖,節(jié)點表示問題的變量,邊表示變量之間的依賴關(guān)系。圖1 表示有5個變量的高斯網(wǎng)絡(luò)。
圖1 變量個數(shù)為5的高斯網(wǎng)絡(luò)
圖1中5個變量的聯(lián)合概率
X 的聯(lián)合概率由n 維高斯分布表示,故稱之為高斯網(wǎng)絡(luò)
例如,如果節(jié)點X1到節(jié)點X2有一條邊,那么稱X1是X2的父節(jié)點,所以X2的值條件依賴于X1的值。如果Xi有一系列父變量pai,它的概率分布是由條件概率密度函數(shù) (PDF)決定,表示為f(Xi|pai)。另外,沒有父變量的節(jié)點Xj的概率分布用無條件概率密度函數(shù)f(Xj)表示。所以,X 的聯(lián)合概率分布由條件概率密度函數(shù)表示,每個密度函數(shù)是一個獨立的高斯分布
式中,μi 是Xi的均值,σ2是Xi條件依賴于Xi父節(jié)點的方差,bki是線性系數(shù),表示Xk與Xi之間的連接強度。如果bki=0,那么Xk與Xi之間沒有聯(lián)系。
將高斯網(wǎng)絡(luò)中的bki和σ2i表示精度矩陣W,通過下列遞推公式得到等價的高斯分布[8]
高斯網(wǎng)絡(luò)從數(shù)據(jù)集中的學(xué)習(xí)過程如下:首先給定一批觀察數(shù)據(jù),搜索網(wǎng)絡(luò)中滿足條件的網(wǎng)絡(luò)并計算網(wǎng)絡(luò)得分,最高得分的網(wǎng)絡(luò)模型表示這些數(shù)據(jù)的聯(lián)合分布。通過搜索和評分方法學(xué)習(xí)的網(wǎng)絡(luò)來提供圖的結(jié)構(gòu),也就是估計每個變量的概率分布。
學(xué)習(xí)高斯網(wǎng)絡(luò)的通用方法是,給定的一個可以提供到空間中每個節(jié)點的相對得分的矩陣,采取一種用于搜索所有可能的候選網(wǎng)絡(luò)結(jié)構(gòu)空間的程序。GAIS 采用啟發(fā)式搜索,初始網(wǎng)絡(luò)為只有節(jié)點沒有邊的網(wǎng)絡(luò);用數(shù)據(jù)集估計每個變量的概率分布并計算網(wǎng)絡(luò)得分。建議搜索過程中通過增加、刪除一條邊,或轉(zhuǎn)換邊的方向來改變圖的結(jié)構(gòu),以便獲得比之前有更高得分的網(wǎng)絡(luò)。每次更改圖的結(jié)構(gòu)之后計算網(wǎng)絡(luò)變量的概率分布。而高斯網(wǎng)絡(luò)的得分矩陣,GAIS采用貝葉斯信息準(zhǔn)則 (BIC)計算[9]
其中
D 表示數(shù)據(jù)集,G 是被估計的網(wǎng)絡(luò),N 是實例數(shù),n是變量數(shù),bki是Xk和Xi的線性系數(shù),pai是Xi的父節(jié)點集,vi是Xi的 條 件 方 差,存 在X1,…,Xi-1i,k。函 數(shù)是懲罰復(fù)雜模型的函數(shù),dim(G)=2n+是被估計參數(shù)的個數(shù)。
一旦建立高斯網(wǎng)絡(luò),利用高斯網(wǎng)絡(luò)編碼的聯(lián)合概率分布 (式 (1))產(chǎn)生新實例。本文在高斯網(wǎng)絡(luò)中使用一種尋找節(jié)點祖先順序的方法,一次實例化一個變量,也就是,直到該變量所有的父節(jié)點被采樣之后,它才被采樣。GAIS中,采樣實例的數(shù)目隨時間變化。
為證明GAIS 訓(xùn)練BP 網(wǎng)絡(luò)權(quán)值的有效性,在這一部分,主要介紹分類問題,BP網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)采用完全連接的標(biāo)準(zhǔn)BP網(wǎng)絡(luò),即只有3 層。圖2 描述了GAIS訓(xùn)練BP網(wǎng)絡(luò)權(quán)值用于網(wǎng)絡(luò)故障診斷的過程。首先,將數(shù)據(jù)集歸一化,并分為兩類數(shù)據(jù):訓(xùn)練樣本和測試樣本。訓(xùn)練樣本送入GAIS中進(jìn)行學(xué)習(xí),而測試樣本直接送入訓(xùn)練后的BP模型中進(jìn)行檢測。
由于BP網(wǎng)絡(luò)的誤差函數(shù)由權(quán)值和偏差構(gòu)成的,訓(xùn)練網(wǎng)絡(luò)變成了一個搜索最佳權(quán)值和偏差的問題,而最佳權(quán)值集要有最小的誤差。抗體是實數(shù)編碼向量,由BP 網(wǎng)絡(luò)輸入層、隱藏層和輸出層的個數(shù)決定抗體的長度。
GAIS中的初始種群是用均勻分布編碼,隨機生成數(shù)值在 [-0.5,0.5]的矩陣。
圖2 GAIS訓(xùn)練BP權(quán)值的故障診斷方法
適應(yīng)度函數(shù)基于BP網(wǎng)絡(luò)性能定義,引用一個能正確分類訓(xùn)練模式數(shù)目的函數(shù)計算。適應(yīng)度函數(shù)可表示為
其中,NPCC (Abi)是網(wǎng)絡(luò)對抗體Abi編碼的正確分類模式的數(shù)目,NP 是訓(xùn)練集的實例總數(shù)。
此階段,消除相似抗體來避免冗余、保持多樣性。
初步實驗表明,抑制機制依賴于待解決問題的維數(shù),即待調(diào)整的權(quán)值和偏差數(shù)量。因為抑制機制采用解之間的歐氏距離,對于規(guī)范化向量,維數(shù)越大,距離越大。由于要研究的問題需要不同的神經(jīng)網(wǎng)絡(luò)維數(shù),與參數(shù)抑制獨立有關(guān)。以下步驟實現(xiàn)抑制:
(1)權(quán)值向量規(guī)范化為 [0,1]區(qū)間的值;
(2)確定規(guī)范化解的歐氏距離閾值ε;
(3)通過閾值將歐氏距離小于ε的抗體從種群中移除。
本文引用廣泛應(yīng)用于機器學(xué)習(xí)的6 種分類數(shù)據(jù)集和NS2模擬網(wǎng)絡(luò)數(shù)據(jù)集,分別對GAIS-BP 網(wǎng)絡(luò)和GA-BP 網(wǎng)絡(luò)[10,11]兩種算法進(jìn)行對比及分析。
實驗中六種數(shù)據(jù)集使用的參數(shù)一致。GAIS初始種群包含50個抗體,最大的迭代次數(shù)作為算法的終止條件,這里定義為500。
GAIS算法與GA 算法分別學(xué)習(xí)BP 網(wǎng)絡(luò)的權(quán)值。GABP是用遺傳算法優(yōu)化BP網(wǎng)絡(luò)的權(quán)值,遺傳算法采用選擇、交叉、變異、克隆等免疫操作。
對于GAIS,每迭代10次建立高斯網(wǎng)絡(luò),但是每迭代一次更新網(wǎng)絡(luò)的概率。為懲罰模型的復(fù)雜度,對一個節(jié)點能擁有父節(jié)點的個數(shù)加一個約束。相當(dāng)于一個可以覆蓋最大相互作用的順序,并且直接影響模型的復(fù)雜度。通過對高斯網(wǎng)絡(luò)學(xué)習(xí)的初步實驗,我們知道網(wǎng)絡(luò)復(fù)雜度越高,越有可能檢測出數(shù)據(jù)間偽相關(guān)性。因此,每個變量只能有兩個父節(jié)點。對于GAIS,當(dāng)前種群個數(shù)的80%用于建立概率模型。產(chǎn)生樣本的數(shù)量是當(dāng)前種群大小的一半。為產(chǎn)生多樣性,插入到種群的隨機個體數(shù)大約是當(dāng)前種群大小的3%。
GAIS使用概率模型,GA 不包含概率模型,因為高斯對非高斯的免疫啟發(fā)算法,所以采用這兩種算法對比是有道理的。
算法的參數(shù)通過初步實驗調(diào)整。兩種算法使用相同的神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),見表1的第5列。
表1 數(shù)據(jù)集的特性
3.2.1 描述數(shù)據(jù)集
我們采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的六種數(shù)據(jù)集:Iris、Ionosphere、Pima、Sonar、Wine、Glass。表1 給出每組數(shù)據(jù)的特性,包括實例總數(shù)、屬性數(shù)量、分類數(shù)和網(wǎng)絡(luò)的結(jié)構(gòu)(輸入數(shù),隱藏神經(jīng)元數(shù)和輸出數(shù))??紤]每個數(shù)據(jù)集的初步實驗的基礎(chǔ)上確定隱藏層神經(jīng)元的數(shù)目。所有數(shù)據(jù)的屬性規(guī)范化到 [-1,1]范圍內(nèi)。
3.2.2 實驗結(jié)果
實驗中把數(shù)據(jù)集分為訓(xùn)練樣本和測試樣本,其中80%的數(shù)據(jù)集作為訓(xùn)練樣本,剩下的20%作為測試樣本。
從表2中可以看出所有算法對測試樣本檢測的正確率都低于訓(xùn)練樣本,因為測試數(shù)據(jù)集是未知數(shù)的數(shù)據(jù),在六組分類數(shù)據(jù)集上表現(xiàn)出較高的泛化能力。由于GA 算法的變異操作不能捕捉變量之間的關(guān)系,故GAIS算法的正確率高于GA 算法。從搜索過程可以看出,GAIS隨著種群的大小動態(tài)地增減。實驗中,GAIS在單次運行中能產(chǎn)生幾個不同高質(zhì)量的神經(jīng)網(wǎng)絡(luò)。此外,在相對較短的迭代次數(shù)中能得到最優(yōu)解。表明識別和保存構(gòu)造模塊與執(zhí)行多峰搜索的能力一樣,使算法收斂速度更快。
表2 測試數(shù)據(jù)集的正確率 (%)
3.3.1 描述數(shù)據(jù)集
以NS2仿真軟件對某網(wǎng)絡(luò)仿真的實測數(shù)據(jù)進(jìn)行驗證。網(wǎng)絡(luò)拓?fù)淙鐖D3所示。
圖3 實驗網(wǎng)絡(luò)拓?fù)鋱D
NS2的模擬仿真圖如圖4所示。
圖4 NS2仿真結(jié)構(gòu)
對核心交換機相連的3個子網(wǎng)端口及與路由器相連端口平均輸出、輸入流量,CRC校驗錯,丟包率,端口協(xié)議,端口管理狀態(tài),端口當(dāng)前狀態(tài),端口檢測數(shù)據(jù)進(jìn)行采集,采樣間隔為10s,獲得5000條樣本數(shù)據(jù),每個樣本包含10個屬性。取其中對故障狀態(tài)有較大影響的3個屬性 (即端口管理狀態(tài)、端口當(dāng)前狀態(tài)、端口檢測)進(jìn)行預(yù)處理。實驗過程中人為設(shè)置鏈路通斷狀態(tài)及網(wǎng)絡(luò)阻塞等故障現(xiàn)象。由于每組數(shù)據(jù)有10個屬性,隱含層節(jié)點數(shù)根據(jù)經(jīng)驗得出,輸出結(jié)果有已知故障4 種:適配器故障、物理鏈路故障、管理性關(guān)閉、協(xié)議故障和未知故障、正常數(shù)據(jù)共6 類,故其神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為10:3:6。
3.3.2 實驗結(jié)果
GAIS隨機選擇80%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)。采用抑制機制消除相似網(wǎng)絡(luò)。實驗結(jié)果見表3。
表3 網(wǎng)絡(luò)故障實驗結(jié)果 (測試樣本)
從實驗結(jié)果中可以看出,正常樣本和協(xié)議故障有重疊導(dǎo)致了正確率偏低,由于未知故障是未確定的類,不能很快確定其故障類型,其它類的故障的識別率都達(dá)到了滿意值,本文提出的方法在實測網(wǎng)絡(luò)數(shù)據(jù)上的正確率可以滿足實際網(wǎng)絡(luò)故障檢測的需要。
網(wǎng)絡(luò)故障診斷中,算法的運行時間及檢測故障的正確率是網(wǎng)絡(luò)管理系統(tǒng)評價一個方法是否有效的兩個性能指標(biāo)。本文提出將利用采用概率模型的GAIS 來優(yōu)化BP 網(wǎng)絡(luò)權(quán)值,提高了收斂速度并能識別和保存構(gòu)造模塊,與遺傳算法相比減少了運行時間,提高了正確率。在UCI數(shù)據(jù)集和網(wǎng)絡(luò)實測數(shù)據(jù)集的實驗結(jié)果中可以看出,GAIS-BP 和GABP算法的運行時間隨著數(shù)據(jù)維數(shù)的增加而增加。實驗表明,GAIS設(shè)計精確網(wǎng)絡(luò)分類模型,并根據(jù)該模型的性能產(chǎn)生更好的結(jié)果。
盡管取得滿意結(jié)果,但仍然還有一些需要進(jìn)一步完善的地方,比如,評估高斯網(wǎng)絡(luò)的方法、采樣新個體的方法。
[1]HOU Rui.Introductions and applications of BP artificial neutral network [J].Science & Technology Information,2011,30(3):75-418 (in Chinese).[侯瑞.人工神經(jīng)網(wǎng)絡(luò)BP算法簡介及應(yīng)用 [J].科技信息,2011,30 (3):75-75.]
[2]Al-Enezi J R,Abbod M F,Alsharhan S.Artificial immune systems-models,algorithms and applications [J].International Journal of Research and Reviews in Applied Sciences,2010,3(2):118-131.
[3]Castro P A D,Von Zuben F J.Learning ensembles of neural networks by means of a bayesian artificial immune system [J].IEEE Transactions on Neural Networks,2011,22 (2):304-316.
[4]Castro P A D,Von Zuben F J.Multi-objective feature selection using a Bayesian artificial immune system [J].Journal of Intelligent Computing and Cybernetics,2010,3 (2):235-256.
[5]Castro P A D,Von Zuben F J.GAIS:A gaussian artificial immune system for continuous optimization [R].Australia:Proc 9th Int Conf on Artificial Immune Systems,2010:171-184.
[6]Castro P A D,Von Zuben F J.A gaussian artificial immune system for multi-objective optimization in continuous domains[R].USA:Proc 10th International Conference on Hybrid Intelligent Systems,2010:159-164.
[7]LI Bin,ZHONG Runtian,WANG Xianji,et al.A continuous optimization algorithm based-on progressive estimation of gaussian mixture model[J].Chinese Journal of Computers,2007,30 (6):979-985 (in Chinese).[李斌,鐘潤添,王先基,等.一種基于遞增估計GMM 的連續(xù)優(yōu)化算法 [J].計算機學(xué)報,2007,30 (6):979-985.]
[8]Prakash P Shenoy.Inference in hybrid Bayesian networks using mixtures of Gaussians[R].USA:Twenty-Second Conference on Uncertainty in Artificial Intelligence,2012:428-436.
[9]XU Jinchao,ZENG Guosun,WANG Wei.Software reliability assessment based on Bayesian method [J].Journal of Tongji University (Natural Science),2012,40 (7):1102-1110 (in Chinese).[許金超,曾國蓀,王偉.一種基于貝葉斯理論的軟件可靠度評估方法 [J].同濟大學(xué)學(xué)報 (自然科學(xué)版),2012,40 (7):1102-1110.]
[10]XIAO Zhiping,WU Wenquan,ZENG Yang.Research on application of GA-BP neural networks is fault diagnosis of airborne radar[J].Computer Measurement & Control,2011,19 (1):14-16 (in Chinese).[肖治平,吳文全,曾洋.遺傳BP網(wǎng)絡(luò)在機載雷達(dá)故障診斷中的應(yīng)用研究 [J].計算機測量與控制,2011,19 (1):14-16.]
[11]NONG Jifu.Precipitation forecasting model based on neural network and genetic algorithms [J].College Mathematics,2012,28 (5):114-118 (in Chinese).[農(nóng)吉夫.遺傳算法與神經(jīng)網(wǎng)絡(luò)結(jié)合的降水預(yù)報模型 [J].大學(xué)數(shù)學(xué),2012,28(5):114-118.]