A Heuristic Detector Generation Algorithm for Negative Selection Algorithm with Hamming Distance Partial Matching Rule - Artificial Immune Systems - page 233

+ determinate bits. The
values of the new k determinate bits are set by flipping the corresponding bits of

Obviously, template

T ,

has l − c − k “blanks” and c k

s

l k c

⎛ ⎞

⎜ ⎜
⎝

⎟ ⎟
⎠

s = y y y L y . Therefore, the possible number of

T , is

.

s 1 2 3 l

3.2 Heuristic Detector Generation Algorithm

Fig. 2 shows the heuristic detector generation algorithm in detail. The valid detectors
generated are stored in R .

(1) Denote all elements in the self set as s , 2 s , L , s .

1 N

S

(2) Initialize = R .

(3) Select a self string

Φ

s ( ≤ r ≤ N ) randomly. Randomly generate a candidate

r s

lc ) of s , and the candidate detec-
tor template is denoted by d . Therefore, d has

detector template with order c ( = − r + 1

r − 1 “blanks”. Let

m = r − 1 .

(4) Initialize i = 0 .

(5) Set i = i + 1 ,

a) If i = r , go to (5).

b) If . If the size of R reaches the expected number of

the mature detectors or other end conditions are satisfied, the algorithm
terminates. Otherwise, go to (3).

i > N , R ← R ∪ { d }

S

c) If i ≤ N ,

S

i. Calculate the number of bits that both d and the self string s are

identical in the corresponding positions where the bits of d are
determinate, and denoted by k . That is to say, no “blank” bit is
considered when calculating k .

ii. If k ≥ r , delete d and go to (3).

iii. = rk , all “blank” bits of d are replaced by the flipped

value of the corresponding bits of s , and set

If − 1

m = 0 . Go to (5).

iv. mk , the candidate detector template d

and it's “blank” m bits remain unchanged, go to (5).

If k < r − 1 and + ≤ r − 1

v.

mk , randomly generate one candidate
detector template t with order

If k < r − 1 and + > r − 1

l − ( r − 1 − k ) of both d and s .

, go to (5).

And set d = t , m = r − 1 − k

Fig. 2. The heuristic detector generation algorithm

The detectors generated by the algorithm in Fig. 2 consist of {0, 1, *}. And the “*”
can be matched with both “0” and “1”. Assume a detector d has b “blanks”. Any ran-
dom string is matched by this detector with a probability of