Information Technology Reference
In-Depth Information
(particularly the second version) find solutions with greater frequency, however
they spend more time moving in and out of the local optima from which the
BCA never escapes.
Culling the fittest member of the population (as with anti-elitism) may at first
seem counter-intuitive. However, if its fitness does not change for a certain given
period of time, the fittest member of the population is highly likely to be stuck
in one of the most dicult local optima. If it has a better fitness than it would
have in other nearby local optima, then its chances of escape are the slimmest of
the whole population. Thus it does make sense to cull the fittest individual, since
that individual has the lowest chance of improvement. This makes anti-elitism
a more intelligent (or targeted) culling, as opposed to the “cull everything that
doesn't move for a while” approach of the megamutation.
6
Conclusions
This work has benchmarked the B-Cell algorithm on four Diophantine equations.
We have implemented three modified versions of this algorithm, all of which
outperformed the original in terms of the probability of finding a global optimum
within a given number of iterations and demonstrated a reduction of the average
number of function evaluations needed for a global optimum to be found. The
most successful modification is anti-elitism, which culls the fittest member of the
population when its fitness has not changed within a certain specified number
of steps.
Further work remains to be done, including:
1. Attempt to solve the same Diophantine equations using genetic algorithms
and/or swarm optimization for comparison with these results.
2. Apply the anti-elitism modified version of the BCA to other optimization
problems to gain a more general determination of its advantages.
3. Design and test a variant of the anti-elitism algorithm utilizing memory cells,
for problems where the optimal fitness value is not known.
There is a substantial literature on so-called deceptive problems for GAs,
and on finding modifications that result in better performance of GAs upon
application to these sorts of problems (see [Dasgupta 1994], for instance). Thus
it would also be good to use deceptive problems as another set of benchmarks
for AIS algorithms. In fact, for a Diophantine equation, there can be points
with very small but non-zero values of
g
=
(i.e. local optima) that are far
from the actual solutions in search space, so in this sense Diophantine equations
correspond to a particular class of deceptive problems.
It is also worth mentioning here that, quite recently [Andrews 2006], Paul
Andrews showed us his implementation of the AIS algorithm opt-aiNet, another
optimization algorithm introduced in [de Castro and Timmis 2002a]. When opt-
aiNet was applied to the simplest of our benchmarks (problem #1), it appeared
to perform very badly. In every trial that we saw, most of the fittest members
of the population remained near one of the local optima (1
,
165) or (165
,
1);
|
f
|
