阴性选择算法检测器生成的优化及仿真

门 洪, 陈 鹏

(东北电力大学 自动化工程学院, 吉林 吉林 132012)

阴性选择算法检测器生成的优化及仿真

门 洪, 陈 鹏

(东北电力大学 自动化工程学院, 吉林 吉林 132012)

针对现有常规阴性选择算法在非我空间覆盖设计上未考虑自身免疫性检测器发生的问题, 提出一种能检测和剔除自身免疫性检测器的方法, 并以MATLAB软件为仿真实验平台, 分别对不规则分布数据、环形分布数据和近圆形分布数据3种空间数据分布进行仿真研究.仿真结果表明, 该方法能有效剔除90%的自身免疫性检测器, 提升了免疫阴性选择算法的鲁棒性和自适应能力.

人工免疫系统； 阴性选择； 自身免疫性检测器； 算法优化； 算法仿真

0 引 言

人工免疫系统中的阴性选择算法[1]源于人体内T淋巴细胞发育过程中的阴性选择机制.该算法定义正常情况下的信息为自我集合, 异常状态为非我集合, 从而实现自我与非我间的区分.检测器生成是阴性选择算法的关键环节, 与问题表达的编码方案紧密相关.目前主要有两种编码方案： 二进制编码和实值编码, 分别对应传统阴性选择算法和实值阴性选择算法.其中传统阴性选择算法延续了Forrest阴性选择算法的技术, 而实值阴性选择算法因问题表示逼近实际空间、匹配规则容易建立等优点而被广泛应用[2-3].

实值阴性选择算法根据检测器在三维空间中的形状可分为球形检测器和立方体检测器.其中球形检测器通常分为固定半径检测器和可变半径检测器, 提出的目的是为了缩小阴性选择算法中难以避免的“黑洞”问题[3].目前针对缩小阴性选择算法黑洞的方法主要有检测器移动检测技术[4-5]、分布调整技术[6]、定向受体编辑技术[7]及可变模糊匹配技术[8]等, 但这些技术都只在一定程度上缩小了黑洞, 即提高了对非我空间的覆盖率.王玉健[9]针对矩形检测器提出了基于检测划分机制的检测器生成算法, 该算法为确定性算法, 能确保非我区域的全覆盖, 但生成的检测器规模较大, 算法耗时.

针对阴性选择算法检测器生成耗时问题, 常见的解决方法是使检测器的感受半径能自适应的调整, 如刘芳等[10]提出的强制多目标优化技术对检测器的空间分布进行干涉, 有效提高了检测器的生成效率.此外, 通过设计携带粒子群优化功能的检测器生成, 也能对检测器的生成起精简作用, 相关实验结果证明了该方法也能同时提高阴性选择算法的泛化能力[11].借鉴随机思想, 杨东勇等[12]将多种群遗传算法融入到检测器生成环节, 有效降低了原始检测器生成算法的冗余问题和耗时过大问题.文献[13]针对自我空间边界容易被检测器过境入侵的现象, 设计了带进化边界检测器的阴性选择检测器生成算法, 提高了阴性选择算法在异常检测上的成功率.

实现成熟检测器对非我空间全覆盖的前提是自我个体空间能被自我个体全覆盖, 即自我个体数量上的充分满足, 但实际采集到的样本总是有限, 且有随机性, 这种漏洞极易引发检测器生成的自身免疫问题, 针对该问题, 本文以矩形检测器生成算法为基础, 提出一种能避免检测器生成自身免疫现象的方案, 计算机软件仿真测试结果验证了该方案的有效性.

正常状态下， 生物体免疫系统是稳定的， 当识别到非我信号时启动免疫应答， 而对自体成分保持宏观上的免疫耐受， 即能正确地识别“自我”和“非我”.一旦这种状态被打破， 就会产生自身免疫性疾病， 作为动态的免疫系统， 由于T细胞受体和B细胞受体的基因序列随机重排现象， 决定了暂态的自身免疫活动属正常范围， 且暂态的自身免疫活动会伴随淋巴细胞成长过程中的克隆删除和免疫失活而平息， 但如果发生持续性自身免疫现象就会演变成自身免疫性疾病.自身免疫性疾病由于和正常的免疫应答一样会产生抗体， 从而对自身组织器官产生一定程度的损害， 具有反复发作和慢性迁延的特点.

