A Novel Negative Selection Algorithm with Optimal Worst-case Training Time Complexity for R-chunk Detectors

Abstract
Objectives: To generate complete and non-redundant detector set with optimal worst-case time complexity.

Methods: In this study, a novel exact matching and string-based Negative Selection Algorithm utilizing r-chunk detectors is proposed. Improved algorithms are tested on some data sets; the experiments’ results are compared with recently published ones. Moreover, algorithms’ complexities are also proved mathematically.

Findings: For string-based Artificial Immune Systems, r-chunk detector is the most common detector type and their generation complexity is one of the important factors considered in the literature. We proposed optimal algorithms based on automata to present all detectors.

Novelty/applications: The algorithm could generate the representation of complete and nonredundant detector set with optimal worst-case time complexity. To the best of our knowledge, the algorithm is the first one to possess such worst-case training time complexity.

Keywords: Artificial Immune Systems, Negative Selection Algorithms, Positive Selection Algorithms, Detector Sets, Self, Non-self