On average time complexity of evolutionary negative selection algorithms for anomaly detection

ABSTRACT

Evolutionary Negative Selection Algorithms have been proposed and used in artificial immune system community for years. However, there are no theoretical analyses about the average time complexity of such algorithms. In this paper, the average time complexity of Evolutionary Negative Selection Algorithms for anomaly detection is studied, and the results demonstrate that its average time complexity depends on the self set very much. Some simulation experiments are done, and it is demonstrated that the theoretical results approximately agree with the experimental results. The work in this paper not only gives the average time complexity of Evolutionary Negative Selection Algorithms for the first time, but also would be helpful to understand why different immune responses (i.e. primary/cross-reactive/secondary immune response) in biological immune system have different efficiencies.

REFERENCES

• 1: Drift analysis and average time complexity of evolutionary algorithms, Artificial Intelligence, v.127 n.1, p.57-85, March 2001 [doi>10.1016/S0004-3702(01)00058-3]
• 2: Dipankar Dasgupta , Fernando Nino, Immunological Computation: Theory and Applications, Auerbach Publications, Boston, MA, 2008
• 3: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 4: Dasgupta, D., Ji, Z. and Gonzalez, F. 2003. Artificial Immune System (AIS) Research in the Last Five Years. IEEE Congress on Evolutionary Computation. 1, 123--130.
• 5: Luo, W., Wang, J. and Wang, X. 2005. Evolutionary Negative Selection Algorithms for Anomaly Detection. In 8th Joint Conference on Information Sciences, Salt Lake City, Utah. 440--445.
• 6: Castro, L. N. d. and Zuben, F. J. V. 2002. Learning and Optimization Using the Clonal Selection Principle. IEEE Transactions on Evolutionary Computation. 6, 239--251.
• 7: Stephanie Forrest , Alan S. Perelson , Lawrence Allen , Rajesh Cherukuri, Self-Nonself Discrimination in a Computer, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.202, May 16-18, 1994
• 8: Patrik D'haeseleer , Stephanie Forrest , Paul Helman, An Immunological Approach to Change Detection: Algorithms, Analysis and Implications, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.110, May 06-08, 1996
• 9: Patrik D'haeseleer, An Immunological Approach to Change Detection: Theoretical Results, Proceedings of the 9th IEEE workshop on Computer Security Foundations, p.18, March 10-12, 1996
• 10: Kim, J. 2002. Integrating Artificial Immune Algorithms for Intrusion Detection. Ph.D. Thesis: Department of Computer Science, University College London.
• 11: Kim, J. and Bentley, P. J. 1999. Negative Selection and Niching by an Artificial Immune System for Network Intrusion Detection. In Genetic and Evolutionary Computation Conference. Orlando, Florida. 149--158.
• 12: P. J. Bentley, Towards an artificial immune system for network intrusion detection: an investigation of dynamic clonal selection, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1015-1020, May 12-17, 2002
• 13: Kim, J. and Bentley, P. J. 2002. A Model of Gene Library Evolution in The Dynamic Clonal Selection Algorithm. In Proceedings of the First International Conference on Artificial Immune Systems, Canterbury, 175--182.
• 14: Luo, W., Cao, X. and Wang, X. 2005. Research on Adaptively Generating Detector Algorithm. Acta Automatica Sinica. 31, 907--16 (In Chinese).
• 15: Luo, W., Guo, P. and Wang, X. 2008. On Convergence of Evolutionary Negative Selection Algorithms for Anomaly Detection. IEEE Congress on Evolutionary Computation. 2933--9.
• 16: Yiguo Zhang , Wenjian Luo , Zeming Zhang , Bin Li , Xufa Wang, A hardware/software partitioning algorithm based on artificial immune principles, Applied Soft Computing, v.8 n.1, p.383-391, January, 2008 [doi>10.1016/j.asoc.2007.03.003]
• 17: Luo, W., Zhang, Y., Wang, X. and Wang, X. 2006. Experimental Analyses of Evolutionary Negative Selection Algorithm for Function Optimization. Journal of Harbin Engineering University. 27(B07), 158--163 (In Chinese).
• 18: Zhang, Z., Luo, W. and Wang, X. 2007. Research of Mobile Robots Path Planning Algorithm Based on Immune Evolutionary Negative Selection Mechanism. Journal of Electronics and Information Technology. 29(8), 1987--1991 (In Chinese).
• 19: Cao, X., Zhang, S. and Wang, X. 2001. Immune Optimization System Based on Immune Recognition. In International Conference on Neural Information Processing. 1,3, 535--541.
• 20: Gonzalez, F. and Dasgupta, D. 2002. An Immunogenetic Approach to Intrusion Detection. In Proceedings of the Genetic and Evolutionary Computation Conference, New York.
• 21: Jun He , Xin Yao, A study of drift analysis for estimating computation time of evolutionary algorithms, Natural Computing: an international journal, v.3 n.1, p.21-35, 2004 [doi>10.1023/B:NACO.0000023417.31393.c7]
• 22: He, J. and Yao, X. 2002. From an Individual to a Population: An Analysis of The First Hitting Time of Populationbased Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation. 6, 5, 495--511.
• 23: Luo, W., Zhang, Z. and Wang, X. 2006. A Heuristic Detector Generation Algorithm for Negative Selection Algorithm with Hamming Distance Partial Matching Rule. In the International Conference on Artificial Immune Systems, LNCS 4163, Instituto Gulbenkian de Ciência, Oeiras, Portugal. 229--243.
• 24: Joseph M. Shapiro , Gary B. Lamont , Gilbert L. Peterson, An evolutionary algorithm to generate hyper-ellipsoid detectors for negative selection, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068063]
• 25: Balachandran, S., Dasgupta, D., Nino, F. and Garrett, D. 2007. A Framework for Evolving Multi-Shaped Detectors in Negative Selection. In Proceeding of the IEEE Symposium Series on Computational Intelligence. 401--408.
• 26: Zhang, S., Cao, X. and Wang, X. 2002. Immune Algorithm Based on Immune Recognition. Acta Electronica Sinica. 30, 12, 1840--1844 (In Chinese).
• 27: K. Igawa , H. Ohashi, A negative selection algorithm for classification and reduction of the noise effect, Applied Soft Computing, v.9 n.1, p.431-438, January, 2009 [doi>10.1016/j.asoc.2008.05.003]
• 28: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Theory, Verification

Keywords:
anomaly detection, artificial immune system, drift analysis, evolutionary negative selection algorithm, time complexity