1 实值检测器生成算法自身免疫缺陷的分析

定义二维模式空间全集为U: {U(x,y)|x∈[0,1],y∈[0,1]},N表示非我模式空间,S表示自我模式空间, 并满足U=S∪N.S的区域定义为

成熟检测器集定义为d{dij=[cij,r0],cij=(c1,c2,…,cV)}, 其中V表示所处空间维度, 本文设V=2.

从自我区域内随机选取60个点作为自我个体集合, 定义每个自我个体的感受半径rs=0.015； 应用基于实值划分的检测器生成程序生成对应的成熟检测器, 控制最小检测器探测半径rmin分别为0.005,0.01,0.02,0.04, 观察其对非我区域的覆盖度、运行耗时t及生成的成熟检测器数目n0.仿真结果如图1所示.

图1 成熟检测器对非我空间的覆盖仿真结果Fig.1 Simulation results of mature detector’s coverage for non-self space

为了说明基于检测划分实值检测器生成算法存在的自身免疫缺陷, 下面给出两个定义.

1) 致病检测器： 检测器d(c,r)所处空间完全为自我个体分布的空间内部, 即d⊂S, 如图1(A)和(B)就存在一定量的致病检测器.

2) 半致病检测器： 检测器d(c,r)所处空间与自我个体的分布空间存在濒临关系或其所处空间位置为自我模式空间的边缘部位, 没有完全置于内部, 如图1中的黑色区域即为半致病检测器存在的区域.

致病检测器的存在与生物免疫系统中的自身免疫性疾病原理一致, 即致病检测器将对自我元素启动识别和判断, 如果用于数据的分类, 则会将本属于自我集合的元素判断为非我元素.为了衡量检测器是否为致病检测器, 关键的问题是要判断其是否处于自我空间内部, 尤其是当自我模式空间为任意可能存在形状的情况下.

2 致病检测器的判别方法

2.1初次判定方法

图2 初次判定规则的漏洞Fig.2 Preliminary determination rules’ loopholes

对于检测器d(c,r)是否处于自我模式范围内部, 直观条件是其周围是否存在自我个体, 对于二维空间意义上的检测器, 即以其中心为中心平面坐标系的4个象限内均有自我元素存在, 可初步判断检测器d(c,r)产生在自我范围内.本文通过计算每个生成检测器与每个自我个体间的夹角θ, 判断对应自我个体相对于待测检测器所处的空间象限位置.夹角在同一象限的所有自我元素被分配相同的内部系数(2W)-1, 其中W为所处空间的维度, 并被赋予相同的象限标签nd.同时, 根据

计算待测检测器d(c,r)的内部因子τ(θ), 其中:n0为生成检测器的数目;ns为自我集合空间中随机选取的自我个体数目; numel和unique为MATLAB中的函数.当τ(θ)i=1时, 则判定检测器dij(cij,rj)为致病检测器; 当τ(θ)i≤0.5时为成熟检测器; 否则为半致病检测器.

2.2二次判定方法

如果仅以检测器周围是否存在自我个体作为其是否为致病检测器的判定尚不完备, 因为当自我个体在空间中的分布符合环形分布特点时, 环带内部生成的成熟检测器将被初次规则定义为致病检测器, 如图2所示.

其中:c(j,m)表示第j个致病检测器的空间坐标信息;m∈[1,W], 表示W维致病检测器每个个体空间坐标有W个数值.通过累加计算求出该检测器与自我个体S(i,m)的亲和度qhd.

根据初步判定规则可知, 被判定为致病检测器的内部因子τ=1, 而深度判定规则的建立就是进一步对内部因子τ进行重新修正, 修正方法如下:

其中系数ε为亲和度阈值调节系数.亲和度阈值调节系数的引入是因为其阈值并非一个固定值, 而是随数据的分散程度而定, 聚集度较高的数据亲和度阈值较小; 反之, 离散程度较高的数据集, 其亲和度阈值则较大.为了直观分析其内在关系, 本文定义一种数据离散度指数： 分散系数Fsd, 计算方法如下：

