第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/i.i8sn.1673-4785.2011.02.014 一种可变模糊匹配阴性选择算法 王辉，于立君，王科俊，张利军 (哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：通过对人工免疫系统中阴性选择算法机理的分析，定义了连续相似度与背离度，提出了一种可变模糊匹配 阴性选择免疫算法.算法通过调整匹配阈值的方法降低黑洞数量；利用模糊思想，实现了具有一定连续相似度的模 糊匹配，模糊程度可控；为了消除检测器间的冗余，提高检测器集的检测效率，算法在模糊匹配的基础上，生成了有 效检测器集.仿真实验表明，可变模糊匹配阴性选择算法生成的成熟检测器检测范围较大，空间覆盖率明显提高，黑 洞数量大幅下降，算法具有较强的鲁棒性. 关键词：阴性选择；连续相似度；模糊匹配；黑洞；有效检测器集 中图分类号：TP301文献标识码：A文章编号：16734785(2011)02-017807 An adjustable fuzzy matching negative selection algorithm WANG Hui,YU Lijun,WANG Kejun,ZHANG Lijun (College of Automation,Harbin Engineering University,Harbin 150001,China) Abstract:This paper analyzed the negative selection algorithm mechanism in an artificial immune system,defined continuous similarity and deviation,and put forward an adjustable fuzzy matching negative selection immune algo- rithm.The algorithm clearly reduced the number of holes through adjusting the matching threshold,and used a fuzzy idea to realize fuzzy matching with continuous controlled similarity.In order to eliminate the redundancy phe- nomenon between detector sets and increase the detecting efficiency,an effective detector set was created on the ba- sis of fuzzy matching.The simulation results show that the mature detector generated by the adjustable fuzzy matc- hing negative selection algorithm can detect data in a larger range and the space coverage ratio is noticeably in- creased.Also,the number of holes clearly declines,and the algorithm has better robustness. Keywords:negative selection;continuous similarity;fuzzy matching;holes;effective detector sets 生物免疫系统是一个自适应和自组织的系统，足：检测黑洞数量较大，且检测率与字串长度呈线性 具有强大的信息处理能力.生物免疫系统的主要作 关系，进而检测器集与自我集规模呈指数级代价关 用是能够辨别“自己”与“异己”物质，只对非自体成 系.在阴性选择算法的基础上，l996年由Dhaeseleer 份的抗原作出免疫应答，对“自体”成份形成免疫耐 等人[2]提出2个异常检测器产生算法，检测器与输 受，并具有排除与记忆非己的功能.而阴性选择 入规模呈线性时间比例关系；Kim和Bentley提出了 算法是免疫系统识别非自体，对自体形成自我耐受 在克隆选择中嵌入阴性选择算子的思想，并验证了 的关键所在，因此成为核心免疫算法之一，其性能对 其可行性3]：罗一丹等人提出了一种基于免疫重构 整个免疫系统具有重要意义. 的阴性选择算法4，以保证系统发生意外的时候能 阴性选择算法的一个主要优点就是在未知的状 够及时恢复、重组；蔡自兴等人提出一种基于 态下可以对非我模式进行有效的防御，但也存在不 (+入)进化策略的阴性选择算法5]，进而使得检 测器的搜索不再盲目. 收稿日期：200909-15 基金项目：国家自然科学基金资助项目(60704004)；黑龙江省博士后 本文对阴性选择算法进行了深入研究，针对算 基金资助项目(LBH-Z09216);中央高校基本科研业务费 法在匹配规则及检测器集等方面存在的不足，提出 专项基金资助项目(HEUCF00401). 通信作者：王辉.E-mail:wangh@hrbeu.eu.cn. 一种可变模糊匹配阴性选择免疫算法.匹配规则采
第2期 王辉，等：一种可变模糊匹配阴性选择算法 ·179… 用变阈值思想，通过阈值r的调整来减少“黑洞”的 符串Z在T中对应位置上所包含的一系列子串，则 数量.为了提高检测器集的检测效率，利用模糊思 模式串T和Z的连续相似度记为lxsd(Z,T),计算 想，提出了连续相似度与背离度的概念，实现了模糊 式(2)： 匹配，并生成了有效检测器集，提高了系统的检测效 Ixsd(Z,T)=max(Len(Thik;))/Len(T).(2) 率和性能， 式中：max(Len(T,))表示所有连续相同子串长度 的最大值.例如，串B:0111001011001,串Z: 1阴性选择算法及其存在的问题分析 0100110111000,其连续相似度为xsd(Z,B)=max 免疫系统首要任务就是能够区分自己和非己物 (24)/13=4/13=0.3077. 质，并通过免疫应答来发现外来入侵，执行免疫功 定义3背离度.设模式串T=‘t1…tn’和目 能6，这就是免疫系统的自体-非自体识别原理. 标串Z=‘2云n’均为二进制字符串，则字符串Z 1994年Forrest等人[78]基于此原理提出了阴性选择 与模式串T的背离度定义为bld(Z,T)= 算法，实现了自体耐受， 1-xsid(Z,T)=1-ELen(Thi /Len(T). 阴性选择算法描述如下： 例如，对于上述串B和串Z,则背离度为bld 随机生成未成熟检测器； (Z,B)=1-xsid(Z,B）=1-∑Len(Bi,g)/ While(成熟检测器集合还没有产生) Len(B)=1-(2+4)/13=0.5385.背离度体现了2 {计算一个未成熟检测器与自体的亲和力； 个字符串的完全背离程度，即2个字符串对应位不 (未成熟检测器与自体集匹配)该检测器 相同的字符所占的比例 不能成熟； 定义4匹配.在一定匹配规则下，2个模式串 else该检测器成熟，加入到检测器集合中； T和Z的连续相似度超过匹配阈值r/Len(T),则称 . T和Z匹配，记为Ppei(T,Z) 利用经过耐受的成熟检测器集识别非自体，利 2.2算法描述 用阴性选择算法可以在没有先验知识的情况下，对 可变模糊匹配阴性选择算法分2部分，第1部 未知入侵进行有效防御.因此，阴性选择算法主要应 分为可变模糊匹配算法实现，第2部分为生成有效 用在异常检测方面，但在检测过程中存在“黑洞”问 检测器集算法实现9. 题.黑洞的存在取决于模式集的结构及模式匹配所 可变模糊匹配算法实现， 采用的匹配规则6].自我模式集与非我模式集越相 1)定义自我集S为长度L的字符串集， 似，黑洞的数量就会越多.由于黑洞不可能被任何检 2)设置初始阈值r1,计算bldf(背离度阈值)及 测器检测到，因此应尽可能减少黑洞的数量及其出 xsdf(连续相似度阈值). 现的概率， 3)随机生成长度为L的未成熟检测器A,将A 依次与自我集S进行模糊匹配. 2可变模糊匹配阴性选择算法 4)若A未与自我集发生任何匹配，则A成熟， 2.1相关定义 将A及其匹配阈值加入到检测器集中、若检测器个 定义1相似度.设模式串T=‘t2…tn’和目 数已达到要求，转到7)；否则，转到3)· 标串Z=‘a12名n’均为二进制字符串，字符串Z与 5)否则，S中还有未与A进行匹配操作的个体， 模式串T的相似程度记为xsid(Z,T),计算式(1)： 计算A与S中未操作的当前个体的相应背离度.若 xsid(Z,T)=>Len(Thihi)/Len(T).(1) 背离度超过阈值，转到4)；否则，计算连续相似度. 式中：T,为字符串Z在T中对应位置上所包含的 6)若连续相似度未超过阈值，转到4)：超过阈 一系列子串TL,2,T8,4,…,TM,g(1≤h1≤h2T。,转到3)，否则，转 h4,…<h.≤h,≤n),Len表示字符串的长度.显然当 到4). xsid(Z,T)=1时，Z=T,Z与T精确匹配 7)生成有效检测器集. 定义2连续相似度.对于2个模式串T=‘t2 算法流程图如图1所示。 …tn’和Z=‘a12zn’,设TM(1≤h:≤h,≤n)为字
·180. 智能系统学报 第6卷 定义自我集S 定义初始匹配阙值r、bldf、lxsf 随机生成字符A 4与S进矿模糊匹配 A与S中所行个体 都进行了模糊匹配 A成熟将A及 IN 匹配阈值加人 计算4与S当前个体的背离度 到检测器十 Bld(A.S)>bldf 检测器个数是 否达到要求？ IN Lxsd(A.S)>Ixsdf Y Y 生成行效 调整L配阀值，计算bld 检测器集 R'>r 结束 图1可变模糊匹配阴性选择算法流程 Fig.1 The flow chart of the adjustable fuzzy matching negative selection algorithm 可变模糊匹配阴性选择算法在检测过程中通过 器集（由第一部分可变模糊匹配算法生成），为检 不断地调整匹配阈值使黑洞中的字符被检测到，从 测器个数，C[]为当前待操作检测器，C[k]为C剩 而降低黑洞的数量.匹配阈值按r:=T:-1+1的规则 余未操作检测器，算法描述如下： 调整，调整范围为[r,r+C-1],并根据匹配阈值的 1)设置初始阈值r,计算bldf; 变化调整连续相似度.对于不匹配的子串，其长度越 2)C[门与C[k]进行匹配测试； 大，背离度就越大，当背离度超过背离度匹配阈值 3)若C[]通过了匹配测试，则C[]成熟，加入 时，该字符串成熟这种匹配是模糊的，其相似度是 到有效检测器集D中，转到6)； 可控的，并且带有可调的控制参数，可以根据参数控 4)否则取下一个C[k]与C[]进行匹配测试， 制模糊程度，从而使得该算法检测范围较大，具有较 设置lxsd与bld初值，并计算C[i]与当前C[]的 强的鲁棒性。 lxsd与bld; 可变模糊匹配阴性选择算法产生的检测器集是 5)若bld=r/Len(C[i])条 由不同匹配阈值的检测器构成的.匹配阈值可变使 件成立，删掉C[门，转到6)；否则转到3)； 检测器集中检测器个数增多，检测范围增大.普通阴 6)若检测器集合C中的每一个C[]都进行了与 性选择算法生成的检测器集中只有惟一的匹配阈 C[]的匹配测试，算法结束，所生成的D为有效检测 值，检测范围固定，由此可见，普通阴性选择算法是 器集合：否则，转到2). 可变模糊匹配阴性选择算法的一个特例. 算法流程图如图2所示 生成有效检测器集算法其中，C为待操作检测
第2期 王辉，等：一种可变模糊匹配阴性选择算法 ·181· 输人检测器集C及个数n 初始化r、bldf 入 设置循环变量1、k 取当前检测器C与Q匹配测试 C[与所行Ck都匹配 IN 设置lxsd、bld的初值 C成熟，加入 到有效检测器 计算C[i与C[k]的lxsd、bld 集D中 N Bld=r/len(C[i]) Y 删掉C) 每个Q都进行了测试 结束 图2有效检测器算法流程图 Fig.2 The flow chart of the effective detector 匹配操作在可变模糊匹配阴性选择算法中，是一 的概率设为P,则有 个关键操作：生成检测器集时，匹配用于判断检测器是 Pw=(1++1)2-(l-7)21= 否成熟；实施检测操作时，匹配用于识别异常模 式0”.由于自我集具有一定的相似性，因而基于自我 2+ (3) 集产生的成熟检测器之间可能存在匹配的现象检测 式中：l为字符串的长度 器之间互相匹配，使得它们检测空间基本相同，等同于 设产生一个成熟检测器的概率为P,即一个随 一个检测器的作用，因而检测效率大大降低由于冗余 机串经可变模糊匹配阴性选择算法后成为成熟检测 的检测器并不能增加检测器集的整体覆盖空间，因而 器的概率.则P.应满足 要去掉冗余，提高效率有效检测器集生成算法正是基 PR=(1-PM)+P(1-P2)+ 于此思想设计的，算法消除了检测器之间的匹配现象， PMnP(1+Pa)+·+ 使系统的空间覆盖率达到最大， PPMn…PMc-)(1-Pwc）= 3仿真分析 1-PwP2PB…PMc-)PMc 从式(3)中可以看出，通过可变模糊匹配阴性 算法仿真时采用randerr(1200,32,[0:32])函 选择算法产生个成熟检测器的概率比普通阴性选 数随机生成1200个二进制串作为自我集N,字符串 择算法要高.这是因为可变模糊匹配阴性选择算法 长度L=32,并仿真分析了采用可变模糊匹配阴性 有多个可调的匹配阈值，从而使一个随机串成为检 选择算法后检测器数目、检测率及黑洞数目的变化 测器的概率提高. 情况.其中Nm为待检测的检测器数目，NR为由算法 下面分析不同匹配阈值的检测器分布概率 生成的检测器数目，P为2个随机串互相匹配的概 在匹配阈值为：时，对于某一未成熟检测器不 率，f为随机串不与N匹配的概率，P为漏报率，P, 与自我集匹配的概率为 为检测率. f=(1-P)% 3.1成熟检测器生成的概率分析 成为匹配阈值：的成熟检测器的概率为 在连续：位匹配规则下2个随机串互相匹配 P:=(1-f)(1-f)…(1-f-)f
·182 智能系统学报 第6卷 则不同匹配阈值的检测器的分布满足 0.96 Ns=NP· 0.94 0.92 仿真时，随机生成10000个未成熟检测器，即 解0.90 Nm=10000,当最大匹配阈值在T.=14~20之间变 0.88 化时，不同匹配阈值的检测器分布情况如图3所示. 0.86 5.0r 0.84 +200 4.5 ◆ 0.82 量-800 4.0 +-=14 士-1400 3.5 -r=15 0.80 滋 士r=16 31415161718192021 3.0 r=17 最大匹配阀值： 2.5 -"=18 2.0i ◆=19 +-=20 图4不同自体下最大匹配阑值与检测率的关系 1.5 1.0 Fig.4 The function between maximum matching 0.5 三三三 threshold and detection rate with different 1314151617181920 autologous amount 最人匹配阙值： 3.3检测器覆盖空间对比分析 图3成熟检测器分布图 用随机函数randerr()生成自我集，并构造模式 Fig.3 The mature detector 空间.N,为40个长度为L=13的二进制串，则其模 式空间共有8192个模式串.由于可变模糊匹配阴性 从图3中可以看出，表示某一匹配阈值的成熟 选择算法在产生检测器集时匹配阈值是变化的（例 检测器数目的曲线较平缓，并没有随着最大匹配阈 如r=7~11),而普通阴性选择算法匹配阈值固定 值的增加而增大，说明检测器集中某一匹配阈值的 (如r=7),因此可变检测器集中的检测器个数要远 成熟检测器的数目与最大匹配阈值无关，且数目基 远多于普通阴性选择算法所产生的检测器个数，进 本固定.匹配阈值小的成熟检侧器较多，因而能够覆 而可变检测器集的覆盖空间要远大于普通阴性选择 盖较大的模式空间；匹配阚值大的成熟检测器较少， 算法的，为了进一步增加可变检测器集空间覆盖率， 因而它能够检测到的异已模式较少，专一性较强.匹 本文生成了有效检测器集，下面对比分析可变检测 配阈值为模式串长度时所产生的成熟检测器，只能 器集与有效检测器集的覆盖空间. 检测到一个“非己”模式，专一性最强.因此可变模 用可变模糊匹配阴性选择算法分别产生含有 糊匹配阴性选择算法实现了以较小的检测器集合， 21~29个检测器的检测器集(r=7,最大匹配阈值 检测到较大范围的“非己”行为。 。=11),并对每一个检测器集生成对应的有效检测 3.2检测率 器集，对应的覆盖空间进行比较，如图5所示 由分析可知，漏报率P满足 P=(1-P)m+(1-P2)e+ 610 …+(1-PMc)Nc. 回 则检测率为 P,=1-P=1-(1-P4,)m-(1-P,)- …-(1-PMe)c ◆一可变检测器 一有效检测器 仿真中，利用上述实验产生的检测器，分别对含 20212223242526272829 有“异己”字符串的自体个数为200、800、1400的自 检测器个数 我集进行检测，得出不同的最大匹配阈值与检测率 图5覆盖空间的比较 的关系，如图4所示 Fig.5 Comparison of the space coverage 从图中可以看出，检测率随着最大匹配阈值的 从图5可以看出，可变模糊匹配算法的检测器 增加而增大，而与自体个数无关，只要检测器集中检 集与有效检测器集的覆盖空间均有跳变现象，且从 测器个数固定，检测率就固定.图中3条曲线并没有 表面上看，有效检测器集的整体覆盖空间要低于可 完全重合，这与自我集的分布有关.最大匹配阈值为 变检测器集的覆盖空间.这是因为由可变检测器集 13时的检测率最低，说明可变模糊匹配阴性选择算 生成的有效检测器集中，成熟检测器的个数明显减 法的检测率高于普通阴性选择算法， 少，如表1所示
第2期 王辉，等：一种可变模糊匹配阴性选择算法 ·183 表1检测器个数对比表 洞数量迅速下降，这是主要是因为匹配阈值的可调 Table 1 Comparison of the number of detectors 性，使得大匹配阈值的检测器加入到检测器集中.而 原检测器个数 有效检测器个数■ 匹配阈值较大的检测器检测专一性较强，因而使一 21 13 2 15 些原本是黑洞的模式被检测到，从而使黑洞数量下 2 14 降，检测范围扩大.当r。=18时的黑洞数量又有所 24 5 25 17 增加，这主要是由于自我集分布的特点导致的， 2 15 27 14 4结束语 28 18 29 19 阴性选择算法是人工免疫系统中的核心算法， 从表1可以看出，随着原检测器个数的增加，有 其性能的改进对系统具有重要的意义.为了降低黑 效检测器的个数并不是按比例变化，因此出现了图 洞的数量并提高检测率，提出了一种可变模糊匹配 5中有效检测器覆盖空间的跳变现象.为了更好地 阴性选择算法.算法通过调整匹配阈值，并采用相似 分析2种检测器集的空间覆盖率，在检测器个数相 度可控的模糊匹配，使黑洞的数量大幅降低.算法具 同的情况下进行实验对比，结果如图6所示. 有有效检测侧器集，消除了原检测器集中存在的冗余 120 现象，使每个检测器的覆盖空间都能达到最大.仿真 100 实验表明，该算法与普通阴性选择算法相比，具有较 80 润 高的检测率和较少的黑洞数量，覆盖空间明显提高， 60 ◆ 实现了以较小的有效检测器集合，检测到较大范围 40 ◆一可变检测器 的异己行为. 201 ■一有效检测器 20212223242526272829 参考文献： 检测器个数 [1]王辉，王科俊，莫宏伟，等.人工免疫系统及其在控制系 图6相同个数的检测器覆盖空间的比较 统中的应用研究[J].哈尔滨工程大学学报，2007(11)： Fig.6 The comparison of the space coverage with same 1222-1227. detectors WANG Hui,WANG Kejun,MO Hongwei,et al.An im- 从图6可以看出，在检测器个数相同的情况下， mune negative selection algorithm with an adjustable thresh- 有效检测器集的覆盖空间整体高于可变检测器集 old based on fuzzy logic[J].Joumal of Harbin Engineering 的.有效检测器集在检测器个数为28、29时也出现 University,2007(11):1222-1227. 了下降的趋势，这主要是由于检测器集在生成时的 [2]D'HAESELEER D,FORREST S,HELMAN P.An immu- 随机性造成的. nological approach to change detection:algorithms,analysis 3.4黑洞分析 and implications[C]//Proceedings of the 1996 IEEE Sym- 黑洞的数量主要取决于匹配规则及匹配规则下 posium on Research in Security and Privacy.Los Alamitos, 的匹配阈值.根据文献[11]给出的基于连续位匹配 USA:IEEE Computer Society Press,1996:215-220. 规则下的黑洞计算方法，实验计算了最大匹配阈值 [3]BENTLEY P J,GORDON T,KIM J.New trends in evolu- 不同时黑洞的数量，如表2所示. tionary computation [C]//The Congress on Evolutionary 表2最大匹配阑值不同时黑洞数量 Computation(CEC-2001).Seoul,Korea,2001:162-169. Table 2 The number of holes with deifferent maximum [4]罗一丹，蔡自兴，王勇，等.基于免疫重构的阴性选择算 matching threshold 法[J].计算机科学，2008,35(3)：149-151 最大匹配阙值。 黑洞数量/103 LUO Yidan,CAI Zixing,WANG Yong.Negative selection 4 276 219 algorithm based on immune reconfiguration[J].Computer 15 16 74 Science,2008,35(3):149-151. 12 40 [5]肖赤心，蔡自兴，王勇，等.进化策略用于阴性选择算法 18 68 [J].小型微型计算机系统，2008(11)：2091-2094. 19 31 20 19 XIAO Chixin,CAI Zixing,WANG Yong,et al.Application 21 90 of evolutionary strategy to negative selection algorithm[J]. 从表中可以看出，随着最大匹配阈值的增加黑 Joural of Chinese Computer Systems,2008(11):2091-
·184, 智能系统学报 第6卷 2094. 作者简介： [6]莫宏伟.人工免疫网络记忆分类器原理与应用研究 王辉，女，1976生，副教授，主要研 [D].哈尔滨：哈尔滨工程大学，2005：5658. 究方向为先进控制理论及应用、智能控 MO Hongwei.Research of the principles and applications of 制、人工免疫.连续五年获哈尔滨工程 artificial immune network memory classifier[D].Harbin: 大学优秀主讲教师，2009年获哈尔滨工 Harbin Engineering University,2005:56-58. 程大学自动化学院首届教学名师奖，被 [7]FORREST S,HOFMEYR S A.SOMAYAJI A.LONG- 评为2010年度学生最喜爱的教师，发 STAFF T A.Asense of self for unix proceedings of the 1996 表学术论文40余篇，其中EI检索10余篇，编著教材4部. IEEE Symposium on Security and Privacy,Los Alamitos, CA,1996:120-128. 王科俊，男，1962年生，教授、博士 [8]FORREST S,PERELSON A S,ALLEN L,CHERUKURI 生导师、博士，哈尔滨工程大学自动化 R.Selfnonself discrimination in a computer[C]//Proceed- 学院副院长，模式识别与智能系统学科 ings of the 1994 IEEE Symposium on Security and Privacy. 带头人.主要研究方向为模糊混沌神经 Los Alamitos,USA,1994:202-212. 网络、自适应逆控制理论、可拓控制、网 [9]王辉.可变模糊匹配阴性选择免疫算法研究[D].哈尔 络智能控制、模式识别、多模态生物特 滨：哈尔滨工程大学，2008：21-25. 征识别、联脱机指纹考试身份鉴别系统、微小型机器人系统 WANG Hui.Research on the adjustable fuzzy matching neg- 等.完成科研项目20余项，目前在研项目10余项.曾获得部 ative selection immune algorithm[D].Harbin:Harbin En- 级科技进步二等奖2项、三等奖3项，省高校科学技术一等 gineering University,2008:21-25. 奖1项、二等奖1项.发表学术论文180余篇，出版学术专著 [10]罗文坚，曹先彬，王煦法.检测器自适应生成算法研究 3部、国防教材1部，主审教材2部。 [J].自动化学报，2005,31(6)：907-916. LUO Wenjian,CAO Xianbin,WANG Xufa.Research on 于立君，男，1975年生，副教授，博 adaptively generating detector algorithm[J].Acta Auto- 士，主要研究方向为船舶姿态控制、先 matica Sinica,2005,31(6):907916. 进控制理论及应用。荣获黑龙江省科 [11]张剑，何华灿，赵敏.免疫计算中复合检测集生成算法 技进步二等奖、校三育人先进个人、校 [J].计算机工程与应用，2004,28：5-11. 先进工作者、校优秀主讲教师等多项荣 ZHANG Jian,HE Huacan,ZHAO Min.Compound detec- 誉。参加省部级科研项目5项、承担省 tor set:detectors with different affinity[J.Computer En- 博士后基金1项、中央高校自由探索计划项目2项。发表学 gineering and Applications,2004,28:5-11. 术论文30余篇，其中被EI检素8篇，出版著作2部。 [12]DHAESSELEER P.Further efficient algorithms for genera- ting antibody string technical Report CS95-03[R].Albu- querque USA:The University of New Mexico,1995