A Detector Generating Algorithm Based on Interval Partition

Abstract

Based on the functions and some relevant theories of the biological immune system, an artificial immune system is established to solve the practical problems for computing systems. At present, the artificial immune system includes two major categories: the mechanism of non-self recognition and immune network, the most important of which is negative selection algorithm. The negative selection algorithm is proposed to simulate the formation and running mechanism of T cells for the immune system in 1994. In this algorithm, one of the key steps is the detector generation. Unfortunately, the current detector generating algorithms have detector generation inefficiencies, holes area, and redundant detector problems to some degree. In this paper, from the perspective of one dimension, a novel detector generating algorithm that is based on interval partition is proposed. At the beginning of this algorithm, we make the maximal interval be the initial detector; second, this detector should experience the training of self-tolerance. According to the matching rule, we let this detector match the given collection of selves; then we remove the points from the interval detector which matches the selves. At the same time, we divide the interval into two parts at this point and have the candidate detectors optimized by the corresponding interval collations and amalgamations. That is to say, the initial detector interval is divided recursively according to the spatial locations of selves. At last, we can get a set of excellent mature detectors, which can be used to protect the system security. To illustrate the advantage of this algorithm, we have given an example. From this example, we can declare that the algorithm improves the current detector generations and matching rules greatly. It also helps to remove the holes area and redundant detectors. Therefore, both the detector generation efficiency and the detecting efficiency are well improved. By the theoretical analysis and comparison, the system can detect a large number of non-self antigens only using a small quantity of detectors. Obviously, the algorithm achieves the high non-self identification system.

Keywords:

• Negative selection algorithm
• Detector generating algorithm
• Matching rule

This work was supported by the National science Foundation of China (No: 60773049), the Science Foundation of Jiangsu (No: BK2006073,BK2007086).