其中S1(i)表示每个自我个体S(i)所处位置的最近象限亲子个体集, 每个象限取一个亲和度最强个体, 这样S1(i)最多有2W个个体, 至少有1个个体, 并指定n1表示其个体数目(n1∈[1,2W]); ∑表示对自我个体采取行计算并求和;m为维度计数变量, 每计算一次其值增加1, 直至达到W为止.

2.3数据分散系数Fsd的仿真验证

自我空间的覆盖率越低致病检测器越易侵入, 但可通过调节亲和度阈值调节系数ε控制致病检测器的产生, 而ε与自我空间的覆盖率紧密相关, 由于自我个体的感受半径rs可变, 因此通过计算自我个体的总面积或总体积不可行.本文设计的分散系数Fsd则仅与自我个体的空间分布有关, 能反应自我集合数据的空间分布.

为了观察数据分散系数对亲和度阈值的影响, 本文构建一组环形数据集, 因为环带分布的数据集其亲和度阈值比普通分布数据更易受数据离散程度的影响.环形数据集的分布函数为

当自我集合分布为式(6)、采样点数为197时的数据集空间分布及当采样点由5增加到300, 步长为8时, 对应的数据分散系数随采样点数的变化曲线如图3所示.图3显示了37组采样数据集的分散系数变化情况, 每隔3组抽取一组数据集观察数据分散系数对亲和度阈值的影响, 共计13组样本, 输入到检测器生成算法进行调试, 分别获得了13组亲和度阈值及对应的系数ε, 结果列于表1.

图4为表1的折线图.由图4可见, 亲和度阈值对数据的分散程度变化反应迟钝, 通常一个合适的值会在一定区间内产生相同效果, 而不需要跟随分散系数的变化而变化.此外, 由于采样点数的增加, 算法运行所消耗的时间也随之增加, 因此, 在处理实际问题时采样点数并非越多越好.

图3 环形数据分散系数随采样点数的变化曲线Fig.3 Plot of dispersion coefficient of annular data vs sampling point

图4 Fsd,ε及t随采样点数的变化关系Fig.4 Changing trends of Fsd,ε and t with sampling point

表1 Fsd,ε及耗时t随采样点数的变化规律Table 1 Changes of Fsd, ε and t with sampling point

3 仿真结果分析

应用本文优化处理后的检测器生成算法分别对圆环形分布数据集、椭圆环形分布数据集及不规则分布数据集分别进行两次检测器生成, 第一次为优化前的检测器生成, 第二次为优化后的检测器生成, 实验结果如图5所示.由图5可见, 优化后检测器生成算法在很大程度上抑制了致病检测器的生成, 避免了自身免疫缺陷的发生.同时由于检测器数目的降低, 算法运行时间也提高了约30%.

图5 阴性选择检测器生成算法优化前后示意图Fig.5 Scheme of detector’s generation before and after its optimization

综上可见, 检测器的生成是阴性选择算法的关键环节, 本文在学习基于检测划分实值检测器生成算法的基础上, 针对基于检测划分实值检测器生成算法中存在的自身免疫性缺陷提出了一种优化方法, 并利用不同的空间分布数据进行了仿真测试, 结果表明这种优化是有效的, 致病检测器生成的抑制和剔除, 使阴性选择算法的整体性能得到了提升.

[1]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.Los Alamitos, CA: IEEE Press, 1994: 202-212.

[2]Gonzalez F, Dasgupta D, Kozma R.Combining Negative Selection and Classification Techniques for Anomaly Detection [C]//Proc the 2002 IEEE Congress on Evolutionary Computation, CEC-2002.Honolulu: IEEE, 2002: 705-710.

[3]张衡, 吴礼发, 张毓森, 等.一种r可变阴性选择算法及其仿真分析 [J].计算机学报, 2005, 28(10): 1614-1619.(ZHANG Heng, WU Lifa, ZHANG Yusen, et al.An Algorithm ofrAdjustable Negative Selection Algorithm and Its Simulation Analysis [J].Journal of Computers, 2005, 28(10): 1614-1619.)

