Information Technology Reference
In-Depth Information
A Heuristic Detector Generation Algorithm for Negative
Selection Algorithm with Hamming Distance Partial
Matching Rule
Wenjian Luo, Zeming Zhang, and Xufa Wang
Department of Computer Science and Technology,
University of Science and Technology of China, Hefei 230027, China
wjluo@ustc.edu.cn, zmzhang@mail.ustc.edu.cn, xfwang@ustc.edu.cn
Abstract.
Negative selection algorithm is one of the most important algorithms
inspired by biological immune system. In this paper, a heuristic detector genera-
tion algorithm for negative selection algorithm is proposed when the partial
matching rule is Hamming distance. Experimental results show that this novel
detector generation algorithm has a better performance than traditional detector
generation algorithm.
1 Introduction
Artificial immune system (AIS) is an emergent bio-inspired research field after artifi-
cial neural network and evolutionary computation, which is inspired by biological
immune system [1-4]. Negative selection algorithm (NSA) has been proposed for
more than ten years, which is one of the most important algorithms and components
in artificial immune systems [5]. The detector generation algorithms for negative
selection algorithm have been studied for years, too [2, 3, 6, 7]. S. Forrest and her
colleagues proposed the linear time detector generation algorithm and the greedy
detector generation algorithm for negative selection algorithm with the r-continuous-
bits partial matching rule [7]. The negative selection algorithm with r-chunk rule is
proposed in [8], and the variable length detector for real-valued shape space is pro-
posed in [9-10]. T. Stibor and his colleagues analyzed the negative selection algo-
rithm theoretically in [11-12]. In addition, evolutionary negative selection algorithms
that combine negative selection model and evolutionary operators are also investi-
gated [13]. These are typical works in this field.
However, so far, when the partial matching rule is Hamming distance, there is no
efficient detector generation algorithm. As for the previous detector generation algo-
rithm that proposed about ten years ago, it runs in exponential time with respect to the
size of the self set [5, 7]. This paper concerns with an efficient detector generation
algorithm for negative selection algorithm that adopts Hamming distance as its partial
matching rule.
The rest of this paper is organized as follows. Section 2 briefly introduces the tradi-
tional detector generation algorithm and its time and space complexities. The new
heuristic detector generation algorithm is given in detail in section 3. In section 4,
