Information Technology Reference
In-Depth Information
2
The B-Cell Algorithm
An important aspect of the adaptive immune response is the huge diversity
in lymphocyte populations, which allows essentially any possible antigen to be
recognized. For B cells, this diversity is generated in two quite different ways.
(See section D of [Lydyard et al. 2004] for an overview.) Firstly, at the germline
level (in the absence of antigen), diversity arises due to random selection and
recombination of the genes that code for immunoglobulins. Secondly, further
diversity is generated by somatic mutation, when (in the presence of antigen) B
cells undergo costimulation with T-helper cells and a population of B cell clones
is produced. The somatic mutation means that the clones potentially have a
higher anity for the antigen than their parent cells.
The B-cell algorithm (BCA) is loosely based on this process of somatic mu-
tation in B cell clones. There is some evidence in the immunological literature
[Lamlum 1999] that mutation occurs in
clusters
of regions within cells. The novel
feature of the BCA is the use of an analogous notion applied to bit strings: muta-
tion is applied to contiguous regions along the string. This mutation mechanism
is referred to as the
contiguous somatic hypermutation
operator (described in
more detail below).
The BCA takes bit strings (vectors) of length
L
, which represent a point in
the search space; this could correspond to bit-encoded double-precision num-
bers, integers, or any other way of encoding the coordinates in search space.
These vectors are considered to be the B cells within the system (although the
analogy with biology is very loose: the B cells are identified with their genetic
code, and with the associated immunoglobulins). Each B cells is associated with
a vector
v
P
,where
P
is the population, and the objective function
g
can
be evaluated at
v
to give
g
(
v
), which corresponds to the fitness of the cell. An
ecient population size for many functions can be small in contrast with ge-
netic algorithms; a population size of five would be typical. In fact, as noted
in [Clark et al. 2005], in the original specification of the algorithm the separate
members of the population evolve independently, so there is no difference be-
tween running the algorithm
N
times with a population of size one, or once
(i.e. in parallel) with population size
N
. Unlike standard GAs, the BCA does
not use crossover. However, in practice Kelsey has used a heuristic for culling
the weakest member of the population in each generation [Kelsey 2006], which
effectively introduces an interaction between the different members. (Whether
this is the right heuristic to use will be discussed later.)
Within every iteration (or generation) of the algorithm, each B-cell
v
is cloned
to produce a
clonal pool
,
C
(
v
). For
each
B cell within the population, all the
adaptation takes place within
C
(
v
).Thesizeof
C
is typically the same size as
the population
P
(but this does not have to be the case). Each B-cell
v
∈
∈
C
(
v
)
is subjected to the contiguous somatic hypermutation operator. The BCA is
outlined in figure 1.
An unusual feature of the BCA is the form of the mutation operator. This
operates by subjecting
contiguous
regions of the vector to mutation. In essence
a more focused search is undertaken: in [Clark et al. 2005] this is understood
