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

In another work, Stibor et al. (2004) developed a deterministic algorithm to
generate all possible detectors using the r -chunk matching rule. Such a detector
set is called a “perfect detector set,” D perfect , which contains a minimal number of
detectors that recognize all elements in U \ S , where U is the representation space
and S is the self-set (assuming all self-strings are included in S ). h e perfect detector
set does not solve the problem of the holes. Instead, it clarifi es the fact that holes are
impossible to correct even when the complete self-set and proper matching rule are
given. h e algorithm uses a hash table H data structure to insert, delete, and search
e ciently Boolean values, which are indexed with a composite key of r -chunk string
concatenated with detector position p . It is divided into three phases. h e total
space size is O (|

∑

| r ) . h e time complexity of the entire three phases is

∑ ∑ ∑ | r )

h e average number of generable detectors, depending on a self-set S , r -chunk
length r , and alphabet size

O ( (l − r) ⋅ | | r ) + O( | S | ⋅ (l − r + 1)) + O ( | | r ) = O ( |

∑

was estimated as

Slr

⋅

( 1 ) (

⋅

lr 1 )

1

1 ⋅

r

Σ
However, it is hardly possible to have perfect coverage as for any string representa-
tion, but a matching rule with variable threshold may possibly fi ll the holes better.

⋅ ( l r 1 )

r

⋅

( l r 1 ) S

4.5 Empirical Analysis: Binary Matching
Rules and Detector Coverage
h e original NS algorithm (described earlier) is very general and should work with
any representation space and matching rule. It is clear that the algorithmic e ciency
of generating good detectors varies with the t ype of representation space (continuous,
discrete, hybrid, etc.), the detector representation, and the process that determines
the matching (rule) ability of a detector.
Gonzalez et al. (2003a) analyzed and compared the eff ect of diff erent binary
matching rules (described in Chapter 3) in NS: r -contiguous matching, r -chunk
matching, Hamming distance matching, and its variation “Rogers and Tanimoto
(R&T) matching” to establish guidelines in selecting the matching rules for NSAs.
Experiments were carried out on a two-dimensional space (unit square) using
diff erent encoding schemes: binary and Gray encoding, and observed the eff ect of
matching rules on the area covered by individual detectors.
Experiments showed that the binary matching rules were not able to produce
a good coverage of the nonself space. h e r -chunk matching rule generated
satisfactory coverage of the nonself space (Figure 4.5b); however, the self-space was
covered by some lines resulting in erroneously detecting the self as nonself (false
alarms). h e Hamming-based matching rules generated an even more stringent