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

where the approximation is valid for large n and small P(l, k) , the probability that
two random strings match. For an “ideal” detector set, the coverage is fi xed. For
a given number of detectors that are not “ideal,” detectors are chosen so that a
maximum number of diff erent templates are used. For implementation of the algo-
rithm, a binary tree is used to represent the connection between the self-templates.
Following the tree representation, all possible “self-strings” are reconstructed and
those that are not self-strings can be found. h ese nonself, or undetectable, strings
can come from two sources: strings that can be built from templates in T S , or self-
templates and those that have nonself templates (templates in T N ).

4.3.4.3 DynamiCS

A variation of NSA introduces “dynamic clonal selection algorithm (DynamiCS)”
to deal with a nonself detection problem in a continuously changing environment
(Kim and Bentley, 2002). In particular, DynamiCS is based on Hofmeyr's idea
(Hofmeyr and Forrest, 2000) of dynamics of three diff erent populations: imma-
ture, mature, and “memory detector” populations. Initial “immature detectors”
are generated with random “genotypes.” Using an NS, new immature detectors are
added to keep the total number after a predefi ned number of generations (“toleriza-
tion period” T). If a detector is within its predefi ned “life span” L and the match
counts are larger than a predefi ned “activation threshold” A, it becomes a memory
detector. “Mature detectors” are used on all given antigens. However, a human
security o cer's confi rmation (costimulation) is necessary to make the detector a
memory detector, which makes the approach dependent on human interaction.
An enhanced NS algorithm (Hofmeyr, 1999) with multiple secondary
representations was introduced to reduce the number of trials needed to generate
detectors on the structured self as much as three orders of magnitude less. h e sug-
gested secondary representations included pure permutation, imperfect hashing,
and substring hashing.

4.3.4.4 Schemata-Based Detection Rules

Hang and Dai (2004) introduced a new idea in detector generation by converting
the data space into schemata space. Such a conversion compresses the data space.
h e problem space is n -dimensional vector space including categorical and numeric
features. For real-valued features, a schema r is defi ned as the conjunction of the
intervals as in the rules. Common schemata are those that are common in a group
of rules. A number of common schemata are fi rst evolved through a coevolutionary
genetic algorithm (GA) in self-data space. h e population used in the coevolution-
ary GA consists of a number of non-inter-breeding subpopulations. Species are
initialized randomly, and new species are added into the population until the total
number of species reaches a certain value. h en all the species are decoded into
common schemata. Detectors are then constructed in the complementary space