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

Diophantine Benchmarks for the B-Cell
Algorithm

P. Bull 1 ,A.Knowles 2 , G. Tedesco 3 , and A. Hone 4

1 Department of Computer Science, University of Aberystwyth,
Aberystwyth SY23 3DB, U.K.
[e-mail]
2 Department of Electronics, University of York, York YO10 5DD, U.K.
[e-mail]
3 School of Computer Science, University of Nottingham,
Nottingham NG8 1BB, U.K.
[e-mail]
4 Institute of Mathematics, Statistics & Actuarial Science, University of Kent,
Canterbury CT2 7NF, U.K.
[e-mail]

Abstract. The B-cell algorithm (BCA) due to Kelsey and Timmis is a
function optimization algorithm inspired by the process of somatic muta-
tion of B cell clones in the natural immune system. So far, the BCA has
been shown to be perform well in comparison with genetic algorithms
when applied to various benchmark optimisation problems (finding the
optima of smooth real functions). More recently, the convergence of the
BCA has been shown by Clark, Hone and Timmis, using the theory
of Markov chains. However, at present the theory does not predict the
average number of iterations that are needed for the algorithm to con-
verge. In this paper we present some empirical convergence results for
the BCA, using a very different non-smooth set of benchmark problems.
We propose that certain Diophantine equations, which can be reformu-
lated as an optimization problem in integer programming, constitute a
much harder set of benchmarks for evolutionary algorithms. In the light
of our empirical results, we also suggest some modifications that can be
made to the BCA in order to improve its performance.

1 Introduction

Artificial immune systems (AIS) constitute a fairly new approach to biologically
inspired computing, that seek to exploit the mechanisms inherent in the natural
immune system for computational purposes. So far, the application of the AIS
approach to problems such as fault detection and network security has been
quite successful (see [de Castro and Timmis 2002b] for a variety of applications).
However, it is still not clear for which classes of problems it is appropriate to
use AIS techniques. Moreover, even in situations where AIS methods are known
to be successful, there is a dearth of theory to explain why they work.
Some of the first steps in the precise theoretical analysis of AIS were taken by
Villalobos-Arias et al. [Villalobos et al. 2004], who have shown the convergence