树突细胞算法及其理论研究

On Dendritic Cell Algorithm and its Theoretical Investigation

树突细胞算法(DCA)是受先天性免疫系统中树突细胞(DCs)功能的启发而开发的算法,它已被成功运用于许多计算机安全相关领域。但是对DCA理论方面的分析工作很少,对算法大多数理论方面的研究也较少出现。而其它的人工免疫算法如负选择算法、克隆选择算法在理论方面的研究工作却出现在很多文献中。因此对DCA算法进行相似的理论分析,确定算法的运行时间复杂度,揭示其它算法的属性就显得非常重要。根据算法执行的3个阶段,通过引入3个运行时间变量实现对DCA算法的理论分析。标准DCA算法取得的运行时间复杂度下界为Ω(n),而在最坏情况下的时间复杂度为O(n2)。另外,如果利用"分片"方法实现DCA的在线分析组件,则算法的运行时间复杂度可以改进为O(max(nN,nδ))。

Dendritic cell algorithm（DCA）is inspired by functions of the dendritic cells（DCs）of the innate immune system,and has been successfully applied to numerous security-related problems.However,theoretical analysis of the DCA has barely been performed,and most theoretical aspects of the algorithm have not yet been revealed.Other immune inspired algorithms,such as negative and clonal selection algorithms,are theoretically presented in many literatures.As a result,it is important to conduct a similar theoretical analysis of the DCA,and determine its runtime complexity and other algorithmic properties in line with other artificial immune algorithms.Theoretical analysis was implemented via introduction of three runtime variables in terms of three phases of the algorithm.The standard DCA achieves a lower bound ofΩ（n）runtime complexity and an upper bound of O（n2）runtime complexity under the worst case.In addition,the algorithm＇s runtime complexity can be improved to O（max（nN,nδ））by using segmentation approach for online analysis component.