T Cell–Inspired Algorithms - Immunological Computation: Theory and Applications - page 76

Another lower bound for N R can be given in terms of matching probability P M , the
probability that a string and a detector that are randomly chosen match each other
according to the specifi c matching rule is

≥ −

N R (1 P f )/P M

It is shown that the holes are unavoidable. For example, in a partial matching
rule (rcb) , two self-strings together may eliminate all detectors that are necessary
to detect certain nonself strings. Given a string h and a matching rule M , if M
has constant matching probability P M , a self-set of size N S

= ′ = ⋅

| M (h) | P M N U ,

′

(h) is the set of the detectors matching string h , always su ces to induce

where M

holes.
Esponda et al. (2003) have shown that the holes can be constructed by “cross-
over closure” (CC) method under various matching criteria. Accordingly, for a
given set S of strings, and a fi xed 1

≤ ≤

l , applying the construction method
on S , only holes can be constructed that are “crossed” combinations of bits in S .
For example, assuming the string length, l

r

= =

4, rcb 2, and for three self-strings

= = =

1100, it is possible to construct holes h 1 = s 1 0110, s 2 1010, and s 3 1110 and

=

h 2 0100 as follows (Figure 4.4):

h ese examples have shown that the CC is a proper subset of the possible strings,
and holes can be generated by the genetic algorithm's crossover operator for a set of
bit strings, S . Also r -chunk matching rule can be viewed as a generalization of the
rcb matching rule, which is related with the concept of CC.

r − 1 r − 1

s 1 = 01 11 10 = {0110, 1110, 1010} = { s 1 , h 1 , s 2 }

s 2 = 10 01 10 = {1010, 0110, 1110} = { s 2 , s 1 , h 1 }

s 3 = 11 10 00 = {1100, 0100} = { s 3 , h 2 }

(a)

h 1 = 11 11 10 = {1110, 0010} = { h 1 , n 2 }

n 1 = 00 01 11 = {0011, 1111} = { n 1 , h 3 }

(b)

Figure 4.4 The fi gure illustrates the construction of holes from a given set of
self using CC. (a) Holes ( h 1 = 1110, h 2 = 0100) are constructed by s 1 = 0110,

s 2 1100. (b) An additional hole h 3 can be constructed by the

already found hole h 1

= 1010, and s 3 =

= 1110 and n 1 = 0011.