A Real-Valued Negative Selection Algorithm Based on Grid for Anomaly Detection

Abstract EN

Negative selection algorithm is one of the main algorithms of artificial immune systems.

However, candidate detectors randomly generated by traditional negative selection algorithms need to conduct self-tolerance with all selves in the training set in order to eliminate the immunological reaction.

The matching process is the main time cost, which results in low generation efficiencies of detectors and application limitations of immune algorithms.

A novel algorithm is proposed, named GB-RNSA.

The algorithm analyzes distributions of the self set in real space and regards the n-dimensional [0, 1] space as the biggest grid.

Then the biggest grid is divided into a finite number of sub grids, and selves are filled in the corresponding subgrids at the meantime.

The randomly generated candidate detector only needs to match selves who are in the grid where the detector is and in its neighbor grids, instead of all selves, which reduces the time cost of distance calculations.

And before adding the candidate detector into mature detector set, certain methods are adopted to reduce duplication coverage between detectors, which achieves fewer detectors covering the nonself space as much as possible.

Theory analysis and experimental results demonstrate that GB-RNSA lowers the number of detectors, time complexity, and false alarm rate.