王玉玨 漆德寧

(陸軍軍官學(xué)院 合肥 230031)

?

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

王玉玨 漆德寧

(陸軍軍官學(xué)院 合肥 230031)

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

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

Class Number TP301.6

1 引言

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

2 實(shí)值否定選擇算法

2.1 否定選擇算法

墨西哥大學(xué)Forrest教授[2]在1994年在對(duì)計(jì)算機(jī)入侵檢測(cè)研究中,依據(jù)T細(xì)胞成熟過程中所經(jīng)歷的審查過程(只有那些不能與機(jī)體自身組織發(fā)生應(yīng)答的T細(xì)胞才能離開胸腺,執(zhí)行免疫任務(wù)),依據(jù)這樣的否定選擇原理,首次引入NSA,用于計(jì)算機(jī)數(shù)據(jù)變化的檢測(cè)?；舅惴鞒倘鐖D1所示。

圖1 基本算法流程

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

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

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

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

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

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

3 優(yōu)化算法

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

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

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

Step1 根據(jù)自體數(shù)據(jù)隨機(jī)生成候選檢測(cè)器。

Step2 將候選檢測(cè)器與自體集和成熟檢測(cè)器集同時(shí)進(jìn)行耐受訓(xùn)練,只有不被自體與成熟檢測(cè)器檢測(cè)到的候選檢測(cè)器才能成為成熟檢測(cè)器。

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

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

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

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

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

仿真結(jié)果顯示,在期望成熟檢測(cè)器數(shù)量為20、50和80時(shí),改進(jìn)算法在檢測(cè)器覆蓋率和診斷正確率上比RNSA和V-detector都有所提高。

表1 實(shí)驗(yàn)(1)結(jié)果對(duì)比,rs=0.05

圖2 Num=80時(shí),三種算法示意圖

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

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

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

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

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

5 結(jié)語

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

[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估計(jì)的免疫檢測(cè)器分布優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,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