实值否定选择算法的优化研究*

王玉珏 漆德宁

(陆军军官学院 合肥 230031)



实值否定选择算法的优化研究*

王玉珏 漆德宁

(陆军军官学院 合肥 230031)

针对传统的否定选择算法和V-detector算法存在的“黑洞”以及检测器冗余问题,论文提出了优化算法。在检测器生成阶段,候选检测器与自体数据和成熟检测器同时进行耐受训练,比较结果确定检测器半径,减少检测器的重复覆盖;在检测器成熟阶段,计算自体重复覆盖率剔除完全被覆盖的检测器,克服了“黑洞“及冗余问题。最后,通过Iris数据比较了三种算法。实验结果显示,改进算法的检测器数量大幅减少,利于实践应用。

人工免疫; 否定选择算法; V-detector

Class Number TP301.6

1 引言

随着工业的发展,设备对诊断系统的实时性、准确性提出了高要求,传统的故障诊断方法已经难以满足复杂设备检测诊断的要求。近年来,以智能信息处理为核心的智能诊断技术得到了快速发展,至今智能诊断技术有专家系统、模糊逻辑、神经网络和遗传算法等。传统的智能诊断技术受限于先验知识,需要大量的故障样本进行训练,影响了故障诊断的开展。受自然免疫系统启示,人工免疫技术发展迅速。人工免疫方法主要包括三方面[1]:否定选择算法(negative selection algorithm,NSA)、克隆选择算法和免疫网络模型。作为人工免疫技术核心算法的否定选择算法,不同于传统的智能诊断算法,由于其不需要先验知识,只需要有限的正常数据就可以检测出异常数据,使得NSA在异常检测及故障诊断方面取得了一系列的研究成果。

2 实值否定选择算法

2.1 否定选择算法

墨西哥大学Forrest教授[2]在1994年在对计算机入侵检测研究中,依据T细胞成熟过程中所经历的审查过程(只有那些不能与机体自身组织发生应答的T细胞才能离开胸腺,执行免疫任务),依据这样的否定选择原理,首次引入NSA,用于计算机数据变化的检测。基本算法流程如图1所示。

图1 基本算法流程

算法模仿免疫系统否定选择的原理,随机产生检测器,删除能够检测到自体(self)的检测器,保留检测到非自体(non-self)的检测器。特点是不需要设备的先验知识,能够利用有限的自体数据产生检测器,检测出设备的异常。自NSA提出以来,国内外学者对其进行了大量研究,使算法得到了进一步优化,使之更适合于实践的应用。NSA的技术要点主要包括自体数据形式、检测器表示、匹配准则和检测器生成原理等。

2.2 实值否定选择算法检测器的表示、匹配规则及生成原理

实值检测器的表示主要有下列类型:超球体模型、超方体模型、超椭球体模型、多形状模型和矩阵类型。匹配规则:闵可夫斯基距离、隶属函数、空间包含匹配准则和双向匹配准则等[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的基础上提出了优化改进。

3 优化算法

将实值空间U划分为两部分,自体空间Uself和非自体空间U=Uself∪Unon-self。自体集S⊂Uself,检测器集D⊂{s1,s2,…,sNs},D={d1,d2,…,dNd},其中Ns和Nd分别为自体和检测器的数量。空间距离采用欧式距离:

针对RNSA与V-detector存在着“黑洞”及冗余,优化的目的是产生检测器覆盖较多的非自体区域,并使检测器之间的重复覆盖较少。

优化算法的流程为:

Step1 根据自体数据随机生成候选检测器。

Step2 将候选检测器与自体集和成熟检测器集同时进行耐受训练,只有不被自体与成熟检测器检测到的候选检测器才能成为成熟检测器。

Step3 随机生成检测器比较候选检测器与最近自体和最近成熟检测器耐受情况确定检测器半径。当成熟检测器非自体覆盖率大于预设值时或者达到预定成熟检测器数量时结束算法,否则继续随机生成候选检测器。

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检测器重叠率太高,计算量大;改进算法优化效果较好,保证了每个检测器都不被完全覆盖。

2) 优化算法以期望覆盖率作为算法终止条件,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%时,改进算法在检测器数量上有了大幅度地减少,节省了计算空间,有利于工程实践应用。

5 结语

本文对V-detector算法进行了优化,在检测器生成阶段考虑成熟检测器的影响,随机生成的候选检测器同时与自体集和成熟检测器集进行耐受训练,减少检测器的冗余。在成熟检测器形成后,通过计算自体重复覆盖率剔除无效检测器,大幅度地减少了无效检测器的数量。仿真结果表明,改进算法具有一定的有效性,有利于工程实际的应用。

[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].计算机应用,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日

王玉珏,男,硕士研究生,研究方向:通信与信息系统。漆德宁,男,教授,研究方向:通信与信息系统。

TP301.6

10.3969/j.issn1672-9730.2015.01.014