1 Introduction

The negative selection algorithm (NSA) is one of the main algorithms in artificial immune systems. It simulates the immune tolerance in T-cell maturation process of biological immune system, and achieves effective recognition of non-self antigens by clearing self-reactive candidate detectors without any prior knowledge. It is widely applied in the fields of fault diagnosis, intrusion detection, pattern recognition and etc. [1–8, 24, 29]

Forrest et al. [9] originally established the framework of negative selection algorithms in 1994, and adopted binary string representation of antigens (samples) and antibodies (detectors), and r-contiguous-bit matching method to compute the matching degree between antibodies and antigens, which is successfully applied in anomaly detection system. Balthrop et al. [10] pointed out the vulnerabilities which exist in the r-contiguous-bit matching algorithm and presented an improved r-chunk matching mechanism.

For the lack of binary representation in dealing with numerical data and multi-dimensional data, Gonzalez and Dasgupta [11] proposed a real-valued negative selection algorithm (RNSA), which encodes antigens and antibodies in n-dimensional [0, 1] space and adopts Minkowski distance to compute the matching degree between antigens and antibodies. Because radiuses of detectors are the same size and are difficult to accurately determine, there are holes in the algorithm and the detection rate is not high. Zhou et al. [12, 13] presented a real-valued negative selection algorithm with variable-sized detector (V-Detector), which dynamically determines the detector’s radius by calculating the distance between the center of the candidate detector and the closest self antigen. The work also proposed a method for computing detectors’ coverage rate in non-self space based on the probability, and obtained better detection results. Joseph et al. [14] introduced hyper-ellipsoidal detectors in negative selection algorithm, Ostaszewski et al. [15] introduced super-rectangular detectors, and Zhang et al. [16] introduced a matrix-based detector model, which all achieve the original coverage with fewer detectors. Gao et al. [17] put forward a negative selection algorithm based on genetic algorithms, which searches optimal detectors by genetic mechanism. Yang et al. [18] proposed a multi-population genetic based negative selection algorithm in which the self set was divided according to features and sub populations evolved independently, reducing redundant coverage between detectors. Stibor [19] put forward a classification method of self detectors, which dynamically adjusted the radius of self by ROC analysis to balance the detection rate and the false alarm rate. Chen et al. [20] presented a negative selection algorithm based on hierarchical clustering of self set, which preprocessed the self set to increase the efficiency of detectors’ generation.

