Efficient Algorithms for String-Based Negative Selection

Michael Elberfeld, Johannes Textor


String-based negative selection is an immune-inspired classification scheme: Given a self-set S of strings, generate a set D of detectors that do not match any element of S. Then, use these detectors to partition a monitor set M into self and non-self elements. Implementations of this scheme are often impractical because they need exponential time in the size of S to construct D. Here, we consider r-chunk and r-contiguous detectors, two common implementations that suffer from this problem, and show that compressed representations of D are constructible in polynomial time for any given S and r. Since these representations can themselves be used to classify the elements in M, the worst-case running time of r-chunk and r-contiguous detector based negative selection is reduced from exponential to polynomial.
Original languageEnglish
Title of host publicationProceedings of the 8th International Conference on Artificial Immune Systems (ICARIS 2009)
PublisherSpringer Verlag
Publication date2009
Publication statusPublished - 2009

Cite this