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

4.6.5 A Statistical Method: V-Detector Algorithm

Ji and Dasgupta (2004a, 2004b) proposed a new RNS algorithm called “V-detector,”
which has two main features as follows:

Variable-sized detector to achieve large coverage of nonself space with limited
number of detectors
Estimation of the coverage using the generation process itself

h is algorithm uses the conventional generate-and-test strategy of NS in a real-
valued representation of data space on [0, 1] n . Detector generation is performed by
randomly generating a set of uniformly distributed random samples on I n as possible
centers of the detectors. If a point lies inside the self-set or it has already been covered
by existing detectors, it is simply discarded. Also, the algorithm keeps track of the
failed attempts to generate new detectors by such random points, which is further
used to estimate the current coverage. If a new point either lies inside nonself or has
not been covered by any detector, then it will give origin to a new detector given
as a hypersphere whose radius is the maximum radius that will not make it match
any self-sample. If the number of consecutive failed attempts that fall on a covered
point reaches a limit m , the generation stage terminates with enough confi dence
that the coverage is su cient. However, the value of m is not prespecifi ed; it is
rather decided by the estimated coverage as

1

m

1

where α is the current estimated coverage. h e preceding equation may be explained
as follows. If there is one uncovered point in a sample of size m

′

, an estimate of the

proportion of uncovered volume is 1/ m ′ , and the estimate of the coverage is then

given by

1

m

1

Actually, if there is no uncovered point in a sample of size m , there is a bet-

ter than average chance that the actual coverage is larger than α

′

′

. Because m is
decided by the earlier mentioned equation, after obtaining m consecutive points
that are all covered, we can estimate that the actual coverage is very likely to be
at least α .
An RNS with a constant size detector was used to compare it to the V-detector
NS approach. h e V-detector algorithm works well as long as the number of detec-
tors is not taken into account. Overlap is not an important issue in the detector
generation process as long as the new detector contributes to the coverage.