（计算机软件与理论专业论文）用于异常检测的进化非选择算法性能分析.pdf

摘要 摘要 进化非选择算法是基于生物免疫进化机制和免疫非选择机制提出的，已被应 用于异常检测问题。本文主要对进化非选择算法用于异常检测时的平均时间复杂 度进行分析；并从理论上对比分析了自我检测器集和非我检测器集用于异常检测 时的效率。 对进化非选择算法用于异常检测时的理论分析有助于对算法和异常检测问 题的理解；并且在解决不同的异常检测问题时，有助于选择合适的算法。 本文的具体工作包括以下几个方面。 ( 1 ) 从理论和实验角度分析了进化非选择算法用于异常检测时的平均时间 复杂度。首先，根据进化非选择算法的特性，将异常检测问题分成两种不同的情 况，即无g a p 情况和有g a p 情况。然后，当采用完全匹配策略时，在检测个体的 每一位都以o ( t 。1 ) 的概率进行变异的条件下，分别分析了进化非选择算法用于这 两种异常检测问题时的平均时间复杂度。最后，通过实验分别对无g a p 情况和有 g a p 情况进行了验证，得出理论结果和试验结果是基本一致的。 ( 2 ) 当采用完全匹配策略时，对比分析了自我检测器集和非我检测器集用 于异常检测时的平均时间复杂度。首先分别了计算自我检测器集和非我检测器集 用于异常检测时所需要的平均时间复杂度。然后通过对比分析，得出在解决不同 的异常检测问题时，是自我检测器集还是非我检测器集更加有效。通过分析的结 论可以得出，自我检测器集的大小、非我检测器集的大小和异常发生的概率都对 检测器集的选择有影响。本文的实验结果验证了此理论结果的正确性。最后讨论 了在使用进化非选择算法生成非我检测器和使用并行工作站同时检测异常两种 情况下的不同检测器集的平均时间复杂度。 ( 3 ) 在采用部分匹配策略的条件下，对比分析了自我检测器集和非我检测 器集用于异常检测时的平均时间复杂度。首先分别计算自我检测器集和非我检测 器集用于异常检测时所需要的平均时间复杂度。然后通过对比分析，得出了在采 用部分匹配时的自我检测器集和非我检测器集的效率对比情况，并从实验角度验 证了结论的正确性。 总的来说，本文分析了进化非选择算法用于异常检测时的平均时间复杂度； 并对自我检测器集和非我检测器集用于异常检测时的平均时间复杂度进行了对 比分析。本文的工作不仅对进一步理解进化非选择算法的求解效率具有参考价 值，而且有利于促进基于生物免疫原理的异常检测算法的研究。 a b s t r a c t b a s e do nt h eb i o l o g i c a li m m u n es y s t e ma n dn e g a t i v es e l e c t i o nm e c h a n i s m ，t h e e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m sh a v eb e e np r o p o s e d ，a n db e e nu s e df o r a n o m a l yd e t e c t i o np r o b l e m s t h i sp a p e ra n a l y z e st h ea v e r a g et i m ec o m p l e x i t yo f e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m sf o ra n o m a l yd e t e c t i o n ，a n dc o m p a r e st h e a v e r a g et i m ec o s t so fe m p l o y i n gt h en o n s e l f d e t e c t o rs e ta n dt h es e l fd e t e c t o rs e tf o r a n o m a l yd e t e c t i o n t h em a i nw o r k si nt h i sp a p e ri n c l u d et h ef o l l o w i n ga s p e c t s ( 1 ) t h ea v e r a g et i m ec o m p l e x i t yo fe v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m s f o ra n o m a l yd e t e c t i o ni sa n a l y z e dt h e o r e t i c a l l ya n de m p i r i c a l l y f i r s t l y ，t h ea n o m a l y d e t e c t i o np r o b l e m sa r ec l a s s i f i e di n t ot w os i t u a t i o n s ：n og a ps i t u a t i o na n db e i n g ag a p s i t u a t i o n s e c o n d e l y , w h e nt h ec o m p l e t em a t c h i n gr u l ei sa d o p t e d ，a n de a c hb i to f t h e i n d i v i d u a lh a v et h es a m ep r o b a b i l i t yo ( t 一1 ) t of l i p ，t h ea v e r a g et i m ec o m p l e x i t yo f e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m sf o ra n o m a l yd e t e c t i o ni sa n a l y z e d i nt h e e n d ，t w ok i n d so fs i m u l a t i o ne x p e r i m e n t so f n og a ps i t u a t i o na n db e i n gag a ps i t u a t i o n a r ed o n e t h ee m p i r i c a lr e s u l t sa n dt h e o r e t i c a lr e s u l t sa r eb a s i c a l l yi d e n t i c a l ( 2 ) w h e n t h ec o m p l e t em a t c h i n gr u l ei sa d o p t e d ，t h ea v e r a g et i m ec o s ta b o u tt h e s e l fd e t e c t o rs e ta n dt h en o n s e l fd e t e c t o rs e tf o ra n o m a l yd e t e c t i o ni sc o m p a r e d f i r s t l y , t h ea v e r a g et i m ec o s to ft h es e l fd e t e c t o rs e ta n dt h en o n s e l f d e t e c t o rs e tf o r a n o m a l yd e t e c t i o ni sa n a l y z e dr e s p e c t i v e l yw h e nt h ec o m p l e t em a t c h i n g r u l ei su s e d t h e nt h ea v e r a g et i m ec o s t sa r ec o m p a r e d 。t h ea n a l y s i sr e s u l t sc o u l dh e l pt oc h o o s e m o r ee f f i c i e n td e t e c t o rs e tw h e ns o l v i n gas p e c i f i ca n o m a l yd e t e c t i o np r o b l e mt oa c e r t i a ne x t e n tw h e nc o m p l e t em a t c h i n gr u l ei su s e d s i m u l a t e de x p e r i m e n t sa r ed o n e ， a n de 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 et h a tt h et h e o r e t i c a lc o n c l u s i o ni se s s e n t i a l l y c o r r e c t ( 3 ) w h e nt h ep a r t i a lm a t c h i n gr u l e sa r ea d o p t e d ，t h ea v e r a g e t i m ec o s ta b o u tt h e s e l fd e t e c t o rs e ta n dt h en o n s e l fd e t e c t o rs e tf o ra n o m a l yd e t e c t i o ni sc o m p a r e d t h e o r e c t i c a l l ya n de m p i r i c a l l y t h ea v e r a g et i m ec o s to ft h es e l fd e t e c t o rs e ta n dt h e n o n s e l fd e t e c t o rs e tf o ra n o m a l yd e t e c t i o ni sa n a l y z e dr e s p e c t i v e l yw h e nt h ep a r t i c a l m a t c h i n gr u l e s a r ea d o p t e di nt h eb e g i n n i n g t h e nt h ea v e r a g et i m ec o s t sa r e c o m p a r e d i nt h ee n d ，t h ee m p i r i c a lr e s u l t sd e m o n s t r a t et h a tt h et h e o r e t i c a la n a l y s i si s h a i p a l l vc o r r e c t a b s t r a c t a l g o r i t h m sf o ra n o m a l yd e t e c t i o ni sa n a l y z e di nt h i sp a p e r , a n d t h ea v e r a g et i m ec o s t s o fe m p l o y i n gt h en o n s e l fd e t e c t o rs e ta n dt h es e l fd e t e c t o rs e tf o ra n o m a l yd e t e c t i o n a r ec o m p a r e dt h e o r e t i c a l l y t h ew o r ki nt h i sp a p e rc o u l dn o to n l yh e l pt ou n d e r s t a n d t h ep e r f o r m a n c eo fe v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h mf o ra n o m a l yd e t e c t i o n ， b u ta l s oh e l pt oa d v a n c et h ed e v e l o p m e n t so fa n o m a l yd e t e c t i o na l g o r i t h m sw h i c ha r e b a s e do nb i o l o g i c a li m m u n ep r i n c i p l e 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 ，e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m ， a v e r a g et i m ec o m p l e x i t y , n e g a t i v es e l e c t i o na l g o r i t h m 插图目录 图1 1 图2 1 图2 2 图2 3 图2 4 图2 。5 蚕2 6 图2 7 图2 。8 图2 9 图2 1 0 图2 。l l 鹜2 1 2 图2 1 3 图2 。l j 4 图2 。1 5 图2 1 6 图2 重7 图3 1 图4 1 图4 2 图4 3 图4 4 图4 5 圈4 6 图4 7 图4 。8 图4 9 图4 1 0 图4 1 1 插图目录 迸讫菲选择算法基本流程f l ，2 0 ，2 2 2 检测空间模型8 g a p 存在8 无g a p 。8 三种不同的免疫反应9 大多数好的个体能存活下来。1 2 大多数好的个体不能存活下来1 2 初始种群和待检测个体虽在间个非我子空间内，但求解仍需要跳过g a p 1 3 求解需要跳过多个g a p 1 4 被检测个体所在的菲我子空间的两种情况1 5 卢1 6 时l o w e r b o u n d ( g , w ) 的取值札1 6 芦3 2 时l o w e r b o u n d ( g , w ) 的取值1 7 = - 6 4 时l o w e r b o u n d ( g , w ) 的取值。1 7 - - 1 6 ，w = 2 时l o w e r b o u n d ( g , w ) 和l n ( l o w e r b o u n d ( g , w ) ) 的曲线图1 8 - - 1 7 ，g = 2 对l o w e r b o u n d ( g , w ) 的曲线豳1 8 实验基本流程1 9 无g a p 情况下三种实验的结果曲线图2 0 存在g a p 情况下实验结果的馥线图。2 l 对比自我和非我检测器集检测效率的实验流程3 0 采用部分匹配时的对比实验流程4 5 s = r ，l = 1 2 ，r = 1 0 时理论馕与实验值的对比图4 7 s = 灭，l = 1 2 ，r = ll 时理论值与实验值的对比图4 8 s = r ，l = 1 6 ，r = 1 3 时理论值与实验值的对比图4 9 s = 霞，l = 1 6 ，r = 1 4 时理论傻与实验 壹的对比图5 0 s = r ，l = 1 6 ，r = 1 5 时理论值与实验值的对比图一5 l 胎( m 肋事趴对4 ) ，l = 1 2 ，r = 1 0 时理论值与实验值的对比图5 2 r = ( n - h ) * s ( s + h ) ，扣1 2 ，r = l l 对理论值与实验馕的对比图5 3 r = ( n - h ) 幸趴酣聊，l = 1 6 ，r = 1 3 时理论值与实验值的对比图5 4 r = ( n - 挪+ 鳓蛮- + 劢，l = 1 6 ，r = 1 4 时理论值与实验值的对比图5 5 r = - ( n - h ) * s ( s + h ) ，l = 1 6 ，r = 1 5 酵理论僵与实验值的对比圈。5 6 表格强录 表3 1 表3 2 表4 。l 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表4 9 表4 1 0 表格目录 实验中自我集大小和非我集大小3l 实验结采3 2 采用部分匹配策略的结果对比( s = r ，l = 1 2 ，r = 1 0 ) 4 6 采用部分匹配策略的绪采对赣：( s = r ，l = 1 2 ，r = 1 1 ) 4 7 采用部分匹配策略的结果对比( s = r ，l = 1 6 ，r = 1 3 ) 4 8 采瘸部分匹配策旗的结果对比( s = 霆，l - - 1 6 ，r = 1 4 ) 4 9 采用部分匹配策略的结果对比( s = r ，l = 1 6 ，r = 1 5 ) 5 0 采蔫部分匹配策略的结果对比( 霆：嘲枣s ( s + g ) ，l = 1 2 ， 采用部分匹配策略的结果对比( 胆c m 仞幸趴甜仞，l = 1 2 ， 采用部分匹配策略的结果对比( 贮( m 功牛| s 讣固，l = 1 6 ， 采用部分匹配策略的结果对比( r = - ( n - h ) 卓s ( s + h ) ，l = 1 6 ， 采用郝分匹配策略的结果对比( 胎( m 功+ 影伊棚，l = 1 6 ， = 严 产 r = r = 1 5 ) 5 l 。5 2 5 3 5 4 5 5 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 签字暑期：二乌庭4 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中圜科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向图家有关部门蠛枧构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进季亍检索，可以采髑影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 作者签名： 签字日期： 融保密( 年) 粗 蚪 导师签名：里叁望 导师签名：蔓叁苎 。 签字日期：丝 ：苎兰z 第1 章绪论 第1 章绪论 进化非选择算法( e v o l u t i o n a r yn e g a t i v es e l e c t i o na l g o r i t h m s ，e n s a s ) 是基 于生物免疫进化机制和免疫非选择机制，结合进化算法与非选择算法而提出来的 【1 4 】，已被应用于求解异常检测等问题 1 ，5 8 】。 对进化非选择算法用于异常检测时的理论分析，尤其是对平均时间复杂度的 分析，有助于加深对算法和所求解问题的理解。进化非选择算法是通过模拟免疫 系统中免疫细胞的进化和清除病毒机制而提出的，对算法平均时间复杂度的研究 也从某种程度上解释免疫系统中存在的不同免疫应答现象。 本文主要对进化非选择算法用于异常检测时的平均时间复杂度进行分析；并 从理论上对比分析了自我检测器集和非我检测器集用于异常检测时的效率问题。 本章首先介绍了进化非选择算法的基本流程，然后对进化非选择算法的应用 研究现状和理论研究现状分别进行概述，然后对进化算法的时间复杂度分析工作 进行了简单的介绍，最后介绍了本文的主要研究内容。 1 1 进化非选择算法概述 进化非选择算法( e n s a s ) 是基于生物免疫进化机制和免疫非选择机制而提 出的【1 4 】，主要应用于异常检测和复杂优化问题求解等【l ，5 1 6 。本节首先介绍 生物免疫机制和非选择机铜j 1 7 1 9 ，然后重点介绍进化非选择算法的流程【1 ，1 0 ， 2 0 2 2 】。 1 1 1生物系统中的免疫进化机制与免疫非选择机制 生物免疫系统通过生成非我空间中的免疫细胞来识别自我和非我，从而达到 清除非我入侵i 1 8 ，1 9 ，2 3 ，2 4 。 在免疫系统中，只有与抗原相匹配的免疫细胞才能识别并清除抗原抗原 【2 3 1 。在免疫细胞的成熟过程中，其增值程度与亲和度有关。即免疫细胞的亲和 度越高，其增殖的就越多。然后免疫细胞会通过不断地进化生成新的的免疫细胞。 对于新生成的免疫细胞，首先要在胸腺中与自我细胞进行匹配。那些与自我匹配 的免疫细胞会死亡，以防止自我免疫反应的发生 2 3 】。而剩余的免疫细胞则会进 入人体进行免疫检测。此过程一直进行，直到生成能够清楚抗原的有效免疫细胞。 其中的一部分有效的免疫细胞会成为记忆细胞【2 3 】，使得免疫系统以后能够对相 同或相似的抗原进行快速识别。 第1 章绪论 1 1 2 进化非选择算法的流程 基于生物免疫非选择机，f o r r e s t 等人提出了非选择算法( n 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 ，n s a s ) 【2 5 ，并应用于异常检测问题。一般来说，n s a s 包括三个步 骤，即生成自我集、根据自我集生成非我检测器集、利用非自我检测器集进行检 测。其中生成非我检测器集是利用非选择机制，把那些与自我相匹配的未成熟的 检测器删除，而那些不匹配的则成为成熟的检测器【2 6 3 1 。 非选择算法是预先生成固定的检测器集。对于新的入侵，其缺乏鲁棒性和自 适应性 1 ，3 ，2 8 。特别地，s t i b o r 等 3 2 ，3 3 通过实验，从检测器的检测率和误检 率方面说明了在二进制空间中，非选择算法并不适用于异常检测问题。而对于实 值空间的异常检测问题，s t i b o r 等 3 4 ，3 5 通过实验说明了非选择算法并不能生成 有效的检测器。 进化非选择算法是结合了进化算法和非选择机制而形成的具有自适应和自 学习能力的算法 1 ，2 0 ，2 8 】，其能在检测过程中不断的进化检测器集。进化非选 择算法的基本流程如图1 1 。 s t e p l ： 初始化检测器集。随机生成一定数目的非我检测器个体。 s t e p 2 ： 亲和度评估。计算每个非我检测器个体的亲和度。 检测异常。用非我检测器个体与待检测的数据进行匹配。如果匹配成功， s t e p 3 ： 则检测到异常，算法结束；否则进入s t e p 4 。 进化操作。进化操作般包括变异和重组操作。由父代检测器个体生成 s t e p 4 ： 未成熟的检测器个体。 非选择操作。对新生成的未成熟检测个体进行非选择操作，所有与任一 s t e p 5 - 自我集个体匹配的未成熟检测器都被删除掉，以防止自我免疫的发生。 s t e p 6 ： 亲和度评估。计算非选择后的成熟检测器个体的亲和度。 s t e p 7 ： 生成下一代检测器集。根据所采用的选择策略，生成下一代检测器集。 s t e p 8 ：算法跳转到s t e p 3 。 图1 1 进化非选择算法基本流程【l ，2 0 ，2 2 】 因为进化非选择算法是结合了进化算法和非选择机制而提出的，所以在操作 过程中不仅要针对不同的问题设计合理的操作算子和匹配策略，还要给出合适的 自我集定义。 从图1 1 可以看出，进化非选择算法主要包括8 个基本的步骤。其中第4 步 的进化算子与进化算法中的相同，可以分为组合和重组操作 1 7 1 9 。 2 第l 章绪论 第5 步的非选择操作是在未成熟的检测器个体和自我集个体之间进行的，是 通过相互匹配操作完成的。除了完全匹配以外，算法中也经常采用部分匹配规则， 如h a m m i n g 距离匹配规贝j j 3 0 ，3 3 、r c b 匹配规贝j j 2 5 】以及r - c h u n k 匹配规则【3 6 】 等。 针对不同的问题，自我集的设定是不同的。例如，在异常检测问题中将需要 保护的串定义为自我集【1 ，5 ，9 】，这里的自我集是静态的；而在利用算法自动设 计逻辑电路时，算法会将每代最差的个体定义为自我集【3 7 】，此时自我集是动态 变化的【2 】。 1 2 进化非选择算法的研究现状 进化非选择算法已经应用于不少领域，并取得了一定的成果。相应的理论研 究工作也取得了一些进展 1 0 ，2 0 ，2 2 。 1 2 1进化非选择算法应用现状 进化非选择算法最初多用于异常检测和网络安全 1 ，5 8 】，目前已应用于软硬 件划分【2 】、机器人路径规划【3 等多个层面。 在异常检测和网络安全方面。f o r r e s t 等人提出了非选择算法( n e g a t i v e s e l e c t i o n a l g o r i t h m ，n s a ) ，最初被用于异常检钡j j 2 5 。但是，n s a 生成成熟检测 器的时间代价较大，并且检测器集的自适应性差。文献 3 8 1 9 将免疫非选择机制 与进化学习机制相结合，提出了两种用于异常检测问题的进化非选择算法。l e e 和m a o 等人【6 提出用于家庭网络异常检测的自适应进化非选择算法。k i m 和 b e n t l e y 等人【4 通过综合非选择机制、基因库进化、克隆选择和免疫记忆机制， 提出了用于入侵检测的动态克隆选择算法，可视其为一种进化非选择算法。 此外，曹先彬等 3 9 】提出了结合基因库进化与非选择策略的算法，并用于旅 行商求解问题。在函数优化问题中，由于函数往往具有多个局部最优解，此时进 化非选择算法能利用非选择的作用，使算法能跳出局部最优 1 1 】。文献【3 】将e n s a 用于移动机器人路径规划问题。该算法在进化过程中既能通过非选择的作用，避 免产生差的个体，加快算法收敛速度；同时又能通过控制种群个体的多样性来防 止陷入局部最优。文献【2 】提出了用于软件硬件划分的进化非选择算法 e n s a h s p 。当采用赌论选择方法并保留最好的个体时，e n s a h s p 是收敛的。 在e n s a h s p 算法中，自我集是动态变化的，采用的是先进先出更新策略。 3 第1 章绪论 1 2 2 进化非选择算法理论研究现状 相比应用而言，对进化非选择算法的理论研究还处于初始阶段。通过这些理 论研究，可以加深对算法及所解决问题的理解。与此同时，进化非选择算法是通 过模拟免疫系统中免疫细胞的进化及清除病毒机制而提出的，对进化非选择算法 用于异常检测时的平均时间复杂度的研究也可从某一方面解释免疫系统中存在 的不同免疫反应现象。 p e i 和l u o 1 0 从理论和实验角度分析了进化非选择算法用于组合优化时的 平均时间消耗。对于收敛性的研究，文献【2 2 】分析了e n s a 用于异常检测时的收 敛性，主要分析了两种不同的变异算子对收敛性的影响。 虽然针对进化非选择算法的理论研究工作还不多，但关于进化算法的理论研 究，尤其在求解简单问题时的平均时间复杂度的研究已经取得了一些较好的成 果。概括来说其分析方法可以分成如下四种。 ( 1 ) y u 和z h o u 4 0 通过研究进化算法的收敛率来计算算法求解的平均时间 复杂度。 ( 2 ) d r o s t e 和j a n s e n 等 4 1 4 3 通过研究进化算法各算子的概率情况，计算 出了算法用于组合优化问题时的平均时间复杂度的上界。其主要方法是通过研究 各个算子对算法求解所起到的最小作用，从而得到算法求解的最小概率，从而得 出平均时间复杂度的上界。 ( 3 ) h e 和y a o 4 4 4 7 $ u 用d i r f ta n a l y s i s 分析了进化算法用于求解不同问题 时的平均时间复杂度。其方法是综合研究进化算法里各个算子对算法求解的影 响，从而得出在进化时，相对于当前解，下一代解是朝向最优解的方向进化还是 向反方向进化，并得出各种情况下的概率，从而综合计算出算法求解所需要的平 均时间复杂度。 ( 4 ) 利用马尔可夫模型，h e 和y a o 4 8 ，4 9 分析了进化算法用于求解问题时 的平均时间复杂度。其主要考虑当前种群的每个个体变成其他各种情况的个体时 的概率，得到这个种群求得解的概率，从而得出算法求解的平均时间。 1 3 本论文的主要研究内容及组织安排 本文的主要研究内容包括如下三个部分。 ( 1 ) 从理论角度对进化非选择算法用于异常检测时的平均时间复杂度进行 了分析。首先，根据将异常检测问题分成了两种不同的情况，即算法求解时不需 要跳过自我空间个体就可以找到解( 无g a p 情况) 和算法必须跳过自我空间才能 4 第1 章绪论 求得解( 有g a p 情况) 。然后，在采用完全匹配策略，以及检测个体的每一位都 以伙厂1 ) 的概率进行变异的条件下，分别分析了进化非选择算法用于两种异常检 测问题时的平均时间复杂度。最后，通过实验分别对无g a p 情况和有g a p 情况进 行了验证，得出理论结果和试验结果是基本一致的。 ( 2 ) 当采用完全匹配策略时，对比分析了自我检测器集和非我检测器集用 于异常检测时的效率。首先，计算当自我集和非我集分别作为检测器集用于异常 检测时所需要的平均时间复杂度。然后通过对比分析，得出在解决不同的异常检 测问题时，是自我检测器集还是非我检测器集更加节省时间。本文的实验结果验 证了理论结果的正确性。最后讨论了在使用进化非选择算法生成非我检测器集和 并行工作站同时检测两种情况下的不同检测器集的平均时间复杂度。 ( 3 ) 在采用部分匹配策略的条件下，对比分析了自我检测器集和非我检测 器集用于异常检测时的效率。首先分别计算自我检测器集和非我检测器集用于异 常检测时所需要的平均时间复杂度。然后通过对比分析，得出了在采用部分匹配 时的自我检测器集和非我检测器集的效率对比情况，即在解决某一异常检测问题 时，使用自我检测器集还是非我检测器集更加有效。并从实验角度验证了结论的 正确性。 本文的内容安排如图1 2 。 绪论 分析进化非选择算法用于异常检测时的平均时间复杂度 对比分析自我检测器和非我检测器用于异常检测的效率 存在g a p 情况 无g a p 情况 完全匹配 图1 2 本文主要内容安排 第二章从理论和实验角度分析了进化非选择算法用于异常检测时的平均时 间复杂度。给出了理论证明，并通过实验验证了理论结果。 针对非选择算法是否适用于异常检测等问题，第三章从理论的角度，通过对 比分析自我检测器集和非我检测器集用于异常检测时的平均时间复杂度，给出在 解决某一特定的异常检测问题时，是自我检测器集还是非我检测器集更加有效。 并且在实验角度验证了结论的正确性。最后讨论了在使用进化非选择算法生成非 我检测器集和并行工作站同时检测两种情况下的不同检测器集的平均时间复杂 度的对比。 5 第1 章绪论 第四章是当采用部分匹配策略时，自我检测器集和非我检测器集用于异常检 测时的平均时间复杂度的对比分析。文中给出了在采用部分匹配规则时的自我检 测器集和非我检测器集的效率对比情况，最后，实验结果与理论结果是相吻合的。 第五章总结本文，并提出了以后的工作方向。 6 第2 章进化非选择算法用于异常检测的平均时间复杂度 第2 章进化非选择算法用于异常检测的平均时间复杂度 近些年，进化非选择算法已经被应用于很多方面，并且取得了些可喜的成 果。相比而言，对进化非选择算法的理论研究还很少。 关于进化算法的理论研究，尤其是求解简单组合优化问题时平均时间复杂度 的研究，已经取得了一些较好的成果，建立了很好的理论研究模型和方法。通过 这些理论研究，加深了对算法及所解决问题的理解。 基于进化算法平均时间复杂度方面的研究工作，本章对进化非选择算法用于 异常检测时的平均时间复杂度进行了分析，并通过模拟实验对理论的分析结果进 行了验证。通过理论研究，加深了对进化非选择算法以及其求解过程的的理解。 因为进化非选择算法模拟了生物免疫系统中免疫细胞的进化以及清除病毒的过 程，对其平均时间复杂度的研究也有助于从时间复杂度角度解释免疫系统中存在 的不同免疫应答现象。 2 1 概述 人们通过引入一些模型和方法用于进化算法的平均时间复杂度的研究，并且 取得了较好的成果。例如y u 和z h o u 4 0 j 嗵_ 过研究进化算法的收敛率来计算进化 算法的首次找到解的平均时间复杂度。d r o s t e 和j a n s e n 4 1 4 3 等通过研究进化算 法各算子的概率情况得出了进化算法在求解组合优化时的平均时间复杂度的。 h e 和y a o 4 4 4 7 并u 用d i r f ta n a l y s i s 分析了进化算法用于求解不同问题时的平均时 间复杂度。通过利用马尔可夫模型，h e 和y a o 4 8 ，4 9 分析了求解问题时平均时 间复杂度。z h o u 和h e 5 0 矛l j 用吸收马尔可夫模型，分析了进化算法用于解决约 束优化问题时的平均时间复杂度。 由于进化非选择算法是进化算法和非选择算子结合而成的算法，对其平均时 间复杂度的研究有很大不同。对于每代生成的检测器，非选择算子都会过滤掉那 些落入自我集空间的检测器个体，以免发生自我免疫 1 8 ，2 7 】。如果在进化过程 中，在变异概率一定的情况下，新生成的检测器个体以很大的概率落入自我空间 里，那么非选择算子就会过滤掉几乎整个新生成的个体。此时这些个体是算法求 解所必需的过渡个体，那么算法找到解的概率就会很小，平均的求解时间就会变 得很长。而如果非选择算子不能过滤掉那些中间个体，那么算法经过一代一代的 进化就会很快的找到有效的检测器。 7 第2 章进化非选择算法用于异常检测的平均时间复杂度 图2 1 检测空间模型 圆：s e l f s e t 圆：n o n s e l f s e t 图2 2 有g a p 图2 3 无g a p 出现以上不同求解情况的原因是由于整个空间中自我集空间形状的不同所 造成的。图2 1 给出了一个一般的检测空间模型。从图中可以看出，非我空间可 能被自我空间分离成很多个。如果初始的检测器集与所要求得的目标解不在同一 个非我子空间内，那么算法求解过程中的许多过渡个体都属于自我空间，算法求 得匹配解的概率就会很低，那么所消耗的求解时间就会很长。否则，若初始检测 器集与目标解在同一个非我子空间里，并且存在很多过渡个体，通过这些过渡个 体算法可能很快地找到有效的检测器。本文把有许多过渡个体落入自我空间的情 况称为存在g a p 的情况，如图2 2 ，因为算法必须跳过这些过渡个体而直接求得 8 第2 章进化非选择算法用于异常检测的平均时间复杂度 解或者更加好的解。这些落入皇我空间的个体就像一条沟( g a p ) ，如果算法要找 到解就必须跳过去。反之，这些过渡个体得以保留的情况称为无g a p 的情况，如 图2 3 ，因为求解过程会很平坦，非选择算子基本上不会对求解过程造成很大影 响。 本章首先分别对存在g a p 的情况和无g a p 情况的情况进行平均时间复杂度的 分析，最后通过模拟实验来验证理论分析结果与实验结果是否相符 2 0 】。 值得指出的是，对进化非选择算法用于异常检测问题的平均时间复杂度的研 究，也有劲于解释为什么生物免疫系统对不同类型的入侵病毒，有不同的免疫应 答现象。在生物免疫系统中，对于不同的病毒入侵，免疫细胞的反应时间是不同 的。即存在三种不同的免疫应答，如图2 4 2 0 】：初次免疫反应应答( p r i m a r y i m m u n er e s p o n c e ) ，交叉反应免疫应答( c r o s s r e a c t i v ei m m u n er e s p o n c e ) 和二次 免疫应答( s e c o n d a r yi m m u n er e s p o n c e ) 【2 3 。这三种免疫应答的响应时间是不同 的，且是依次变小的。那么，为什么会存在这种现象呢? 因为进化非选择算法是 通过模拟生物免疫系统里的进化及清除病毒的过程而提出的，那么对进化非选择 算法震予异常检测时的平均时间复杂度的研究有助于对不同类型的免疫波答现 象进行解释。 时阔 图2 4 兰种不同的免疫反应 2 2 平均时间复杂度的理论分析 h e 和y a o 4 4 4 7 通过引入d r i f ta n a l y s i s 方法，分析了进化算法用于组合优化 问题求解时的平均时闻复杂度。在h e 和y a o 4 4 4 7 】研究工作的基础上，本章分 析了进化非选择算法用于异常检测时的平均时间复杂度。下面首先简单介绍一下 这个方法【4 4 】。 9 第2 章进化非选择算法用于异常检测的平均时间复杂度 设d ( x ，c ) 表示为候选解x 和最优解c 之间的跑离，一般记d ( x ，c ) 为d ( x ) 。那 么，d ( e k ) = m i n d ( x ) ：x e e k 为第k 代种群与最优解c 之间的距离，即种群缸中最 好的个体与c 之间的距离。可以得到第k 代的d r i f t 值定义为 ( d ( & ) ) = d ( ) 一d ( 6 k + 1 ) 。记f 为首次找到最优解c 的运行代数，因此 f = m i n k ：d ( c k ) = o ) 。为方便起见，下面给出了h e 和y a o 在文献 4 4 q h 给出的定 理。在本章后边的分析中将会用到该定理。 定理2 1 4 4 】：假设有两个关于，的多项式的值为( ，) o 和盯( ，) 0 。对于任 意的初始化种群x 都有d ( x ) ( ，) ；且每代的d r i f t 值都不小于o - ( t ) ，即 e d ( e k ) 一d ( c m ) id ( 6 k ) 0 】o - ( t ) ( 七o ) 。因此找到解的平均时间复杂度为 e rld ( 6 0 ) o 】( t ) c r ( o ( 2 1 ) 本节首先分析在无g a p 情况下进化非选择算法用于异常检测时的平均时间 复杂度，然后对存在g a p 的情况进行分析。以下是本节分析所用到的一些符号。 初始检测器集 c ：待检测的异常个体 s ：自我集 ：非我集 ，：种群个体编码长度 以：串中每一位的变异概率，并且p m = 厂1 或p 。= o ( 1 - 1 ) 本节所讨论的进化非选择算法主要包括四个基本的步骤：适应度评估，变异 操作，非选择操作和选择操作。因为进化非选择算法有很多变种，下面给出了本 章所分析的进化非选择算法的基本流程。 ( 1 ) 初始化检测器种群。生成一个大小为n ( 7 0 ) 的种群，表示为岛，并 设k = - o 。 ( 2 ) 适应度评估。对于种群中的所有个体五e k ，计算其适应度值 a f f i n i t y ( x i ) = z 日( 葺，c ) ，其中h ( x f ，c ) 为而和c 的h a m m i n g 距离。如 果适应度值大于匹配阈值( 其大小是由匹配策略决定的) ，即 a f f i n i t y ( x ，) 万，那么就找到了异常个体，算法结束。 ( 3 ) 变异操作。对种群s 。中的每一个个体西进行变异操作，生成一个中 间种群，表示为。+ m 。 ( 4 ) 非选择操作。对占“m 进行非选择操作，任何与自我匹配的个体都将 从种群中删除，保证不会发生自我免疫现象。此时，g 。+ 肘中剩余的 个体形成了一个新的种群，记为吼+ 。 ( 5 ) 适应度评估。对于任何而唧的个体，计算其适应度值a f f i n i t y ( x ，) 。 如果a f f i n i t y ( x 。) 万，就找到了异常，算法结束。 1 0 第2 章进化非选择算法用于异常检测的平均时间复杂度 ( 6 ) 选择操作。本章使用截断选择策略，即在& + 和唧中选择种群中最 好的前个个体，所得的种群记为占。+ s 。 ( 7 ) 生成下一代种群。使& + 1 = 吼+ s ，k = k + l 。跳转到步骤( 3 ) 。 因为本章对进化非选择算法的分析是基于h e 和y a o 4 4 的工作进行的，需 要用到d r i f ta n a l y s i s ，下面给出距离d ( 工) 的定义方法。 m 叶”a f - f i n 。砂 卜na 铷f f i n i 吣t y ( x ) 脚 0 】p 。( 1 一如) 卜1 。 对于任何初始种群x ，