skip to main content
10.1145/1543834.1543920acmconferencesArticle/Chapter ViewAbstractPublication PagesgecConference Proceedingsconference-collections
research-article

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

Published: 12 June 2009 Publication History

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]
He, J. and Yao, X. 2001. Drift Analysis and Average Time Complexity of Evolutionary Algorithms. Artificial Intelligence. 127, 57--85.
[2]
Dipankar, D. and Fernando, N. 2008. Immunological Computation: Theory and Applications. Auerbach Publications.
[3]
Castro, L. N. d. and Timmis, J. 2002. Artificial Immune Systems: A New Computational Intelligence Approach. Springer-Verlag.
[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]
Forrest, S., Perelson, A. S., Allen, L. and Cherukuri, R. 1994. Self-Nonself Discrimination in a Computer. In IEEE Computer Society Symposium on Research in Security and Privacy, Los Alamitos, CA. 202--212.
[8]
D'haeseleer, P., Forrest, S. and Helman, P. 1996. An Immunological Approach to Change Detection: Algorithms, Analysis and Implications. In IEEE Symposium on Security and Privacy, Los Alamitos, CA. 110--119.
[9]
D'haeseleer, P. 1996. An Immunological Approach to Change Detection: Theoretical Results. In IEEE Computer Security Foundations Workshop. 18--26.
[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]
Kim, J. and Bentley, P. J. 2002. Towards an Artificial Immune System for Network Intrusion Detection: an Investigation of Dynamic Clonal Selection. In Proceedings of the Congress on Evolutionary Computation. 1015--1020.
[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]
Zhang, Y., Luo, W., Zhang, Z., Li, B. and Wang, X. 2008. A Hardware/Software Partitioning Algorithm Based on Artificial Immune Principles. Applied Soft Computing. 8, 383--391.
[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]
He, J. and Yao, X. 2004. A Study of Drift Analysis for Estimating Computation Time of Evolutionary Algorithms. Natural Computing. 3, 21--35.
[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. S., Gary, B. L. and Gilbert, L. P. 2005. An Evolutionary Algorithm to Generate Hyper-Ellipsoid Detectors for Negative Selection. In Proceedings of the Conference on Genetic and Evolutionary Computation, Washington, DC, USA. 1, 337--344.
[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 and H. Ohashi. 2009. A Negative Selection Algorithm for Classification and Reduction of the Noise Effect. Applied Soft Computing. Elsevier Science Publishers B.V.Amsterdam, The Netherlands. 9, 1, 431--438.
[28]
Stefan, D., Thomas, J. and Ingo, W. 2002. On The Analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science. 276, 51--81.

Cited By

View all
  • (2009)A Preliminary Study on Why Using the Nonself Detector Set for Anomaly Detection in Artificial Immune SystemsProceedings of the 2009 International Conference on Computational Intelligence and Security - Volume 0110.1109/CIS.2009.165(559-564)Online publication date: 11-Dec-2009

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GEC '09: Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation
      June 2009
      1112 pages
      ISBN:9781605583266
      DOI:10.1145/1543834
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 12 June 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. anomaly detection
      2. artificial immune system
      3. drift analysis
      4. evolutionary negative selection algorithm
      5. time complexity

      Qualifiers

      • Research-article

      Conference

      GEC '09
      Sponsor:

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)1
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 22 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2009)A Preliminary Study on Why Using the Nonself Detector Set for Anomaly Detection in Artificial Immune SystemsProceedings of the 2009 International Conference on Computational Intelligence and Security - Volume 0110.1109/CIS.2009.165(559-564)Online publication date: 11-Dec-2009

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media