计算机科学 ›› 2015, Vol. 42 ›› Issue (2): 131-133.doi: 10.11896/j.issn.1002-137X.2015.02.028
方贤进,王丽,康佳,刘佳
FANG Xian-jin, WANG Li, KANG Jia and LIU Jia
摘要: 树突细胞算法(DCA)是受先天性免疫系统中树突细胞(DCs)功能的启发而开发的算法,它已被成功运用于许多计算机安全相关领域。但是对DCA理论方面的分析工作很少,对算法大多数理论方面的研究也较少出现。而其它的人工免疫算法如负选择算法、克隆选择算法在理论方面的研究工作却出现在很多文献中。因此对DCA算法进行相似的理论分析,确定算法的运行时间复杂度,揭示其它算法的属性就显得非常重要。根据算法执行的3个阶段,通过引入3个运行时间变量实现对DCA算法的理论分析。标准DCA算法取得的运行时间复杂度下界为Ω(n),而在最坏情况下的时间复杂度为O(n2)。另外,如果利用“分片”方法实现DCA的在线分析组件,则算法的运行时间复杂度可以改进为O(max(nN,nδ))。
[1] Greensmith J.The Dendritic Cell Algorithm[D].Nottingham:University of Nottingham,2007 [2] Leandro N,De Castro J T.Artificial Immune Systems:A New Computational Intelligence Approach[M].London:Springer-Verlag,Inc,2002 [3] Greensmith U A.Dendritic Cells for SYN Scan Detection[C]∥Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2007).London,UK:ACM Press,2007:49-56 [4] Al-Hammadi Y,Aickelin U,Greensmith J.DCA for Bot Detec-tion[C]∥Proceedings of the IEEE World Congress on Computational Intelligence (WCCI 2008).Berlin Heidelberg:Springer-Verlag,2008:1807-1816 [5] Oates R,J G,Aickelin U,et al.The Application of a Dendritic Cell Algorithm to a Robotic Classifier[C]∥Proceedings of the 6th International Conference on Artificial Immune (ICARIS 2007).2007:204-215 [6] Greensmith J,Feyereisl J,Aickelin U.The DCA:SOMe Comparison A comparative study between two biologically-inspired algorithms[J].Evolutionary Intelligence,2008,1(2):85-112 [7] Stibor T R O,Kendall G,et al.Geometrical insights into the dendritic cell algorithm[C]∥Proc.of the Genetic and Evolutionary Computation Conference (GECCO).2009:1275-1282 [8] Oates R.The Suitability of the Dendritic Cell Algorithm for Robotic Security Applications[D].Nottingham:School of Computer Science,University of Nottingham,2010 [9] Feng Gu,Julie G,Uwe A.The Dendritic Cell Algorithm for In-trusion Detection[J].Bio-Inspired Communications and Networking,IGI Global,2011:84-102 [10] Greensmith J,U A.The Deterministic Dendritic Cell Algorithm[C]∥Proceedings of the 7th International Conference on Artificial Immune Systems (ICARIS 2008).Phuket,Thailand.Lecture Notes in Computer Science Volume 5132,2008:291-302 [11] Gu Feng,J G,Aickelin U.Integrating Real-Time Analysis With The Dendritic Cell Algorithm Through Segmentation[C]∥Proceedings of the Genetic and Evolutionary Computation Conference(GECCO2009).Montreal,Canada,2009 (下转第156页)(上接第133页) [12] Elberfeld M,J T.Negative selection algorithms on strings with efficient training and linear-time classification[J].Theoretical Computer Sicence,2011,412(6):534-542 [13] Zarges C.Rigorous runtime analysis of inversely fitness proportional muation rates[C]∥Proceedings of Parallel Problem Solving from Nature (PPSN).LNCS 5199,2008:112-122 [14] Zarges C.On the utility of the population size for inversely fitness proportional mutation rates[C]∥Proceedings of the 10th ACM SIGEVO Workshop on Fundations of Genetic Algorithms (FOGA).2009:39-46 [15] Timmis J,Home A,Stibor T,et al.Theoretical advance in artificial immune systems[J].Theoretical Computer Science,2008(403):11-32 [16] Janse T,Zarges C.Analyzing different variants of immune inspired somatic contiguous hypermutations[J].Theoretical Computer Science,2011,412(6):517-533 |
No related articles found! |
|