[4]Laurentys C A, Palhares R M, Caminhas W M.A Novel Artificial Immune System for Fault Behavior Detection [J].Expert Systems with Applications, 2011, 38: 6957-6966.

[5]张凤斌, 王天博.实值n维混沌映射否定选择算法 [J].计算机研究与发展, 2013, 50(7): 1387-1398.(ZHANG Fengbin, WANG Tianbo.Real Value Negative Selection Algorithm with then-Dimensional Chaotic Map [J].Journal of Computer Research and Development, 2013, 50(7): 1387-1398.)

[6]XU Aiqiang, LIU Yong, ZHAO Xiuli, et al.Optimization and Application of Real-Valued Negative Selection Algorithm [J].Procedia Engineering, 2011, 23: 241-246.

[7]李贵洋, 郭涛.一种基于受体编辑的实值阴性选择算法 [J].计算机科学, 2012, 39(8): 246-251.(LI Guiyang, GUO Tao.Receptor Editing Based Real Valued Negative Selection Algorithm [J].Computer Science, 2012, 39(8): 246-251.)

[8]王辉, 于立君, 王科俊, 等.一种可变模糊匹配阴性选择算法 [J].智能系统学报, 2011, 6(2): 178-184.(WANG Hui, YU Lijun, WANG Kejun, et al.An Adjustable Fuzzy Matching Negative Selection Algorithm [J].CAAI Transactions on Intelligent System, 2011, 6(2): 178-184.)

[9]王玉健.实值检测器生成算法研究 [D].合肥: 中国科学技术大学, 2009.(WANG Yujian.Research on Real-Valued Detector Generation Algorithm [D].Hefei: University of Science and Technology of China, 2009.)

[10]LIU Fang, GONG Maoguo, MA Jingjing, et al.Optimizing Detector DistributioninV-Detector Negative Selection Using a Constrained Multiobjective Immune Algorithm [C]//2010 IEEE Congress on Evolutionary Computation (CEC).Barcelona, Spain: IEEE, 2010: 1-8.

[11]Heydenrych M, Ehlers E.A Charged PSO Inspired Method for Generating Immune Detectors for Network Intrusion Detection [C]//2011 IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom).[S.l.]: IEEE, 2011: 134-141.

[12]杨东勇, 陈晋音.基于多种群遗传算法的检测器生成算法研究 [J].自动化学报, 2009, 35(4): 425-432.(YANG Dongyong, CHEN Jinyin.Researeh on Deteetor Generation Algorithm Based on Multiplepopulations GA [J].Acta Automatica Sinica, 2009, 35(4): 425-432.)

[13]WANG Dawei, ZHANG Fengbin, XI Liang.Evolving Boundary Detector for Anomaly Detection [J].Expert Systems with Applications, 2011, 38: 2412-2420.

Real-ValuedDetector’sGenerationofNegativeSelectionAlgorithmOptimizationandSimulation

MEN Hong, CHEN Peng
(SchoolofAutomationEngineering,NortheastDianliUniversity,Jilin132012,JilinProvince,China)

Since current conventional negative selection algorithm does not pay attention to the occurrence of autoimmune detector, and the presence of autoimmune detector will reduces the accuracy of fault diagnosis and other analogous areas, a method which can discover and eliminate pathogenicity detector was proposed.We specially designed a rule to detecting the presence of pathogenicity detector.With the help of MATLAB software, we simulated irregular distributed self-data, annulus distributed self-data and nearly circle distributed self-data.Results show that our method can effectively eliminate 90% of the pathogenic detector, enhance the robustness and adaptive ability of the immune negative selection algorithm.

artificial immune system; negative selection; autoimmune detector; algorithm optimization; algorithm simulation

2013-12-17.

门 洪(1973—), 男, 汉族, 博士, 教授, 从事智能化测控技术、新型传感器和图像处理的研究, E-mail: menhong_bme@163.com.通信作者： 陈 鹏(1990—), 男, 汉族, 硕士研究生, 从事模式识别方法和仿生智能计算的研究, E-mail: chenpeng16899199@126.com.

吉林省科技发展计划项目(批准号： 20130101053JC).

TP18

A

1671-5489(2014)06-1255-06

10.13413/j.cnki.jdxblxb.2014.06.28

韩 啸)