實值否定選擇算法的優(yōu)化研究*

王玉玨 漆德寧

(陸軍軍官學院 合肥 230031)

?

實值否定選擇算法的優(yōu)化研究*

王玉玨 漆德寧

(陸軍軍官學院 合肥 230031)

針對傳統(tǒng)的否定選擇算法和V-detector算法存在的“黑洞”以及檢測器冗余問題,論文提出了優(yōu)化算法。在檢測器生成階段,候選檢測器與自體數據和成熟檢測器同時進行耐受訓練,比較結果確定檢測器半徑,減少檢測器的重復覆蓋;在檢測器成熟階段,計算自體重復覆蓋率剔除完全被覆蓋的檢測器,克服了“黑洞“及冗余問題。最后,通過Iris數據比較了三種算法。實驗結果顯示,改進算法的檢測器數量大幅減少,利于實踐應用。

人工免疫; 否定選擇算法; V-detector

Class Number TP301.6

1 引言

隨著工業(yè)的發(fā)展,設備對診斷系統(tǒng)的實時性、準確性提出了高要求,傳統(tǒng)的故障診斷方法已經難以滿足復雜設備檢測診斷的要求。近年來,以智能信息處理為核心的智能診斷技術得到了快速發(fā)展,至今智能診斷技術有專家系統(tǒng)、模糊邏輯、神經網絡和遺傳算法等。傳統(tǒng)的智能診斷技術受限于先驗知識,需要大量的故障樣本進行訓練,影響了故障診斷的開展。受自然免疫系統(tǒng)啟示,人工免疫技術發(fā)展迅速。人工免疫方法主要包括三方面[1]:否定選擇算法(negative selection algorithm,NSA)、克隆選擇算法和免疫網絡模型。作為人工免疫技術核心算法的否定選擇算法,不同于傳統(tǒng)的智能診斷算法,由于其不需要先驗知識,只需要有限的正常數據就可以檢測出異常數據,使得NSA在異常檢測及故障診斷方面取得了一系列的研究成果。

2 實值否定選擇算法

2.1 否定選擇算法

墨西哥大學Forrest教授[2]在1994年在對計算機入侵檢測研究中,依據T細胞成熟過程中所經歷的審查過程(只有那些不能與機體自身組織發(fā)生應答的T細胞才能離開胸腺,執(zhí)行免疫任務),依據這樣的否定選擇原理,首次引入NSA,用于計算機數據變化的檢測。基本算法流程如圖1所示。

圖1 基本算法流程

算法模仿免疫系統(tǒng)否定選擇的原理,隨機產生檢測器,刪除能夠檢測到自體(self)的檢測器,保留檢測到非自體(non-self)的檢測器。特點是不需要設備的先驗知識,能夠利用有限的自體數據產生檢測器,檢測出設備的異常。自NSA提出以來,國內外學者對其進行了大量研究,使算法得到了進一步優(yōu)化,使之更適合于實踐的應用。NSA的技術要點主要包括自體數據形式、檢測器表示、匹配準則和檢測器生成原理等。

2.2 實值否定選擇算法檢測器的表示、匹配規(guī)則及生成原理

實值檢測器的表示主要有下列類型:超球體模型、超方體模型、超橢球體模型、多形狀模型和矩陣類型。匹配規(guī)則:閔可夫斯基距離、隸屬函數、空間包含匹配準則和雙向匹配準則等[3]。

Gonzalez[4]等2002年提出實值否定選擇算法(Real-Valued negative selection algorithms,RNSA)檢測器的生成方法,并用于時間序列數據的異常檢測,2003[5]年用蒙特卡洛的方法估計了檢測器的數量,提出隨機RNSA算法。RNSA檢測器主要以超球體模型為主,且半徑不變。在RNSA中,“黑洞”問題無法有效地克服,檢測器數量急劇增加,算法復雜度提高,限制了其實際應用。

針對RNSA存在的問題,Zhou Ji[6]提出半徑可變的實值否定選擇算法(V-detector)。算法隨機生成候選檢測器集,并計算與自體數據的距離,為每一個檢測器選定了一個最小半徑。與RNSA相比,V-detector以少量的檢測器覆蓋了大量的非自體空間,減少了“黑洞”,提高了檢測的效率。

RNSA半徑固定不變,為了達到高覆蓋率必定需要大量的檢測器,并且容易產生“黑洞”。V-detector以較少的檢測器達到了高覆蓋率,但是檢測器之間重復覆蓋嚴重,為了達到較高的覆蓋率,容易產生大量冗余檢測器,導致算法的時間消耗巨大,這一缺點限制了V-detector的實際應用。本文針對“黑洞”以及檢測器冗余問題在V-detector的基礎上提出了優(yōu)化改進。

3 優(yōu)化算法

將實值空間U劃分為兩部分,自體空間Uself和非自體空間U=Uself∪Unon-self。自體集S?Uself,檢測器集D?{s1,s2,…,sNs},D={d1,d2,…,dNd},其中Ns和Nd分別為自體和檢測器的數量?？臻g距離采用歐式距離:

針對RNSA與V-detector存在著“黑洞”及冗余,優(yōu)化的目的是產生檢測器覆蓋較多的非自體區(qū)域,并使檢測器之間的重復覆蓋較少。

優(yōu)化算法的流程為:

Step1 根據自體數據隨機生成候選檢測器。

