论文研究-树突细胞算法的运行时间属性分析.pdf

所需积分/C币:6 2019-07-22 19:37:23 942KB .PDF

第二代人工免疫系统中的树突细胞算法(DCA)是受先天性免疫系统中树突细胞(DCs)功能的启发而开发的算法,它已被成功运用于许多计算机安全相关领域。但是对DCA理论方面的分析工作很少,对算法理论方面的研究也较少出现,因此对DCA执行相似的理论分析、确定算法的运行时间变量、揭示其他算法属性就显得非常重要。给出了两个基于算法输入数据流的运行时间变量,并且证明了这两个变量是如何对算法输入数据与算法运行时变量进行关联,也揭示了在给定时间窗内基于输入数据的算法行为,而这些都与实际应用执行的算法无关。此研究工作为算法的进一步应用开发提供了指导。
第1期 王丽,等:树突细胞算法的运行时间属性分析 9 T(n)=0(N)+0(nN)+∑7(n) N∑a1(O()) T(n)≤O(N)+0(nN)+「n/81×O(82 (b2-t1)(x1+ 因为1≤N≤n,1≤δ≤n 所以T(n)=0(N)+0(nN)+O(n6) 证明DC群体中最后个DC的生命期为 (N T(n)=0(max(nN,nδ)) 1)d,整个DC群体的生命期之和为 (r1+xx)N(x1+x1+(N-1)d)N 运行时间复杂度从O(n3)降低为O(max(n,n6));如果 n或δ=n,则算法的时间复杂度为平方级即为O(n2)。如果 2x1+(N-1)d)N N<n且δ<n,则算法的时间复杂度是线性的即为O(n)。 由此可以看出无论是标准DCA还是使用了分片思想实现 设η1为整个DC群体的生命期平均值。 在线分析组件的DCA,它们的运行时间复杂度变量都与n与N 1==x 有关,而n与基于抗原数分片的在线分析有关,N与成熟的树 设φ为一个DC在时间间[t1,t2]内输出CSM信号的平 突细胞数量有关,因为树突细胞成熟越频繁,则需动态增加群均值,这个DC的生命期不断地减去CSM,当为零时则其变为 体生命期的范围,乜就得增大群体大小。 成熟DC。 2DCA的运行时间属性分析 ∑丌1(O()) N∑丌1(0(t) 则δ N-1 为了对DCA的运行时间变量进行评估,本文提出两个变 量作为改变算法运行时间行为的量化指标,它们分别是大小为 恨据定理1.如果能确定生成群体生命期的等差数列、第 N的DC群体中成熟的DC的数量δ(也就是那些达到终止条个DC的生命期与d的值,则可计算在时间区间[1,12]内成 件然后被重置的树突胞的数量)、被处理的抗原数量A。成熟的C数量。 熟的DC数量指示处理的信息量与输入数据流中的 signal实例 定理2 Gaussian分布。如果DC群体的生命期由 Gaussian 相关,而被处理的抗原数量意味着处理的信息量与输入数据流分布x-N(A,2),那么式(6)成立。 中的 antigen实例相关。对这两个变量属性进行公式化还涉及 N∑丌1O(1) N∑丌10(1) 到DC采样时间区间[t1,t2]={1,t1+1,…,2}。如果使用此 95.44% 2)(t2-11) 算法的检测系统要实现在线部署,则这两个参数就非常关键, 因为在线检测系统通常要求执行连续检测,并且适应于实时环 境的改变。 其中:P(·)表示概率算子,N表示群体大小,8表示在时间区 2.1成熟的树突细胞数量 间[t1,t2内群体中成熟的DC数量。 证明设群休中DC生命期均值为η2,由于DC群休中 定叉1成熟DC( matured DC)。群体中一个树突细胞 DC每采集到一个信号,就计算CSM的值,然后将其生命期的 DC的生命期x满足高斯分布x~N(p,a2),那么其生命期均值 n2的方差为a2/N,n2也满足 Gaussian分布n2~N(,a2/N) 值减去CSM。如果在某个时刻DC的生命期值为0.则该DC2根据高斯分布由线性质有 称为成熟的。 P(-2≤2≤+2—)=95.44% 在一个时间区间内成熟的DC数量涉及到DC群体的重置 频率,它表示DC群体对输入数据流进行处理的工作荷绂,因 祥体中个DC在时间区间[t1,t2内输出CSH信号的平 而能指示是否需要对系统的当前配置进行调整。如果群体中 ∑丌1(O(t)) DC被重置的频率高,则大多数DC在获得足够的信息之前均值为9==1。因此δ可以计算为 就变为成熟而被重置,不利于群体对数据流的处理。因此,DC 群休生命期的范围应被扩展,使得更多的信息被群伓获得并加 N∑m1(O(t)) 6=1」 以处理。在扩展DC群体生命期范围的同时,为避免生命期的 值出现稀疏,应增加DC群体的大小N。 N∑丌10(1) N∑丌10(1) DC群体中成熟DC的数量依赖于用于生成DC生命期的P 」≤8≤L 分布区数以及在某个时间区间内输人数据流中的数据。为简 (-2=)(12-1) +2)(2-1)95.44% 易起见,均匀分布( uniform distribulion)和高斯分布( Gaussian 可以看出生命期均值η2的上下界可以用于推导出群体中 distribution)分别用于生成群体中n的初始生命期。群体中成熟DC的数量范围 成熟DC的数量通过CSM信号的平均值与DC群体生命期的 根摒定理2,如果DC群体的生命期值满足 Gaussian分布, 平均值进行计算获得。集中讨论在给定时间区间内变为成熟并且知道了均值和标准差、DC群体大小N、在时间区间 DC的平均数量,而不是在某一代中的具体数量。 [1,,内输入数据的个数,则有95%的概率能获知群体中成 定理均匀分布。如果群体中DC生命期值通过等差数熟DC数量的上下界。因而能在实时场景中为系统调整提供 列生成x1=x1+(i-1)d,此处x;为第i个DC的生命期(i 足够的信息。 2,…,N),x1为第一个DC的生命期,为连续两个DC生命期22处理的抗原数量 的间隔。DC群体中成熟DC的数量为 定义2处理的抗原( processed antigeN)。群体中的DC接 20 计算机应用研究 笃33卷 收输入数据流屮的 antigen和 signal,对 antigen进行顺序采样收矩阵与检测性能之间的关系等。 集,对 signal执行信号处理机制。如果DC,在时刻t采样收集参考文献: 到抗原a,并且此刻某个DC的生命期为零,则该DC呈递的抗[1 Zhao Zengshun, Feng Xian, Lin Yan)an,ean. Evolved neural net- 原称为处理的抗原。 work ensemble by multiple heterogeneous swarm intelligence J I 文献[11]中提出利用分片( Segmentation)思想高效率地改 Neuro Computing,2015,149(2):29-38. 进了检测精度,这是因为被处理的抗原数量决定了是否有必要2 De castroL n, Timmis j. Artificial immune systerms: H torula 分析当前批次的被处理信息。与输入数据流中的 antigen不 tional intelligenee approach_ M]. London: Springer, 2002 同,被处理的 antigens是指那些被成熟的DC呈递的 antigen 3 Greensmith J. The dendritic cell algorithm[ D]. Nottingham: Univer sity of Nottingham, 2007 因此硏究被处理的 antigen数量与算法输入流屮数据量之间的 [4 Greensmith J, Aieketin U. Dendritic cells for SYN sean delection 关系是对算法研究的基础,尤其对开发将分片思想集成到 [C//Proc of Genetic and Evolutionary Computation Conference DCA更是非常重要。可以利用基于输入数据流的被处理的 LS 1.: Elsevier Science Limited, 2007: 49-56 mIllicell的数量而获得的先验知识来决定合适的分片大小。因5」 Al-llammadi a, Aicketin U, Greensmith I. dCA for bot detection 此本节硏究被处理的 antigen数量与输入流中数据,特别是输 [C]//Proc of IEEE World Congress on Computational Intelligence 入数据流中抗原数量之间的关系并使之公式化。 2008:1807-1816 定理3设A为在给定的时间区间[1,2]内处理的抗原60, Greensmith J. Mckean,. et aL. The application of a den 数量,c=δmdN,d=modN,其中§是DC群体的平均牛命 national Conference on Artificial Immune System. Berlin: Springer 期,θ是输人数据流屮含有的抗原总数。则有 2007:204-215 (-N31)(1+131)ifc<d [7] Greensmith J, Feyereisl J, Aickelin U. The DCA SOMe comparison A (7) a comparative study bel ween two biologically-inspired algorithms[ J] )年 Evolutionary Intelligence, 2008, 1(2):85-112 [8 Stibor T, Oates R, Kendall G, et al. Geometrical insights into the den 证明对输入数据流中抗原和信号的处理机制是不一样 dritic cell algorithm[ C]//Proc of the 1 l th Annual Confe 的。输入数据流中所有θ个抗原被N个DC顺序采样,DC的 netic and Evolutionary Computation. New York: ACM 2009 编号为i=modN,即第1个抗原被第1个DC采样,第2个抗 1275-1282 原被第2个DC采样,…,第N个抗原被第N个DC采样,第「91 Oates r. The suitability of the dendritic cell algorithm for robotic se N+1个抗原又被第1个DC采样。但输入数据流屮每个信号 curity applications [D. Nottingham University of Nottingham 都要被群体中每个DC收集并进行信号转换,当某个时刻某个 2010 DC的生命期为零时,该DC成熟并输出其信号值,而恰在此前 [10] Gu Feng, Greensmith J, Aickelin U. The dendritic cell algorithm for I M//Biologically d Network 被DC采样收集的抗原就称为处理的抗原。 Sensing: Algorithms and Architectures. S.I.: IGI Global, 2012 c=5-M」,d=0-MJ(将模运算转换为下限函数) [ Il Greensmith J, Aickelin U. The deterministic dendritic cell algorithm [CI//Proc of the 7th International Conference on Artificial Immune A=c(1+16)=(gM5』)(1 2008:291303. cHe2c≥d [12 Gu Feng, Greensmith J, Aickelin U. Integrating real-time analysis with the dendritic cell algorithm through segmentation[C1/Proe of 入=c 」+d=(5-N-NN)x」 the 1 l th Genetic and Evolutionary Computation Conference. New 在此,处理的抗原数量的公式化揭示了算法的运行时间变 York. ACM Press 2009. 1203-1210 量与输入数据流之间的关系,即与群体大小、输入数据流中抗[l3] Elberfeld M, Textor j.丶 Negative selection al gorithms on strings with efficient training and lincar-time classification[ J. Theoretical Com 原的数量以及群体的平均生命期有关,而与实际运行的算法无 puter Science,2011,412(6):534-542 关,这为算法用于解决特定问題时进行调整提供了理论基础。 14] arges C. Rigorous runtime analysis of inversely fitness proportional mutation rates[C //Parallel Problem Solving from Nature. Berlin 3结束语 Springer-Verlag, 2008: 112-122. 本文给出了两个重要的变量:处理的抗原数与成熟的DC15 J Arges C. On the utility of the population size for inversely fitness pro portional mutation rates[ C]//Proc of the 10th ACM SIGEVO Work- 数量,并对它们进行了公式化。这两个变量显小出在给定时间 shop on Foundations of Genetic Algorithms. New York: ACM Press 区间内基于输人效据流的算法行为,并与具体的算法运行无 2009:39-46 关。在实时坼境检测时,这两个变量可被用于动态调节系统配[l6] Timmis J, Home a, Stibor t,etal. Theoretical advance in artificial 置的指示器;针对异常检测问题,还可以刈算法的这些属性的 immune systems[ J]. Theoretical Computer Science, 2008, 403 有益之处作进步的研究。 (1);11-32 未来的工作包括对DCA进一步的开发,使之成为自动的、[17] Janse Zarges C. Analyzing different variants of immune inspired 自适应的在线检测系统;构建由各种概率密度函数生成的合成 somatic contiguous hy permutations J]. Theoretical Computer Science,2011,412(6):517-533. 数据集用于测试本文中的定理与公式;进一步研究算法的其他 18 Fang Xianjin, Wang Li. Theoretical investigation into the dendritic 属性,包括由每个DC产生的活动窗∏的作用、不同方法产生 cells algorithm[I. Journal of Beij ing Institute of Technology 的DC群体的初始生命期,以及冂C群体的大小、信号转换权值 2014(3

...展开详情
试读 4P 论文研究-树突细胞算法的运行时间属性分析.pdf
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-树突细胞算法的运行时间属性分析.pdf 6积分/C币 立即下载
    1/4
    论文研究-树突细胞算法的运行时间属性分析.pdf第1页
    论文研究-树突细胞算法的运行时间属性分析.pdf第2页

    试读已结束,剩余2页未读...

    6积分/C币 立即下载 >