（计算机应用技术专业论文）实值检测器生成算法研究.pdf

摘要 摘要 人工免疫系统是借鉴生物免疫系统中的信息处理机制而设计的模型和算法， 提供了一种解决复杂计算问题的新颖途径。目前，人工免疫系统在诸如故障检测、 数据挖掘、优化等多个领域中表现出了很强的问题求解能力。 非选择算法是人工免疫算法中的重要分支之一。此算法可以分为以下三个步 骤，即定义自我集、检测器生成、使用生成的检测器进行检测。其中，检测器生 成算法是非选择算法的核心部分。检测器生成算法早期的研究主要是着眼于离散 空间，但自2 0 0 2 年实值非选择算法被提出后，越来越多的工作开始关注实值检 测器生成算法的研究。 本文主要的研究内容如下： ( 1 ) 提出了一种新的基于划分测试的实值检测器生成算法( r e a l v a l u e d d e t e c t o rg e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n t e s tp r o e s s ：p t - r n s a ) 。 与传统的实值非选择算法相比，f f - r n s a 是一种确定性的算法，可以确保 除边界区域外的非我区域均可被成熟检测器覆盖。通过与v - d e t e c t o r 算法的实验 对比，p t - r n s a 显示了其在检测率与成熟检测器生成代价方面的竞争力。但是 与v - d e t e c t o r 相比，仍有不足，主要是要达到比较高的检测率，其所需的成熟检 测器数目非常多。 ( 2 ) 在p t - r n s a 算法的基础上，提出了基于划分测试扩展的算法 ( r e a l - - v a l u e dd e t e c t o rg e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n t e s t s p r e a d p r o e s s ：p t s r ns _ a ) 。 p t s r n s a 在划分测试的基础上，引入了扩展策略，在保持p t - r n s a 原有 算法特性的前提下，减少了所需的成熟检测器个数。实验结果显示，p t s r n s a 算法比p t - r n s a 有了较大改善。与此同时，与v - d e t e c t o r 算法的实验比较结果 说明，p t s r n s a 具有较好的竞争力。 总的来说，本文针对于实值非选择算法的检测器生成问题，提出了基于划分 测试的算法和基于划分测试扩展的算法，并用实验结果证明了算法的有效性。 这些工作不仅对非选择算法的进一步研究具有一定的意义，而且对于人工免疫系 统的算法研究和实际应用具有参考价值。 关键词：人工免疫非选择算法检测器生成算法实值检测器生成 a b s t r a c t a b s t r a c t a r t i f i c i a li m m u n es y s t e m ( a i s ) i si n s p i r e db yt h eb i o l o g i c a li m m u n es y s t e m ， a n dp r o v i d e san o v e lw a yt os o l v ec o m p l e xc o m p u t a t i o n a lp r o b l e m s s of a r , i th a s b e e na p p l i e di nm a n yf i e l d s ，i n c l u d i n gf a u l td e t e c t i o n ，d a t ap r o c e s s i n g ，o p t i m i z a t i o n ， a n ds o o n t h en e g a t i v es e l e c t i o na l g o r i t h m ( n s a ) p r o p o s e db ys f o r r e s ta n dh e r c o l l e a g u e si so n eo ft h em o s ti m p o r t a n tb r a n c h e si na r t i f i c i a li m m u n es y s t e m c o m m u n i t y i tc a nd i s t i n g u i s ht h ea n o m a l yf r o mt h en o r m a l ，w h i l eo n l yt h en o r m a l i n f o r m a t i o ni sn e e d e d t h en o r m a li so f t e nd e f i n e da st h es e l f , a n dt h ea n o m a l y b e l o n g st ot h en o n - s e l t h ed e t e c t o rg e n e r a t i o na l g o r i t h mi st h ec o r ec o m p o n e n to f t h en s a s ，a n di th a sb e e ns t u d i e df o ry e a r s m o s to fe a r l i e rw o r k sa v em a i n l yf o c u s e d o nt h ed i s c r e t es p a c e ，e s p e c i a l l yt h eb i n a r ys p a c e h o w e v e r , g o n z a l e ze ta 1 a n a l y z e d t h eb i n a r ym a t c h i n gr u l ei nn s a s ，a n dp o i n t e do u tt h a tt h eb i n a r yr e p r e s e n t a t i o n c a n n o tc a p t u r ea d e q u a t ei n f o r m a t i o nt os o l v es o m er e a l - v a l u e dp r o b l e m s t h e r e f o r e ， t h eb i n a r yr e p r e s e n t a t i o ni sn o tf i tf o rs o m er e a l w o r l da p p l i c a t i o n s t os o l v es u c h p r o b l e m s ，t h er e a l - v a l u e dn e g a t i v es e l e c t i o na l g o r i t h m ( r n s a ) i sp r o p o s e db y g o n z a l e ze ta l f r o mt h e no n ，t h er n s a sh a v es h o w ni t s p o t e n t i a lp o w e ri n r e a l - w o r l da p p l i c a t i o n s t h ef o l l o w i n gi st h em a i nw o r ks t u d i e di nt h i sp a p e r ( 1 ) an o v e ld e t e c t o rg e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n t e s tp r o c e s sf o i r e a l v a l u e dn e g a t i v es e l e c t i o na l g o r i t h m s ，i e t h ep t - r n s a ，i sp r o p o s e d t h e p t - r n s ai sad e t e r m i n i s t i ca l g o r i t h m i tc a ne n s u r et oc o v e rt h ew h o l e n o n s e l f s p a c e e x c e p tt h eb o u n d a r ya r e a i nt h i sp a p e r , t h ep e r f o r m a n c eo ft h ep t - r n s ai sc o m p a r e d w i t ht h ev - d e t e c t o ra l g o r i t h m ，w h i c hi st h es t a t e o f - t h e a r td e t e c t o r g e n e r a t i o n a l g o r i t h mf o rr n s a s e x p e r i m e n t a lr e s u l t s d e m o n s t r a t et h a tt h ep r i 乇n s ai s c o m p e t i t i v e h o w e v e rt h en u m b e ro ft h em a t u r ed e t e c t o r so ft h ep t - r n s am a yb e l a r g ec o m p a r e dw i t ht h ev - d e t e c t o ra l g o r i t h m ( 2 ) a ni m p r o v e da l g o r i t h mo fp t - r n s ai sp r o p o s e d ，w h i c hi sb a s e do nt h e p a t i t i o n t e s t s p r e a dp r o c e s s ，i e t h ep t s r n s a e x p e r i m e n t a lr e s u l t sd e m o n s t r a t e t h a tt h en u m b e ro ft h em a t u r ed e t e c t o r si sl e s st h a nt h a to fp t - r n s a b y c o m p a r i n g w i t ht h es t a t e o f - t h e - a r ta l g o r i t h m ，i e t h ev - d e t e c t o ra l g o r i t h m ，e x p e r i m e n t a lr e s u l t s d e m o n s t r a t et h a tt h ep e r f o r m a n c eo f t h ep t s r n s ai sv e r yc o m p e t i t i v e i i a b s t r a c t o v e r a l l ，i nt h et h e s i s ，w i t ht h er e s e a r c h e si nr e a l v a l u e dn e g a t i v es e l e c t i o n a l g o r i t h m s ，t h ep t - r n s aa n dt h ep t s r n s aa r ep r o p o s e d a n dt h ee x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h ea l g o r i t h m sa r ee f f e c t i v e t h i sw o r kn o to n l yh a sc e r t a i n s i g n i f i c a n c et of u r t h e rr e s e a r c ho ft h en s a s ，b u ta l s oh a sr e f e r e n c ev a l u ef o rt h e a l g o r i t h mr e s e a r c ha n dt h er e a l - w o r l da p p l i c a t i o n so f a i s s k e yw o r d s ：a r t i f i c i a li m m u n es y s t e m ，n e g a t i v es e l e c t i o na l g o r i t h m ，r e a l v a l u e d n e g a t i v es e l e c t i o na l g o r i t h m ，r e a l v a l u e dd e t e c t o rg e n e r a t i o na l g o r i t h m i i i 插图目录 插图目录 图1 1 非选择算法流程图2 图2 1p t - r n s a 核心思想7 图2 2 二维空间长方形的表示8 图2 3 二维空间的划分测试过程8 图2 4p t - r n s a 在二维空间中实现时的伪代码1 0 图2 5 候选检测器与自我区域的关系l l 图2 6 成熟检测器随的变化关系1 4 图2 7 固定成熟检测器数目1 6 图2 8 固定自我半径2 2 图2 9 长方形与圆的外切正方形相交情况2 7 图2 1 0 判断长方形与圆是否相交的伪代码2 8 图2 1 1v - d e t e c t o r 生成检测器的分布与p t - r n s a 生成检测器的分布2 8 图2 1 2 合并检测器2 9 图3 1p t s - r n s a 核心思想3 0 图3 2p t s r n s a 二维空间划分- 钡4 试- 扩展过程3 l 图3 3a 类的四种情况3 3 图3 4a 类各情况所采取的扩展策略3 3 图3 5b 类的六种情况3 4 图3 6b 类各情况所采取的扩展策略3 5 图3 7c 类的四种情况3 6 图3 8c 类各情况所采取的扩展策略3 6 图3 9c 类两种不同的扩展方式3 7 图3 1 0 二维空间中p t s r n s a 算法实现伪代码3 9 图3 1 l 确定。l 的值。4 0 图3 1 2p t - r n s a 与p t s - r n s a 生成检测器集的对比( c r o s s 数据集) 4 1 图3 1 3p t - r n s a 与p t s r n s a 生成检测器集的对比( r i n g 数据集) 4 3 图3 1 4 检测率与误报率5 9 v i 第1 章绪论 表2 1 表2 1 表2 1 表2 1 表2 2 表2 2 表2 2 表2 2 表3 1 表3 2 表3 3 表3 4 表3 5 表3 6 表3 6 表3 6 表3 6 表3 7 表3 7 表3 7 表3 7 表3 8 表3 8 表3 。8 表3 8 表3 9 表3 1 0 表3 1 1 表格目录 p t - r n s a 与v - d e t e c t o r 4 9 】比较( o 0 1 0 0 5 ) 1 7 p t - r n s a 与v - d e t e c t o r 4 9 l v , 较( 0 0 6 ，s o 1 0 ，续表) 1 8 p t - r n s a 与v - d e t e c t o r 4 9 比较( o 1 1 厂s o 1 5 ，续表) 1 9 p t - r n s a 与v - d e t e c t o r 4 9 比较( 0 1 6 r s o 2 0 ，续表) 2 0 p t - r n s a 与v - d e t e c t o r 5 0 】比较( o 0 l ，| o 0 5 ) 2 3 p t - r n s a 与v - d e t e c t o r 5 0 】比较( o 0 6 r l o 1 0 ，续表) 2 4 p t - r n s a 与v - d e t e c t o r 5 0 比较( o 1 1 0 1 5 ，续表) 2 5 p t - r n s a 与v - d e t e c t o r 5 0 】比较( o 1 6 r s o 2 0 ，续表) 2 6 a 类每一种具体情况下检测器扩展前后的关系3 4 b 类每一种具体情况下格子合并前后的关系3 5 c 类每一种具体情况下检测器扩展前后的关系3 7 p t - r n s a 与p t s - r n s a 比较( c r o s s 数据集) 4 2 p t - r n s a 与p t s r n s a h ：较( r i n g 数据集) 4 4 p t s r n s a 与v - d e t e c t o r 5 0 比较( o o l 厂s 0 0 5 ，c r o s s 数据集) 4 6 p t s - r n s a 与v - d e t e c t o r 5 0 比较( 0 0 6 如0 1 0 ，c r o s s 数据集，续表) 4 7 p t s - r n s a 与v - d e t e c t o r 5 0 e l 较( o 1 1 ，s o 1 5 ，c r o s s 数据集，续表) 4 8 p t s r n s a 与v - d e t e c t o r 5 0 】比较( 0 1 6 r l o 2 0 ，c r o s s 数据集，续表) 4 9 p t s - r n s a 与v - d e t e c t o r 5 0 】比较( o 0 l o 0 5 ，r i n g 数据集) 5 0 p t s r n s a 与v - d e t e c t o r 5 0 比较( o 0 6 r s o 1 0 ，r i n g 数据集，续表) 5 1 p t s r n s a 与v - d e t e c t o r 5 0 比较( o ，l l ，s o 。1 5 ，r i n g 数据集，续表) 。5 2 p t s r n s a 与v - d e t e c t o r 5 0 】比较( 0 1 6 ，。o 2 0 ，r i n g 数据集，续表) 5 3 p t s - r n s a 与v - d e t e c t o r 5 0 l l 较( 0 0 l 圪0 0 5 ，t r i a n g l e 数据集) 5 4 p r s r n s a 与v - d e t e c t o r 5 0 1 比较( 0 0 6 厂s 0 1 0 ，t r i a n g l e 数据集，续表) 。5 5 p t s r n s a 与v - d e t e c t o r 5 0 较( o 1 1 ，s 0 1 5 ，t r i a n g l e 数据集，续表) 5 6 p t s - r n s a 与v - d e t e c t o r 5 0 】比较( 0 1 6 ，l o 2 0 ，t r i a n g l e 数据集，续表) 5 7 检测率、误报率与自我半径关系( c r o s s 数据集) 5 8 检测率、误报率与自我半径关系( r i n g 数据集) 5 8 检测率与误报率6 0 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特- 3 t ) t l 以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 年 罗及吃 鲈7 7 第1 章绪论 第1 章绪论 人工免疫系统借鉴了生物免疫系统的信息处理机制，提供了一种解决复杂计 算问题的新颖途径。目前，人工免疫系统在诸如故障检测、数据挖掘、优化等多 个领域中表现出了很强的问题求解能力。非选择算法、克隆选择算法以及免疫网 络算法是人工免疫系统的三个主要分支。 非选择算法是人工免疫算法中的重要分支之一。此算法可以分为以下三个步 骤，即定义自我集、检测器生成、使用生成的检测器进行检测。其中，检测器生 成算法是非选择算法的核心部分。检测器生成算法早期的研究主要是着眼于离散 空间，但自2 0 0 2 年实值非选择算法被提出后，越来越多的工作开始关注实值检 测器生成算法的研究。本文主要研究了实值检测器生成算法。 本章首先对非选择算法进行概述，给出其基本框架和分类；其次分别介绍了 基于离散表示的非选择算法和基于实值表示的非选择算法；然后给出了本文的主 要研究内容及组织安排；最后是本章小节。 1 1 非选择算法概述 非选择算法( n e g a t i v es e l e c t i o na l g o r i t h m ：n s a ) 是人工免疫系统( a r t i f i c i a l i m m u n es y s t e m ：a i s ) 1 ，2 】的重要分支之一，最早是由f o r r e s t 和她的同事于1 9 9 4 年提出来的 3 ，4 】。非选择算法仅需要一些正常情况下的信息，便可将异常状况 与正常状况区分开来【5 】。通常情况下，正常状态被定义为自我，异常状态则被 认为是非我。该算法模拟了t 细胞在胸腺中产生、成熟的一个过程。在t 细胞 成熟的过程中，未成熟的t 细胞与自我做匹配，匹配成功，则消亡，只有与所有 自我都不匹配的t 细胞才能成长为成熟t 细胞。因此，成熟的t 细胞能够区分 开自我与非我。 非选择算法主要包含如下三个步骤【3 】：定义自我集合、生成检测器、监测 要保护的数据。具体来说，首先是根据应用环境定义合适的自我集合；其次，按 照某种算法生成候选检测器，判断其是否与自我集合相匹配，只有与所有自我集 合都不匹配的候选检测器才有资格成长为成熟检测器；最后是监测要保护的数 据。 第1 章结论 图1 , 1 非选择算法流程圈 图i1 描述的是非选择算法的一般流程f 3 】。非选择算法分两个阶段，第一阶 段是检测器生成阶段：首先检齑候选检测器是酋与自我集台匹配，如果匹配，则 放弃此候选检测器：如果不匹配，则将其视z 为成熟检测器，把它加八到检测器 集合巾。第二阶段为监测阶段：利用生成的检测器集合监测受保护的数据，如果 数据与菜个检测器相匹配，则将此数据视之为异常数据；如果数据与所有的检测 器都不匹配，则视之为正常数据。 在非选择算法中，初始检测器集合的生成速度与检测效率对非选择算法起着 至关重要的作用。检测器生成算法是非选择算法中的核心部分到目前为止，检 测器生成算法已经被研究了十多年了，而早期的大多数研究都是着眼于离散空 间，尤其是二进制表示空间1 3 ，4 ，6 - 1 3 。然而，g o n z a l e z 等人【1 4 】在系统地分析 7 - - - 进制表示的非选择算法以后，指出二进制表示虽然能很好的解决离散空间问 题，但是却不能够获得实值空间问题的足够信息。因此，二进制表示并不适合解 决实值空间问题。 为了解决实值空间问题。g o n z a l e z 等人于2 0 0 2 年提出了基于实值表示的实 值非选择算法( r n s a ) f 1 5 。自此咀后实值非选择算法被广泛的研究，通过 这些研究，实值非选择算法显示了它解决实值空间问题的潜在的能力。 近年来，基于非选择算法的各种人工免疫模型和算法已逐步应用于各种学科 和_ t 程领域，诸如自动控制、模式识别、故障检测、网络安全、系统维护等领域 1 5 - 2 7 】。 第1 章绪论 1 2 非选择算法研究现状 1 2 1 二进制表示的非选择算法 最早的检测器生成算法是由f o r r e s t 等人于1 9 9 4 年提出的，该算法是一种穷 尽式检测器生成算法 3 】。算法随机产生候选集合，依次与自我集合相匹配，匹 配成功则放弃，否则视之为成熟检测器。该算法时间花费非常高，并且随自我集 合的增加而呈指数型增长。 为解决此问题，在1 9 9 6 年，d h a e s e l e e r 等人对此算法进行了改进，基于动 态规划思想，提出了线性时问复杂度的检测器生成算法和贪婪检测器生成算法 【7 】，并分析了算法中存在的黑洞现象。w i e r z c h o 于2 0 0 0 年提出了利用模板样式 忽略不重要位置来生成检测器的算法 2 8 】。s i n g h 于2 0 0 2 年对贪婪算法进行了扩 展后，将其应用于异常检测【2 9 】，a y a r a 等人在检测器生成算法中引入了变异策 略【8 】。上述算法均是基于r 位连续匹配规则 3 】的。 除r 位连续匹配规则外，b a l t h r o p 等人于2 0 0 2 年提出了基于块匹配规则的非 选择算法【3 0 】，块匹配规则可以看作是连续匹配规则的种扩展。在2 0 0 4 年， e s p o n d a 等人对基于块匹配规则的算法给出了具体分析【3 l 】。同年，s t i b o r 等人对 基于块匹配规则的算法进行了扩展 3 2 】。 除此之外，二进制表示的非选择算法还有海明距离匹配规则。项目组于2 0 0 6 年提出了一种检测器长度可变的检测器生成算法【l l 】，并于同年提出了一种基于 海明距离匹配规则的启发式检测器生成算法【1 2 】。 目前，二进制表示的非选择算法在入侵检测、故障检测等领域均得到了较为 广泛的研究与应用 1 7 ，2 1 ，2 9 ，3 0 ，3 3 - 4 0 。 国内对二进制表示的非选择算法也进行了广泛的研究。张衡等人于2 0 0 5 年 提出了一种匹配闽值可变的检测器生成算法【4 l 】，郭振河等人于2 0 0 5 年利用位 变异方法改进了二进制表示的检测器生成算法【4 2 】，王辉等人于2 0 0 8 年提出了 一种最小有效检测器集合的生成算法【4 3 】，王大伟等人于2 0 0 8 年提出了一种二 进制表示与实值表示混合的检测器生成算法 4 4 】。刘永娟等人于2 0 0 7 年将二进 制表示的非选择算法应用于电力负荷异常检n 4 5 1 ，牛慧峰等人于2 0 0 8 年将二 进制表示的非选择算法应用于工业控制系统故障检测【4 6 】，等等。 1 2 2 实值表示非选择算法 实值非选择算法与二进制表示的非选择算法类似，检测器生产算法是其核心 部分。 第l 章绪论 自从g o n z a l e z 等人于2 0 0 2 年提出了基于实值表示的非选择算法( r n s a ) 以来 1 5 】，实值非选择算法在这六、七年中得到了更进一步的研究。 实值非选择算法按检测器形状进行分类，可以划分为超长方体和超球体这二 类。其中，有关超球体形状的检测器生成算法的研究最多。 2 0 0 3 年，g o n z a l e z 和d a s g u p t a 等人提出了一种超球体形状的实值检测器生 成算法 4 7 】，在此算法中，检测器半径是固定的。j i ，d a s g u p t a 二人继而于2 0 0 4 年提出了一种检测器半径可变的超球体形状的实值检测器生成算法，简称为 v - d e t e c t o r 算法 4 8 ，4 9 。此算法使用了蒙特卡罗方法来评估成熟检测器的覆盖率。 为更好地评估成熟检测器的覆盖率，翌年，j i 和d a s g u p t a 两人使用统计假设的 方法来评估v - d e t e c t o r 算法成熟检测器的覆盖率，改进了v - d e t e c t o r 算法成熟检 测器的覆盖率的评估策略，相较于初始的使用蒙特卡罗方法评估v - d e t e c t o r 成熟 检测器覆盖率的策略，此使用统计假设方法评估检测器覆盖率的策略具有更高的 置信度 5 0 】。j i ，d a s g u p t a 二人于2 0 0 9 年，给出了v - d e t e c t o r 算法的综合评述【5 1 】。 其它的一些关于v - d e t e c t o r 算法的研究工作还包括：( 1 ) j i 于2 0 0 5 分析了 v - d e t e c t o r 算法自我区域与非我区域的边界界定问题 5 2 】。( 2 ) c h m i e l e w s k i 等人 于2 0 0 6 年使用k - d 树结构存储自我集合与检测器集合以便加快v - d t e c t o r 算法检 测器生成过程 5 3 】。( 3 ) j i 和d a s g u p t a 两人于2 0 0 6 年将v - d e t e c t o r 算法应用于解 决一些实际异常检测问题，并对v - d e t e c t o r 算法解决实际问题的能力做出了分析 2 5 ，2 6 。( 4 ) s t i b o r 等人将v - d e t e c t o r 算法与其它的分类算法进行了比较分析 5 4 】。 除v - d e t e c t o r 算法外，a m a r a l 于2 0 0 7 年提出了一种利用遗传算法生成超球 体检测器的实值检测器生成算法 5 5 】。 v - d e t e c t o r 算法是实值检测器研究工作中的一个经典算法，是目前代表性的算法， 而且也是目前应用最多的一种算法。v - d e t e c t o r 算法主要流程【4 9 】：首先随机生成 一候选检测器，如果检测器在自我集合内部，则放弃；如果该候选检测器在非我 区域，则调整其半径，使之扩展到自我区域的边界处，然后将此候选检测器加入 成熟检测器集合中。 除超球体形状的检测器生成算法外，s h a p i r o 等人于2 0 0 5 年提出了一种利用 进化算法生成超椭圆体形状的检测器生成算法【5 6 】，b a l a c h a n d r a n 等人于2 0 0 7 年 提出了一种利用遗传算法生成多形状检测器的检测器生成算法 5 7 】。 在有关超长方体形状检测器的生成算法方面，d a s g u p t a ，g o n z a l e z 等人于 2 0 0 2 年提出了超长方体形状的实值检测器生成算法，用于网络入侵检洳j 1 6 ，2 2 ， h a n g 和d a i 两人于2 0 0 4 年对此算法做了改进【5 8 】。 实值非选择算法按所用的检测器生成算法主要特征分类，可以归结为如下两 类：一是随机生成候选检测器，检查是否与自我集合匹配，不与自我集合匹配的 4 第l 章绪论 为视之为成熟检测器。二是随机产生一组候选检测器，然后利用进化算法不断优 化候选检测器。目前，超球体形状的检测器生成算法绝大多数都是随机生成候选 检测器，而其他形状的检测器生成算法则大多是用进化算法优化候选检测器。 在国内，实值检测器生成算法研究也取得了一些进展，李鑫鑫等人分析了超 球体检测器覆盖率的问题【5 9 】，戴常英等人对实值检测器生成算法做了一些改进 性的工作 6 0 】，洪征等人将v - d e t e c t o r 算法应用于蠕虫检n 6 1 ，陶新民等人将实 值检测器生成算法应用于轴承故障检测【6 2 】，李海潮等人将实值检测器生成算法 应用于机械设备故障检测与齿轮箱故障检澳1 j 6 3 ，6 4 ，王大伟等人根据动态聚类 思想，对自我区域进行了预处理并提出了区域否定算法 6 5 1 。 虽然实值非选择算法的研究已取得了一定的进展，但是目前大多数的实值非 选择算法，在检测器生成阶段，都带有一定的随机性，而且存在成熟检测器生成 代价过高等不足。针对此问题，本文提出了一种确定性的检测器生成算法。 1 3 本论文主要研究内容及创新之处 现有的实值检测器生成算法基本都有一定的随机性，从而不能保证均匀的覆 盖非我区域。而且当预期检测率比较高时，其成熟检测器生成的时间代价花费也 比较大。 本论文主要研究内容如下t ( 1 ) 提出了一种基于划分测试的确定性算法( r e a l v a l u e dd e t e c t o r g e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n t e s tp r o e s s ：p t - r n s a ) 。此算法可以 确保除了自我区域与非我区域的边界部分外，其它所有的非我区域均可被成熟检 测器覆盖，而且此算法的成熟检测器的生成代价也较小。但是其不足点在于，要 达到给定的预期的检测器覆盖率，其所需的成熟检测器数目往往很多。 ( 2 ) 针对p t - r n s a 对于给定的预期检测率所需的成熟检测器数目过多的问 题，本论文继而提出了p t - r n s a 的改进算法，即基于划分测试扩展的算法 ( r e a l v a l u e dd e t e c t o rg e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n - t e s t - s p r e a d p r o e s s ：p t s i 斟s a ) 。p t s r n s a 算法基于划分测试扩展过程，实验结果表明， 此算法有效解决了p t - r n s a 算法的不足。 本文的主要创新之处在于： ( 1 ) 区别于具有一定随机性的传统检测器生成算法，本文所提出的算法是 一种确定性的算法。 ( 2 ) 本文所提出的算法，可以确保除了非我区域与自我区域的边界外，其 它非我区域均可被覆盖。 第1 章绪论 现象。 ( 3 ) 本文提出的检测器生成算法所生成的成熟检测器相互之间无交叉覆盖 1 4 本论文的组织安排 本论文其余章节安排如下。 第二章详细介绍了基于划分测试的实值检测器生成算法( p t - r n s a ) 的核心 思想及其二维空间实现的伪代码，并用相关测试集进行性能测试。p t - r n s a 算 法通过与v - d e t e c t o r 算法【4 9 】实验对比，显示了其在成熟检测器生成代价上的优 势，同时在固定预期检测率时，p t - r n s a 的实际检测率也比v - d e t e c t o r 算法 4 9 】 的实际检测率高，但不足之处是在预期检测率较高时，其所需的成熟检测器数目 往往很多。在p t - r n s a 算法与v - d e t e c t o r 的改进算法 5 0 】对比时，p t - r n s a 算 法的实际检测率与v - d e t e c t o r 的改进算法 5 0 l 相当，但p t - r n s a 所需生成的成熟 检测器数目远多于v - d e t e c t o r 的改进算法【5 0 】。 为此，本文在第三章对p t - r n s a 算法进行了扩展，提出了基于划分测试 扩展的实值非选择算法( p t s r n s a ) 。该算法与p t - r n s a 相比，性能提高了很 多，主要体现在，当成熟检测器数目相同时，p t s r n s a 的实际检测率远高于 p t - r n s a 的实际检测率；当预期检测率相同时，二者的实际检测率相当，但 p t s r n s a 所需的成熟检测器数目远少于p t - r n s a 。与v - d e t e c t o r 算法的改进算 法【5 0 】做对比时，可以发现，在固定预期检测率时，二者实际检测率相当，但大 多数情况下，p t s r n s a 所需的成熟检测器数目少于与v - d e t e c t o r 的改进算法 【5 0 l ，而且p t s r n s a 成熟检测器的生成代价大部分情况下也低于v - d e t e c t o r 的 改进算法【5 0 】的成熟检测器生成代价。因此，p t s r n s a 是具有一定优势和竞争 力的算法。 第四章是总结与展望，对本文研究工作进行了简要总结，给出了拟开展的下 一步研究工作。 1 5 本章小结 本章首先简要介绍了非选择算法的基本概念，给出其框架和分类，然后分别 介绍- f - - 进制表示的非选择算法和实值表示的非选择算法以及目前的研究现状 经典工作。最后给出了本论文的主要研究内容，创新之处以及组织方式。 6 第2 章基于划分测试的实值检测器生成算法 第2 章基于划分一测试的实值检测器生成算法 检测器生成算法是实值非选择算法的重要组成部分，然而，目前的实值检测 器生成算法基本都是随机产生候选检测器，具有很大随机性。尤其，当对监测精 度要求很高时，为生成足够多的成熟检测器，随机算法所需的时问花费往往很高。 本章提出了一种基于划分测试的实值检测器生成算法，简记为p t - r n s a ( r e a l v a l u e dd e t e c t o rg e n e r a t i o na l g o r i t h mb a s e do nt h ep a r t i t i o n t e s tp r o e s s ) 。区 别于以往的检测器生成算法，p t - r n s a 是一种确定性的算法。通过p t - r n s a ， 可以确保除了在自我与非我的边界区域外，其他所有的非我区域都能被成熟检测 器集合所覆盖，并且此种算法的成熟检测器生成所需时间也较少。 2 1算法描述 本节首先给出了p t - r n s a 算法的思想，然后给出y - - 维空间中的算法实现。 2 1 1 算法思想 1 初始化： 将整个表示空间看作一超长方体，并将其作为候选超长方体。 2 测试：判断此候选超长方体是否与自我集合相交，如果没有相交，则将其看作一成 熟检测器。 3 划分：如果此长方体与自我集合相交( 即至少与某一自我个体有交叉覆盖区域) ， 则将其均匀划分成一些更小的候选超长方体。 4 对于第三步中划分出来的每一个小的候选超长方体，转第2 步，重复执行“测试划分” 过程，直到满足结束条件。 图2 1p t - r n s a 核心思想 图2 1 介绍了p t - r n s a 的核心思想，其中的步骤2 是f t - r n s a 的测试阶段， 步骤3 是p t - r n s a 的划分阶段。 本文使用一个二元组 l l x i c l l ，1 八c , l ，长方形的覆盖范围数学化 描述为 t 户li x 呶i 扣- 钾_ ) 四 图2 2 二维空闻长方形的表示 为了更好地控制算法的“划分- 测试”深度，可以预先定义一个最小的榆测 器中心点到各维边界上的距离。当候选超长方体的中心点到各维边界上的距离 r 小于h 时，则不再对其进行继续划分。这个预先定义的r o 可以作为算法的终结 条件。另外，同样可以设定其他终结条件，比如，成熟检测器数目、预定义的检 测率菩。 图2 3 给出了p t - r n s a 在二维字问中的”划分- 钡0 试”过程，此过程直观显 示了p t - r n s