dnyNSA: A Novel Real-Value Based Negative Selection Algorithm

摘要

Real-value based negative selection algorithm (NSA) is an important detector generation algorithm of Artificial Immune System. Traditional real-value based negative selection algorithm generates immune detectors randomly and does not consider the sample distribution, therefore too many candidate detectors overlap in the feature space resulting in excessive redundancy. This leads to a low efficiency of detector generation and decreases the performance of NSA. To aim at this problem, the paper proposes a novel real-value negative selection algorithm based on Delaunay triangulation (dnyNSA). Firstly, dnyNSA uses Delaunay triangulation method to analyze the topological structure of training dataset and produces a set of simplicial cells (triangle in 2-dimensional space and tetrahedron in 3-dimensional space, etc.). Then, based on the simplicial cell circum-circle(-sphere) property, dnyNSA generates detectors in more reasonable position and size. Therefore, it only needs a small number of detectors to cover the same feature space, avoiding the generation of redundant detectors in traditional random mode, which greatly improves the efficiency of NSA. Theoretical analysis showed the time complexity of dnyNSA is in logarithmic level. The experimental results showed that, compared with the RNSA and V-Detector, dnyNSA can raise the detector generation efficiency over ten times while maintain similar detection performance.