Negative selection algorithm based on grid file of the feature space

Negative selection algorithm (NSA) is an important algorithm for the generation of artificial immune detectors. However, the randomly generated candidate detectors have to be compared with the whole self set to exclude self reactive detectors. The inefficiency of the comparing process seriously limited the application of immune algorithms. Therefore, a new negative selection algorithm GF-RNSA is proposed in the paper. Firstly, the feature space is divided into a number of grid cells, and then detectors are separately generated in each cell. As candidate detectors just need to compare with the self antigens located in the same cell rather than with the whole self set, the detector training can be more efficient. The theoretical analysis demonstrated that the time complexity of GF-RNSA is effectively reduced that the exponential relationships between self size and time complexity in traditional NSAs is eliminated. The experimental results showed that: not only the time cost of negative selection, but also the time cost of data preprocess and detection are reduced, while the detection accuracy is not much declined.