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

Table 4.1 Complexity of Different Detector Generation Algorithm

NS Algorithm Time Complexity Space Complexity

Exhaustive approach
(Forrest et al., 1994)

O ( m l ⋅ N S ) O ( l ⋅ N S )

Dynamic programming
(D'haeseleer et al., 1996)

O (( l − r + 1 ⋅ N S M r ) + O O (( l − r + 1) 2 ⋅ m r ))

(( l − r + 1) ⋅ m r ) + O ( l ⋅ N R )

Greedy algorithm
(D'haeseleer et al., 1996)

O (( l − r + 1) ⋅ N S M r ) + O O (( l − r + 1) 2 ⋅ m r ))

(( l − r + 1) ⋅ m r ⋅ N R )

Binary template
(Wierzchon, 2000)

O ( m r ⋅ N S ) + O (( l − r + 1) ⋅ O (( l − r + 1) ⋅ m r ) + O ( N R )

m r ⋅ N R )

NSMutation (Ayara et al.,
2002)

O ( m l ⋅ N S ) + O ( N R ⋅ m r ) + O ( l ( N S + N R ))

O ( N R )

Complexity of diff erent negative detector generating algorithms (exhaustive,
linear, greedy, binary template, and NSMutation) is summarized in Table 4.1
(taken from Ayara et al., 2002). h e symbols used are as follows: N S , number of
self-data; N R , number of mature detectors; N R0 , number of candidates; r , matching
threshold; m , alphabet size ( m

=

2 for binary representation); and l , string length.
As shown in Table 4.1, the time complexities of the exhaustive algorithm and
NSMutation are exponential with respect to the size of self. All the others have linear
time complexity. However, when the matching threshold r approaches length l , the
linear complexities may behave similarly to that of the exhaustive and NSMutation
algorithms due to the exponential value m r in their time complexities. NSMutation
has a higher space complexity than that of the exhaustive algorithm. h e linear,
greedy, and binary template algorithms all have higher space complexity, although
the binary template has the lowest among them. h e greedy algorithm with higher
alphabet, proposed by Singh (2002), has a time complexity of O(m r

⋅ − ⋅

N R ),
where N R is the prespecifi ed number of detectors, and m the size of alphabet. h e
space complexity is O(m r

(l r)

⋅ −

(l r) 2 ).

4.4.2 Immunological Holes

An important concept in detector generation is the notion of “immunological
hole.” An immunological “hole” corresponds to a set of nonself strings for which
no antibody exists that fails to match the self. h e concept of holes is applied to a
large class of potential matching rules. For example, in the r -contiguous-symbols
matching rule, if the self contains two strings ABC and A'BC' , where A, A', B, C ,
and C' are substrings, and B contains ( r

−

1) symbols, then there is no antibody
that will detect the nonself strings ABC' and A'BC . h us, counting the number
of holes under diff erent conditions, determining how big the holes are in practice
for a specifi c problem, and devising methods for detecting holes (e.g., by storing
antibodies with diff erent r values) are interesting problems.