Diophantine Benchmarks for the B-Cell Algorithm - Artificial Immune Systems - page 270

1. Initialisation : create an initial random population of
individuals P ;
2. Main loop : ∀v ∈ P :
(a) A nity Evaluation :evaluate g ( v );
(b) Clonal Selection and Expansion :
i. Clone each B-cell :foreach v P , produce a pool of clones C ( v );

ii. Contiguous mutation :Foreach v ∈ P , apply the contiguous somatic hy-
permutation operator to every c ∈ C ;
iii. A nity Evaluation : evaluate each clone by applying
g ; if a clone is fitter than its parent B-cell v ,thenreplace v by c ;
3. Cycle : repeat from step 2 until some stopping criterion
is met.

∈

Fig. 1. Outline of the B-Cell Algorithm

in terms of the bias inherent in the mutation operator, which overall tends to
mutate the least significant bits with higher probability than the most significant
ones. Rather than selecting multiple random sites for mutation, a random site
(or hotspot ) is chosen within the vector, along with a random length; the vector
is then subjected to mutation from the hotspot until the length of the contiguous
region has been reached.

3 Diophantine Equations as Optimization Problems

A Diophantine equation is an algebraic equation

f ( x,y,z,... )=0

which must be solved over the integers . Diophantine problems have a long and

distinguished pedigree in number theory [Mordell 1969]. As the recent proof by
Wiles and Taylor of Fermat's last theorem shows, they also constitute some of
the hardest problems in modern mathematics. While it is well known that there
are infinitely many Pythagorean triples of integers ( x, y, z ) satisfying

Z

x 2 + y 2 = z 2 ,

Fermat's assertion that

x N + y N = z N , N ≥ 3

has no integer solutions turned out to be an incredibly dicult thing to prove.
Hilbert's tenth problem is the general problem of deciding when a Diophantine
equation has integer solutions, and Matiyasevich proved the undecidability of
this problem. Moreover, Matiyasevich showed that any statement in a formal
system can be encoded as an equivalent Diophantine problem (see chapter 3 in
[Manin and Panchishkin 2005] for instance).