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

At the beginning, R (the detectors set) is empty, and C R and C R are ini-

=

2 ( l − r + 1 − i ) and C

R,i [ s ] =

2 ( i − 1) ,

tialized to their maximum values: C R,i [ s ]

which correspond to D R,i [ s ] = 2 ( l − r ) .

When a new detector is generated, the algorithm scans D R looking for its largest
entry. If two templates have the same largest entry, then one of the templates is
picked at random. h en, the algorithm traverses D R to the left and to the right
starting at such a template, each time either a “0” or a “1” is appended to the
starting template, depending on which one corresponds to the template with the
highest number of yet unmatched strings by R . h en, arrays C R and C R are updated

to refl ect that a new detector has been added to R . h is is done incrementally by
setting those entries in C R and C R that correspond to templates that match the

detector to zero, and then recalculating the appropriate values for such entries.
h e process of choosing a detector and updating C R and C R is repeated until all

valid detector templates have zero entries in D R . h us, at the end, for any template
that is not in S , there are no more strings that have not been matched by a detector
yet. In other words, the generated detectors cover all the unmatched strings that
can possibly be covered as the algorithm keeps track of the number of nonself
strings that have not been matched by any detector.
However, tuning a detector generation algorithm requires determining what
is considered an optimal performance. If the goal is to minimize the number of
detectors required for a fi xed reliability level and the self-set, then the string length
( l ), m (the alphabet size), r (the matching threshold), and the matching rule for
generating detectors need to be carefully chosen. In brief, the complexity of the
detector generation process depends on the matching rule.
Singh (2002) extended the greedy algorithm to bigger alphabets. h is is
relevant in cases where the semantics of the information may get lost in binary
representation. A lower number of false-positives were reported compared to results
using binary representation.

4.3.4 Other Variants in Detector Generation
4.3.4.1 NSMutation Algorithm

NSMutation (Ayara et al., 2002) is a modifi ed version of exhaustive algorithm,
which introduces somatic hypermutation mechanism to improve performance.
Particularly, instead of elimination of the candidate detector that matches the self-
data, guided mutation is performed to attempt to make them valid detectors. h e
probability of mutation is considered as directly proportional to a nity between
the candidate and self-sample. h e diff erence in complexity comes from the time to
mutate the matching region of length r of detector candidate. Mutation is limited
to the region of length r , the upper bound of mutating is m r . Matching threshold
( r ), detector lifetime rate, and mutation probability are major control parameters