Step2 將候選檢測器與自體集和成熟檢測器集同時進行耐受訓練,只有不被自體與成熟檢測器檢測到的候選檢測器才能成為成熟檢測器。

Step3 隨機生成檢測器比較候選檢測器與最近自體和最近成熟檢測器耐受情況確定檢測器半徑。當成熟檢測器非自體覆蓋率大于預設值時或者達到預定成熟檢測器數量時結束算法,否則繼續(xù)隨機生成候選檢測器。

Step4 依據Monte Carlo[7]方法去除成熟檢測器中重復覆蓋率為100%和未檢測到的檢測器。最后形成成熟檢測器集用于待測數據的檢測。

4 仿真及結果分析

為了測試和驗證改進算法的性能,本文在不同參數下使用Matlab2013a進行仿真,采用了Fish’s Iris數據集進行對比。該數據集包括setosa,versicolor和virginica三類,每類有50個樣本,每個樣本由萼片寬度,萼片長度,花瓣長度和花瓣寬度四個屬性描述。由于versicolor和virginica空間分布較近,因此選取setosa前兩項屬性作為自體集,versicolor和virginica前兩項屬性作為待測數據。本文設計了兩組實驗:

1) 以期望成熟檢測器數量為算法終止條件,RNSA檢測器半徑取0.1,分別以檢測器數量為20、50和80,自體半徑為0.05,取實驗50次的平均值,比較三種算法的檢測器覆蓋率C和診斷正確率R。

仿真結果顯示,在期望成熟檢測器數量為20、50和80時,改進算法在檢測器覆蓋率和診斷正確率上比RNSA和V-detector都有所提高。

表1 實驗(1)結果對比,rs=0.05

圖2 Num=80時,三種算法示意圖

從圖中可以看出,RNSA存在嚴重的“黑洞”問題,檢測率不高;V-detector檢測器重疊率太高,計算量大;改進算法優(yōu)化效果較好,保證了每個檢測器都不被完全覆蓋。

2) 優(yōu)化算法以期望覆蓋率作為算法終止條件,RNSA檢測器半徑取0.1,分別以期望覆蓋率為60%、75%和90%,自體半徑為0.05,取實驗50次的平均值,對比三種算法的檢測器數量Num和診斷正確率R。

圖3 期望覆蓋率為90%時,三種算法示意圖

算法60%75%90%NumRNumRNumRRNSA30.278.8%5290.8%348.499.8%V-detector4.874.8%11.697.8%143.8100%改進算法3.299.1%6.699.4%22.3100%

仿真結果顯示,在期望覆蓋率為60%、75%和90%時,改進算法在檢測器數量上有了大幅度地減少,節(jié)省了計算空間,有利于工程實踐應用。

5 結語

本文對V-detector算法進行了優(yōu)化,在檢測器生成階段考慮成熟檢測器的影響,隨機生成的候選檢測器同時與自體集和成熟檢測器集進行耐受訓練,減少檢測器的冗余。在成熟檢測器形成后,通過計算自體重復覆蓋率剔除無效檢測器,大幅度地減少了無效檢測器的數量。仿真結果表明,改進算法具有一定的有效性,有利于工程實際的應用。

[1] DASGUPTAA D, YUA SNINO F. Recent advances in artificial immune systems: models and applications[J]. Applied Soft Computing,2011,11:1574-1587.

[2] FORREST S, PERELSON A S, ALLEN L, et al. Self-nonself discrimination in a computer[C]//Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy IEEE. Los Alamitos, CA,1994:221-231.

[3] ZHOU J, DASGUPTA D. Revisiting negative selection algorithms[J]. Evolut Comput,2007,15(2):223-251.

[4] F. Gonzalez, D. Dasgupta, R Kozma. Combining negative selection and classification techniques for anomaly detection[C]//Proceeding of the 2002 Congress on Evolutionary, USA,2002:705-710.

[5] F. Gonzalez, D. Dasgupta. Anomaly detection using real-valued negative selection[J]. Journal of Genetic Programming and Evolvable Machine,2003:383-403.

[6] Zhou Ji, D. Dasgupta. Real-valued negative selection algorithm with variable-sized detectors[C]//Proc. of GECCO, Seattle, WA, USA, Vol.3102 of LNCS, Springer-Verlag,2004:287-298.

[7] 劉海龍,張鳳斌,席亮.基于Monte Carlo估計的免疫檢測器分布優(yōu)化算法[J].計算機應用,2013,33(3):723-726.

Optimization of Real-valued Negative Selection Algorithm

WANG Yujue QI Dening

(Army Official Academy, Hefei 230031)

For the question of “black holes” and the redundancy in the traditional negative selection algorithm and V-detector algorithm, this article proposes the optimization of the algorithm. In the detector generation phase, the self data and mature detectors are tolerated by the candidate’s detector at the same time, the results of the comparision decide the radius in order to reduce the duplicated covering. In the mature detectors phase, the completely covered detector is deleted through calculating, which overcomes the question of “black holes” and the redundancy. At last, it compares three algorithms through data of Iris. The experimental results show that the number of detectors reduces dramatically, which is good for practical application.

artificial immune, negative selection algorithm, V-detector

2014年7月14日,

2014年8月21日

王玉玨,男,碩士研究生,研究方向:通信與信息系統(tǒng)。漆德寧,男,教授,研究方向:通信與信息系統(tǒng)。

TP301.6

10.3969/j.issn1672-9730.2015.01.014