An Antigen Space Triangulation Coverage Based Real-Value Negative Selection Algorithm

Abstract

Negative selection algorithm (NSA) is an important detector generation algorithm of artificial immune system (AIS). Traditional NSAs randomly generate detectors in the whole antigen space without considering the distribution of self/non-self antigens, therefore it is difficult for detectors to cover the whole antigen space evenly and a seriously time-consuming self-tolerance process is required. Aiming at the problem, we proposed a novel NSA based on antigen space triangulation coverage (ASTC) called ASTC-RNSA. In order to avoid the randomness in traditional NSAs, the proposed algorithm employed Delaunay Triangulation method from computational geometry to divide the self space into simplicial cells, which are utilized to determine the detector positions. Then, the overlaps between simplicial cells and self-antigens are removed to form a set of triangulation coverage areas. Finally, immune detectors which only covered non-self antigens space are generated in each triangulation coverage area. After Delaunay triangulation of antigen space, ASTC-RNSA can directly determine sui detector positions and avoid the time-consuming self-tolerance process of traditional NSAs. The analysis result shows that the time complexity of ASTC-RNSA is reduced from traditional exponential level to logarithmic level. The experimental results on several UCI datasets and artificial datasets show that the proposed algorithm can achieve more than 10 times the detector generation efficiency while maintaining similar detection performance with the most widely used representative typical algorithm, V-Detector.

Keywords

• Negative selection algorithm
• detector
• artificial immune system
• Delaunay triangulation