How to generate efficient detector set is the key of negative selection algorithms. The work in [1, 9, 20, 21, 23] pointed out that current problems of negative selection algorithms are as follows. First, the time complexity is \(\mathrm {O(-ln}P_{tp}\mathrm {\cdot }N_{s}\mathrm {/(}P^{\prime }\mathrm {\cdot }{(1-P^{\prime })}^{N_{s}}\mathrm {)}\), where P t p is the detection rate, N s is the size of self set, and \(P^{\prime }\) is the self-reaction rate between detectors. The cost of detectors’ generation is exponential to the size of self set, the generation efficiency of mature detectors is low, and the execution time severely limits practical applications. Second, for a given detection rate P t p , the size of required detector set \(N_{d}\;\approx \; \text {ln}(1-P_{tp})/\text {ln}(1-P^{\prime })\) . The number of detectors is large, and there exists a lot of redundant coverage between detectors, making the detection time much longer. Third, pathogens are always evolving in the direction of vulnerabilities. Holes exist more or less in various negative selection algorithms, resulting in low detection rate.

This paper presents a real-valued negative selection algorithm based on immune optimization (IO-RNSA). The main contributions are as follows. First, introduces the immune optimization mechanism. Detectors are not randomly produced throughout the shape space, but evolved from successive generations with the self set as the initial population, which maintains the diversity of detectors and reduces the redundancy. Second, generates detectors hierarchically, and limits the random generation range of detectors. The algorithm gives priority to producing detectors of large size which are distributed in low coverage areas, decreasing the number of mature detectors. And then the algorithm generates detectors with small size which are distributed in the area close to the self space, reducing the number of vulnerabilities. Third, makes performance analysis of detectors’ generation, and shows effectiveness of the algorithm through simulations.

The remainder of this paper is organized as follows. Related work is introduced in Section 2, including two classical negative selection algorithms RNSA and V-Detector, and basic concepts of the immune optimization. The idea, implementation strategies, and theoretical analysis of IO-RNSA are described in Section 3. The effectiveness of IO-RNSA is verified in Section 4 through experiments. Finally, the conclusion is given and further work is proposed in the last section.

2 Related work

2.1 Basic definitions of RNSA

Immune events occur in the shape space S, and the process of antibodies recognizing antigens is the process of antibodies matching and binding antigens [2, 9, 22]. The algorithm discussed in this paper is based on real value. So, S is the n-dimensional [0, 1] space, and antibodies and antigens are hyper-spheres in the space.

Definition 1

The artificial immune system is expressed as Σ AIS =(X AIS ,γ AIS ,G AIS ). X AIS is the input to be detected, which may be network packets, or file signatures. The input domain can be divided into two mutually exclusive sets, which are a normal set and an abnormal one. γ A I S is the output of Σ A I S . G A I S represents the nonlinear function of the relationship between the input and output.

$$ \mathrm{\gamma }_{AIS}=G_{AIS}\left( X_{AIS} \right)=\left\{ {\begin{array}{llll} 0&X_{AIS}~belongs~to~selves\\ 1&{X}_{AIS}~belongs~to~non-selves \\ \end{array}} \right. $$
(1)

Definition 2

Antigens are represented as the tuple a g= < x,r s >. x is the location of the sample ag, and is expressed as x= < x 1,x 2,…,x n >. n is the data dimension, x i ∈[0, 1](1 < = i < = n) is the normalized value of the i th attribute of ag, and r s is the variation range of ag. The antigen set A G={a g|a g= < x,r s >,r s ∈[0, 1]} is the collection of all the samples in the space.

Definition 3

The self set \(Self\subset AG \)represents all the normal samples, and the non-self set \(Nonself\subset AG\) represents all the abnormal samples. Then, \(Self\cap Nonself=\emptyset , Self\cup Nonself=AG\).

Definition 4

The training set \(Train\subset Self\) is a subset of Self, and is the priori knowledge of detections.

Definition 5

The structure of detectors is similar to antigens, d= < y,r d >. y is the location of the detector d, and is expressed as y= < y 1,y 2,…,y n >. y i ∈[0, 1](1 < = i < = n) is the i th position vector of detector d, and r d is the radius of d. The detector set is expressed as D={d|d= < y,r d >,r d ∈[0, 1]}.

Definition 6

The affinity between antibodies and antigens is the binding strength between them. For real coding, it is usually related to the distance between antibodies and antigens. Euclidean distance is adopted in this paper.

$$ affinity\left( ag,d \right)=dist\left( ag.x,d.y \right)=\sqrt{{\sum}_{i=1}^{n}{(x_{i}-y_{i})^2}} $$
(2)

In the process of detectors’ generation, if d i s t(a g.x, d.y) < = r s +r d , the detector d triggers the immune self-reaction, and cannot become mature. In the process of detection, if d i s t(a g.x,d.y) < r d , the detector d recognizes the antigen ag as a non-self.

Definition 7

The detection rate DR is the ratio of non-self samples which are correctly recognized by detectors to the entire non-selves, and is expressed as (3), where tp represents the number of non-selves correctly recognized by detectors, and fn represents the number of non-selves wrongly recognized.

$$ DR\mathrm{=}R_{DR}\left( \mathrm{\sum}_{AIS} \right)\mathrm{=}P\left( \gamma_{AIS}\mathrm{=1/}X_{AIS}\mathrm{\in }Nonself \right)\mathrm{=}\frac{tp}{tp\mathrm{+}fn} $$
(3)

Definition 8

The false alarm rate FAR is the ratio of self samples which are wrongly recognized as non-selves by detectors to the entire selves, and is expressed as (4), where fp represents the number of selves wrongly recognized by detectors, and tn represents the number of selves correctly recognized.

$$ FAR\mathrm{=}R_{FAR}\left( \mathrm{\sum }_{AIS} \right)\mathrm{=}P\left( \gamma_{AIS}\mathrm{=1/}X_{AIS}\mathrm{\in }Self \right)\mathrm{=}\frac{fp}{fp\mathrm{+}tn} $$
(4)

In real-valued negative selection algorithms, the detection mechanism is shown in Table 1.

Table 1 Mechanism of detection
Full size table

2.2 RNSA

RNSA adopts detectors with fixed size and the preset number of detectors as the termination condition [9]. The algorithm randomly generates a candidate detector d n e w = < y,r d >, and then calculates the distance between d n e w and any self a g= < x,r s > in the training set. If the candidate does not react with any self, put d n e w into the detector set D. This algorithm is expressed in Table 2.

Table 2 Procedure of RNSA
Full size table

2.3 V-Detector

V-Detector adopts detectors with variable size and the expected coverage rate as the termination condition [12, 13]. The algorithm randomly generates the center of candidate detector y in the shape space, and then obtains the minimum Euclidean distance between y and any self ag = < x, r s >in the training set. If d i s t(y,a g.x)>r s , generate a detector d n e w = < y,r d > with y as the center and r d =d i s t(y,a g.x)−r s as the radius.

Figure 1 shows the contrasts of RNSA and V-Detector. Where, the blue area represents selves, the light gray area represents vulnerabilities, and the unfilled area represents detectors. In RNSA, there are many vulnerabilities and the detection rate is low because the radius of detectors is fixed and hard to be determined. In V-Detector, due to variable-sized detectors, detectors with large radius cover most of the non-self space and detectors with small radius cover holes, which not only reduces the number of detectors but the number of holes. As can be seen from Fig. 1, there are general problems which are also raised by the introduction section in these two algorithms: low generation efficiency of mature detectors; large number of detectors and a lot of redundant coverage resulting in longer detection time; existence of holes causing low detection rate.

Fig. 1
figure 1

Contrasts of RNSA and V-Detector

Full size image

2.4 Immune optimization

Immune optimization mechanism simulates the activation process of immune cells in the immune response [26, 27], which is used to solve problems of function optimization, combinatorial optimization and etc. When immune cells are stimulated by antigens, clonal proliferation occurs, a large number of clones are created, and then these cells differentiate into effector ones and memory ones through hyper-mutation. During proliferation, effector cells will produce a large number of antibodies, and then antibodies will replicate and hyper-mutate to increase their affinities and reach affinity maturation ultimately in order to eliminate antigens quickly. Table 3 shows the general flow of the immune optimization algorithm.

Table 3 General flow of the immune optimization algorithm
Full size table

3 IO-RNSA

3.1 Basic idea of the algorithm

In practical problems, it is impossible for normal data to be distributed randomly in the shape space. They are highly concentrated, and are located in a very small part of the space [8, 9, 28]. The main idea of the algorithm is as follows. According to the distribution of self set in shape space, the algorithm introduces the immune optimization mechanism, and generates candidate detectors hierarchically from far to near with selves as the center, which decreases the redundancy between detectors and reduces the detection holes. The algorithm adopts detectors with variable size, and expected coverage of non-self space as the termination condition for the process of detectors’ generation. Self set is regarded as the evolutionary population on which immune optimization operations will be performed. Then, the algorithm does immune selection operation, clonal proliferation operation and hyper-mutation operation on this population, and performs negative selection to obtain detectors of the first level locating far away from selves in the non-self space where coverage rate is low. Repeat the process to get detectors of the second level which locate close to the first level detectors and away from selves but closer than the first level detectors in the non-self space. The antibody mutation rate will decrease with the evolution generation increasing. When detectors are close to selves, detectors have small coverage, reducing detection holes, and when detectors are far from selves, detectors have large coverage, achieving that fewer detectors cover as much non-self space as possible. That is to say, the algorithm produces detectors with large size in low coverage areas, to be followed with detectors of small size in areas close to self space. By analogy, the detector set which satisfies conditions will be obtained finally. Steps of the algorithm are shown in Table 4.

Table 4 Steps of IO-RNSA
Full size table

3.2 Comparisons with RNSA and V-Detector

Iris data set is one of the classic machine learning data sets published by the University of California Irvine (UCI) [25], which is widely used in pattern recognition, data mining and other fields by researchers. We select data records of the category “setosa” in the data set Iris as self antigens, select “sepalL” and “sepalW” as the first dimension attribute and the second dimension attribute of antigens, and select top 20 records as the self training set. Figures 2 and 3 illustrate the idea of IO-RNSA, and differences between IO-RNSA and classic negative selection algorithms RNSA and V-Detector. Filled circles represent self individuals in the space, and unfilled circles represent detectors. RNSA produces detectors with fixed size, and V-Detector dynamically produces variable-sized detectors according to the distance between the center of detectors and the nearest self antigen. For these two algorithms, there is redundant coverage in non-self space between mature detectors with the increase of coverage rate. IO-RNSA hierarchically produces detectors from far to near, and newly-generated candidate detectors are distributed around those of the last level, avoiding from repeated coverage with mature detectors and achieving fewer detectors covering as much non-self space as possible.

Fig. 2
figure 2

Comparisons of detectors’ generation for RNSA, V-Detector and IO-RNSA (simultaneously generate three detectors)

Full size image
Fig. 3
figure 3

Comparisons of detectors’ generation for RNSA, V-Detector and IO-RNSA (to reach the expected coverage 90 %, three algorithms need 408, 56 and 32 detectors respectively)

Full size image

3.3 Immune optimization mechanism

The algorithm introduces the immune optimization mechanism, including immune selection, clonal proliferation and hyper-mutation. And it adopts the self set as the initial population, and searches in the non-self space to get optimum detectors.

The immune selection operator chooses part of antibodies to enter the next operation - clonal proliferation according to the stimulation levels of antibodies. The aim of negative selection algorithms is to cover all non-self space with optimum detectors, and it is necessary to cover the area around each self. Therefore, the algorithm selects all self individuals as the evolutionary population.

The clone operator simulates the clonal expansion mechanism in the immune response. When antibodies identify foreign antigens, clonal proliferation will occur. The number of clones for each detector is limited in this paper. Set the maximum of clones for each detector is c m a x and the minimum of clones is c m i n , then the number of clones c(d)for detector d is calculated as follows.

$$ c(d)=ceil(c_{max}-(1/t)(c_{max}-c_{min})) $$
(5)

Where, t is the evolution generation. And ceil() is a function which returns a minimum integer greater than or equal to the specified expression. The formula shows the relationship between evolution generation and clone scale. In the beginning of evolution, detectors are far away from selves, and the radius of detectors is large. So, the duplication level of detectors is low, trying to cover larger non-self space with fewer detectors. In the last stage of evolution, detectors are close to selves, and the radius of detectors is small. So, the duplication level is high, giving detectors more opportunities to fit the self space.

The mutation operator simulates the hyper-mutation mechanism in the immune response. Antibodies can change their genes randomly through mutation, and antibodies with higher affinities will be produced. In this paper, different candidate detectors will be generated in a wider scope through mutation, and variation ranges of candidate detectors in each generation are limited in different locations. The formulas are as follows.

$$ d^{\prime}.y_{i} = d.y_{i}+\beta \cdot N(0,1) 1<=i<=n $$
(6)
$$ \beta = \sqrt{n} /exp(t-1) $$
(7)
$$ \sqrt{\mathrm{n}} /exp(t) <dist(d^{\prime}.y, d.y)<= \sqrt{\mathrm{n}} /exp(t-1) $$
(8)

Where, \(d^{\prime }\) is the newly-generated candidate detector. N(0,1) is the random variable. β is the mutation rate, adjusting the variation range. n is the data dimension. It is difficult to compute for the above formulas when randomly generating new candidate detectors. So, polar coordinates are adopted. Set the polar diameter is ρ in n-dimensional space, and the polar angles are 𝜃 1 𝜃 2,…,𝜃 n−1. The above formulas are expressed as follows.

$$\begin{array}{@{}rcl@{}} d^{\prime}y_{1}&=&dy_{1}+\rho \cdot cos(\theta_{1})\\ d^{\prime}y_{2}&=&dy_{2}+\rho \cdot sin(\theta_{1})cos(\theta_{2})\\ d^{\prime}y_{n-1}&=&dy_{n-1}+\rho \cdot \sin \left( \theta_{1} \right)\sin \left( \theta_{2} \right){\ldots} cos(\theta_{n-1})\\ d^{\prime}y_{n}&=&dy_{n}+\rho \cdot sin(\theta_{1})\sin \left( \theta_{2} \right){\ldots} sin(\theta_{n-1}) \end{array} $$
(9)

Where, ρ is a random variable in [\(\sqrt n \) /exp(t), \(\mathrm {}\sqrt n \) /exp(t-1)], and 𝜃 1 𝜃 2,…,𝜃 n−1 are random variables in [0,360]. Therefore, variation range of candidate detectors in each generation is limited to a super ring.

At the early stage of detectors’ generation, the mutation rate is greater, and detectors locate mainly in the area of non-self space far from selves. After some generations, the mutation rate decreases, and detectors locate mainly in the area of non-self space close to selves. New mature detectors of each generation have different variation ranges, and cover different regions in non-self space, which reduces redundancy between detectors. When the mutate rate β is less than or equal to r s , that is to say, when the evolutionary generation t> =floor(1 + log( \(\sqrt n /r_{s}))\), the population stops evolving and the coverage of non-self space for mature detectors has reached the requirement. floor() is a function which returns a maximum integer less than or equal to the specified expression.

Adopting Iris data set as well, Fig. 4 shows the process of detectors’ generation. The navy blue filled circles represent self individuals in the space. Figure 4a shows variation ranges of two generations for a self, where the gray area is the variation range of first generation, and the light blue area is the variation range of second generation. Mature detectors of each generation are limited to a certain area. In Fig. 4b, the light blue area is coverage of first generation detectors, and the purple area is coverage of second generation. Detectors of the first level are distributed in the non-self space far away from selves, and have larger coverage; while detectors of the second level are distributed in the non-self space close to detectors of the first level and nearer to selves, and have smaller coverage.

Fig. 4
figure 4

The process of detectors’ generation

Full size image

3.4 Calculation method of coverage in non-self space

The non-self space coverage of detectors is equal to the ratio of the non-self space volume covered by detectors to the total volume of non-self space [12]. It is demonstrated in (10).

$$ P\mathrm{=}\frac{V_{covered}}{V_{nonself}}\mathrm{=}\frac{{\int}_{covered} {dx} }{{\int}_{nonself} {dx} } $$
(10)

Because of duplicated coverage between detectors, the equation above cannot be directly calculated. Method of probability estimation is introduced to calculate the non-self space coverage of detectors P in this paper. In the non-self space, the probability of sampling one time which is covered by detectors obeys the binomial probability b(1,P), and the probability of sampling ntimes obeys the binomial probability b(n,P). If the number of times continual sampling in the non-self space i is not larger than n 0, and \(\frac {m}{\sqrt {n_{0}P(1-P)}}-\sqrt {\frac {n_{0}P}{1-P} > Z_{\alpha }}\), the coverage of non-self space of detectors reaches P [12, 13]. Z α is a quantile of the standard normal distribution, and the value of a determines the precision. m is the number of times sampling in the non-self space covered by detectors in one round. n 0 is the minimal positive integer greater than both 5/ Pand 5/(1- P), and is a determined value.

Therefore, the algorithm needs to record i and m in the procedure of detectors’ generation. At first, i=0 and m=0. When i is less than n 0, it belongs to one round. After sampling randomly in the non-self space, the algorithm judges if the sample is covered by any detector in D. If it is not covered, produce a candidate detector using this sample’s position vector and put it in CD. If it is covered, calculate if \(\frac {m}{\sqrt {n_{0}P(1-P)} }-\sqrt {\frac {n_{0}P}{1-P} >Z_{\alpha }}\). If so, the non-self space coverage of detectors reaches P and stop sampling. If not, increase i. When i is equal to n 0, unite CD into D in order to alter the non-self space coverage, reset i =0m =0, and start a new round. After several rounds of sampling, the detector set D gradually increases, and the non-self space coverage of detectors becomes greater.

3.5 Performance analysis

Set that the total number of samples in the problem space is N A g , the size of self set is N S e l f , the size of training set is N s , and the size of detector set is N d . The matching probability between an arbitrary given detector and an antigen is \(P^{\prime }\), which is related with specific matching rules [9, 10]. P(A)is defined as the probability of event A happening.

Theorem 1

The probability of matching an un-described self for an arbitrary detector which passes self-tolerance is \(P_{d}\mathrm {=}{(1-P^{\prime })}^{N_{s}}\cdot (1-{(1-P^{\prime })}^{N_{Self}-N_{s}})\) . The probability of correct identification for an arbitrary non-self is \(P_{tp}\mathrm {=1-}{(1-P^{\prime })}^{N_{d}\cdot (1-P_{d})}\) , and the probability of being misidentified for an arbitrary non-self is \(P_{fn}\mathrm {=}{(1-P^{\prime })}^{N_{d}\cdot (1-P_{d})}\) . The probability of correct identification for an arbitrary self is \(P_{tn}\mathrm {=}{(1-P^{\prime })}^{N_{d}\cdot P_{d}}\) , and the probability of being misidentified for an arbitrary self is \(P_{fp}\mathrm {=1-}{(1-P^{\prime })}^{N_{d}\cdot P_{d}}\).

Proof

Known from the proposition, the given detector passes self-tolerance, which means that it does not match any self in the training set. Let event A be “the given detector does not match any self in the self set”, and event B be “the given detector at least match one self which is un-described”, then P d =P(A)P(B). In event A, the number of times that detectors match selves satisfies the binomial distribution \(X\sim b(N_{s}P^{\prime })\). So, \(P\left (A \right )=P\left (X=0 \right )={(1-P^{\prime })}^{N_{s}}\). In event B, the number of times which detectors match un-described selves satisfies the binomial distribution Y∼b(N S e l f −N s P). So,\(P\left (B \right )=1-P\left (Y=0 \right )={1-(1-P^{\prime })}^{{N_{Self}-N}_{s}}\). \(P_{d}=P\left (A \right )P\left (B \right )={(1-P^{\prime })}^{N_{s}}\cdot (1-{(1-P^{\prime })}^{N_{Self}-N_{s}}).\)

Let event E be “the given non-self at least matches one detector in the detector set”. In event E, the number of times which non-selves match detectors satisfies the binomial distribution \(Z\sim b(N_{d}\cdot \left (1-P_{d} \right )P^{\prime })\). Then,\(P_{tp}=P\left (E \right )=1-P\left (Z=0 \right )=1-{(1-P^{\prime })}^{N_{d}\cdot (1-P_{d})}\) and \(P_{fn}=1-P_{tp}={(1-P^{\prime })}^{N_{d}\cdot (1-P_{d})}\).

Let event F be “the given self does not match any detector in the detector set”. In event F, the number of times that selves match detectors satisfies the binomial distribution \(W\sim b(N_{d}\cdot P_{d}P^{\prime })\). Then, P t n =P \(\left (F \right )=P\left (W=0 \right )={(1-P^{\prime })}^{N_{d}\cdot P_{d}},\) \(P_{fp}=1-P_{tn}=1-{(1-P^{\prime })}^{N_{d}\cdot P_{d}}\). Proved.

In Theorem 1, \(P^{\prime }\) is the matching probability between any given detector and any antigen, which is the self-reaction rate of a candidate detector. For RNSA and V-Detector, \(P^{\prime } \) is the probability that a candidate detector falls in the self space. For IO-RNSA, \(P^{\prime }\) is the probability that a candidate detector falls in the intersection between its random range and the self space. To simplify the discussion, assume that there are no overlaps between self antigens.

Algorithms of RNSA and V-Detector randomly generate candidate detectors in the n-dimensional [0, 1] space, and the self-reaction rate of a candidate detector is the ratio of the self space to the entire shape space.

$$ {P^{\prime}}_{1}=\frac{V_{Self}}{V_{S}}=\frac{N_{s}{r_{s}^{n}}\pi ^{\frac{n}{2}}}{\tau (\frac{n}{2}+1)} $$
(11)

In IO-RNSA, when the evolution generation is t, candidate detectors which are mutated from an individual d are limited in the region between two hyper-spheres with the individual as the center and \(\sqrt n \) /exp(t-1) and \(\sqrt n \) /exp(t) as the radiuses. Self antigens may intersect with this region, or not. The self-reaction rate of a candidate detector is the ratio of the intersection space to the space between the two hyper-spheres. Suppose that the number of self antigens which satisfy \(\sqrt n /exp(t)-r_{s}<dist(d.y,ag.x)<\sqrt n /exp(t-1)+r_{s}\) is N z , N z < N s .

$$\begin{array}{@{}rcl@{}} {P^{\prime}}_{2}&=&\frac{V_{Cross}}{V_{t}-V_{t+1}}\le \frac{\frac{N_{z}{r_{s}^{n}}\pi^{\frac{n}{2}}}{\tau \left( \frac{n}{2}+1 \right)}}{\frac{\left( \frac{\sqrt n }{exp(t-1)} \right)^{n}\pi^{\frac{n}{2}}}{\tau \left( \frac{n}{2}+1 \right)}-\frac{\left( \frac{\sqrt n }{exp(t)} \right)^{n}\pi ^{\frac{n}{2}}}{\tau \left( \frac{n}{2}+1 \right)}}\\ &=&\frac{N_{z}{r_{s}^{n}}}{\left( \frac{\sqrt n }{\text{exp}(t-1)} \right)^{n}-\left( \frac{\sqrt n }{\text{exp}(t)} \right)^{n}} \end{array} $$
(12)

To compare the self-reaction rate of a detector for the three algorithms, set \(\zeta ={P^{\prime }}_{2}/{P^{\prime }}_{1}\).

$$ \zeta =\frac{P^{\prime}_{2}}{P^{\prime}_{1}}\le \frac{\frac{N_{z}}{\left( \frac{\sqrt n }{exp(t-1)} \right)^{n}-\left( \frac{\sqrt n }{exp(t)} \right)^{n}}}{\frac{N_{s}\pi^{\frac{n}{2}}}{\tau \left( \frac{n}{2}+1 \right)}}=\frac{N_{z}}{N_{s}}(\frac{1}{V_{t}-V_{t+1}}) $$
(13)

When the data dimension and the evolution generation are determined, v t and v t+1 can be calculated. If distributions of self set in the shape space are concentrated, N z is far less than N s . When the evolution generation is small, ζ < 1, it indicates that the self-reaction rate of IO-RNSA is less than that of RNSA and V-Detector. Known from [4], the number of candidate detectors required for generating N d mature detectors is \(N_{c}=N_{d}/{(1-P^{\prime })}^{N_{s}}\). Therefore, the smaller the self-reaction rate is, the smaller N c is, that is, the smaller the cost of detectors’ generation is.

Set the ratio of the training set size N s to the self set size N S e l f is f, \(P_{d}=\left (1-P^{\prime } \right )^{N_{s}}\cdot (1-{(1-P^{\prime })}^{N_{Self}-N_{s}})\). Figure 5 is the matlab simulations of Theorem 1. As can be seen, when N s is large enough, the effect of f and \(P^{\prime }\) on P d is small. For example, when N s =500, P d < 1 % and reaches satisfactory values. The false alarm rate F A R=P f p and the detection rate DR =P t p are related to the self-reaction rate of detectors \(P^{\prime }\), the number of mature detectors N d , the size of training set N s and the size of self set N S e l f . As can be seen, the effect of \(P^{\prime }\) on P f p and P t p is small. With the increase of N s and N d , P f p also increases. When N s is small, P t p increases with the increase of N d . When N s is large enough, P t p is small and approaching 0.

Fig. 5
figure 5

Simulations of Theorem 1

Full size image

□

3.6 Time complexity analysis

Theorem 2

The time complexity of IO-RNSA is O( \(\frac {N_{d}(N_{s}+c_{max}\cdot n+\left (1-P^{\prime } \right ){\cdot N}_{d})}{1-P^{\prime }})\) . Where, N d is the number of mature detectors, N s is the size of self set, c max is the maximum of clones, n is the data dimension, and \(P^{\prime }\) is the average self-reaction rate of detectors.

Proof

IO-RNSA produces mature detectors through the immune optimization and self-tolerance of generations of evolutional population. The main time costs are focused in step 2, step 4 and step 5.

In step 2, the algorithm performs operations of the immune selection, clonal proliferation and mutation. For a single individual, the number of calculation times for clone operation does not exceed c m a x , where c m a x is a determined value and can be negligible, the number of calculation times for mutation operation does not exceed c m a x ⋅n, and the time complexity is O(c m a x ⋅n).

In step 4, the algorithm determines whether a candidate detector falls in the self space, and the time complexity is O(N s ). If it is not covered by selves, perform step 5.

In step 5, the algorithm judges whether a candidate detector is covered by mature detectors, the number of calculation times does not exceed N d , and the time complexity is O(N d ).

Suppose that in generation t, the number of mature detectors is N d t , the number of candidate detectors is N t , the self-reaction rate of candidate detectors is P t , and then N t =N d t /(1- P t ). So, the time complexity of generating mature detectors in generation t is O(N t ⋅ (N s +c m a x ⋅n) + (1- P t ) ⋅N t ⋅N d ) = O(N t ⋅ (N s +c m a x ⋅n) +N d t ⋅N d ). Known from Section 3.3, the number of generations for evolution population is k=floor(1 + log( \(\sqrt n \) /rs)). So, the total time complexity of the algorithm is O(\(\sum _{t=1}^{k} {(N_{t}\cdot (N_{s}+c_{max}\cdot n)+N_{dt}\cdot N_{d})} )\).

Let the average self-reaction of candidate detectors is \(P^{\prime }\), the required number of candidate detectors is \(N=\sum _{t=1}^{k} N_{t} =N_{d}/(1-P^{\prime })\), and the number of mature detectors is \(N_{d}=\sum \nolimits _{t=1}^{k} N_{dt} \). So, the total time complexity of the algorithm is simplified to O(\(N\mathrm {\cdot (}N_{s}\mathrm {+}c_{max}\mathrm {\cdot }n\mathrm {)+}{N_{d}^{2}}\mathrm {))}\) = O(\(\frac {N_{d}(N_{s}+c_{max}\cdot n+\left (1-P^{\prime } \right ){\cdot N}_{d})}{1-P^{\prime }})\). Proved.

RNSA and V-Detector are classical immune algorithms for detectors’ generation, which are widely applied to pattern recognition, anomaly detection, immune optimization and other fields. Table 5 lists contrasts of time complexities of the two algorithms and IO-RNSA. From Table 5, the time complexity is exponential to N s in traditional negative selection algorithms. When the number of selves rises, the time cost will increase fast even to the point of unbearable. The time complexity is linear to the size of self set in IO-RNSA, which greatly lowers the impact on the time cost with the growth of self set. Therefore, IO-RNSA reduces the time complexity and enhances detectors’ generation efficiency. □

Table 5 Comparisons of time complexities
Full size table

4 Experiments

This section verifies the effectiveness of IO-RNSA by experiments. The algorithm chooses two types of data sets which are widely used in the study of real-valued negative selection algorithms, including 2-D synthetic data sets [13] and UCI data sets [25]. 2-D synthetic data sets are authoritative for performance testing of real-valued negative selection algorithms [12, 13, 20], which is provided by the research team of professor Dasgupta in the University of Memphis. UCI data sets are classical machine learning datasets, widely used in performance testing and generation efficiency analysis [12–20]. And the algorithm is compared with two classical real-valued negative selection algorithms RNSA and V-Detector.

The experiments used the number of mature detectors DN, detection rate DR, false alarm rate FAR and the time of detectors’ generation DT to measure the effectiveness of algorithms. Because RNSA adopts the default number of detectors as the termination condition, this paper modified RNSA to use the expected coverage of non-self space, in order to make valid comparisons of the three algorithms in the same experimental conditions.

4.1 2-D synthetic data sets

The data sets contain a plurality of different sub datasets. In general, Ring, Stripe and Pentagram sub datasets are selected to test the performance of detectors’ generation for IO-RNSA. Figure 6 shows distributions of the experimental data in 2-dimensional space.

Fig. 6
figure 6

Distributions of ring, triangle and stripe

Full size image

The size of self sets for three datasets is 1000. The training data are points randomly picked up from the self set, and the testing data are points randomly selected from the 2-dimensional space. Experiments were repeated 20 times and average values were taken. Experimental results are shown in Tables 6 and 7, where values in parentheses are variances. Table 6 lists the contrasts of detection rates and false alarm rates in three datasets for the algorithm, with the same expected coverage of 90 %, the same training set size N s =400 and different self radiuses. As can be seen, detection rate and false alarm rate are higher under small self size, while they are lower under large self size. Table 7 lists the contrasts of detection rates and false alarm rates in three datasets for the algorithm, with the same expected coverage of 90 %, the same self radius r s =0.05 and different training set sizes. With the increase of the training set size, the detection rate gradually raises and the false alarm rate gradually decreases.

Table 6 Effects of different self radius on the algorithm
Full size table
Table 7 Effects of different sizes of self training set on the algorithm
Full size table

4.2 UCI data sets

Three UCI datasets are selected for the experiments, namely Iris, Abalone and Breast Cancer Wisconsin Diagnostic. Experimental parameters are shown in Table 8, where individuals of self set, non-self set, self training set and testing set are chosen randomly. The experiments were repeated 20 times and average results were taken. In this section the algorithm compared with RNSA and V-Detector from these aspects including the number of detectors, the time cost, the detection rate and the false alarm rate.

Table 8 Experimental parameters
Full size table

4.2.1 Comparisons of number of detectors

Figure 7 shows the comparisons of the number of mature detectors on Iris dataset for RNSA, V-Detector and IO-RNSA. Seen from Fig. 7, with the rise of the expected coverage, the number of required detectors generated by the three algorithms increases correspondingly, but the efficiency of IO-RNSA is better than RNSA and V-Detector. On the Iris dataset, in order to achieve the expected coverage 99 %, RNSA needs 11568 mature detectors, V-Detector needs 1371, and IO-RNSA needs 464 which is significantly reduced and has decrease of 96.0 % and 66.2 %. IO-RNSA generates detectors from far to near, improves the coverage of detectors, and achieves fewer detectors covering as much non-self space as possible. So, under the same expected coverage, IO-RNSA requires fewer detectors.

Fig. 7
figure 7

Comparisons of the number of detectors for RNSA, V-Detector and IO-RNSA

Full size image

4.2.2 Comparisons of costs of detectors’ generation

Figure 8 shows the comparisons of costs of detectors’ generation on Breast Cancer Wisconsin Diagnostic dataset for RNSA, V-Detector and IO-RNSA. Seen from Fig. 8, with the increase of expected coverage, costs of detectors’ generation for RNSA and V-Detector sharp rise, and cost for IO-RNSA grows slowly. When the expected coverage is 99 %, the time cost of detectors’ generation for RNSA is 22560.4 seconds, the time cost for V-Detector is 155.8 seconds, and the time cost for IO-RNSA is 54.4 seconds which has decrease of 99.8 % and 65.1 %. By the analysis of Section 3.5, while the distribution of self set is concentrated, the reaction rate of detectors for IO-RNSA is smaller. So, the required number of candidate detectors for IO-RNSA is less, which greatly reduces the time cost of self tolerance.

Fig. 8
figure 8

Comparisons of costs of detectors’ generation for RNSA, V-Detector and IO-RNSA

Full size image

4.2.3 Comparisons of detection rate and false alarm rate

To further verify the effectiveness of IO-RNSA, detection rates and false alarm rates for RNSA, V-Detector and IO-RNSA are contrasted in this section. Abalone dataset is adopted, and experimental results are shown in Fig. 9. As can be seen, under the same expected coverage, IO-RNSA has significantly improved detection rate and lowered false alarm rate compared with RNSA and V-Detector.

Fig. 9
figure 9

Comparisons of detection rates and false alarm rates for RNSA, V-Detector and IO-RNSA

Full size image

5 Conclusions

High time complexities, large number of detectors and redundant coverage are major problems in traditional negative selection algorithms, which limit applications of immune algorithms. An immune optimization based real-valued negative selection algorithm IO-RNSA is proposed. Based on the distribution of self set in morphological space, the algorithm introduces the immune optimization mechanism, and produces candidate detectors hierarchically. In the process of detectors’ generation, the algorithm limits the random generation range of candidate detectors. It gives priority to producing detectors with large size which are distributed in low coverage areas, decreasing the number of mature detectors and redundancies Then it produces detectors with small size which are distributed in the area close to the self space, reducing the number of vulnerabilities. Theoretical analysis and experimental results show that IO-RNSA has better time efficiency and generation quality than classical negative selection algorithms, and is an effective artificial immune algorithm for generating detectors. The next step is to continue studying the immune mechanism of NSA, and propose more efficient negative selection algorithm for dynamic self set.