Information Technology Reference
In-Depth Information
We propose that Diophantine problems make good (and dicult) benchmarks
for testing AIS and other evolutionary algorithms. There are two main rea-
sons why we have decided to consider Diophantine equations: firstly, because
when they arose in some work on discrete dynamics [Hone 2006], the fourth au-
thor wanted a simple algorithm that could find solutions without performing
an exhaustive search; and secondly, some Diophantine problems are close to an
associated smooth optimization problem, and so can be considered as being inter-
mediate between smooth fitness landscapes and the hardest deceptive problems
[Dasgupta 1994].
Using a simple idea mentioned in [Hone and Kelsey 2004], it is easy to con-
vert any Diophantine equation into an optimization problem, namely that of
minimizing the function
g
(
x,y,z,...
)=
|
f
(
x,y,z,...
)
|
(or equivalently one can minimize
f
(
x,y,z,...
)
2
). Thus one wants to
obtain integers
x,y,z,...
which give the global minimum value zero for this
function. Why are these problems hard? Well, in general one has no idea whether
a given problem has any solutions at all. Furthermore, although these algebraic
functions are smooth when considered as functions of real variables, the function
landscape over the integers can be very spiky (since there can be many real
minima which are very close to integer-valued local minima).
In this paper, we consider four different test problems. The prototype example
will be Markoff's equation
over
Z
x
2
+
y
2
+
z
2
=3
xyz
(2)
which has important applications in number theory, where it arises in the theory
of quadratic forms and Diophantine approximation (see [Burger 2000] for an
overview). We have chosen this example because it is known how to generate
all the solutions in a cube of a given size, and furthermore Zagier has shown
[Zagier 1982] that the number of positive triples (
x, y, z
)with
0
<x
≤
y
≤
z
≤
T
that satisfy (2) grows like
C
log
2
(3
T
)
for a constant
C
0
.
1807. When applying the BCA to finding solutions of (2),
the latter asymptotic result should be helpful in measuring how the algorithm
scales with the problem size, but we will not address this issue here.
Ourfirsttestproblemistosolve a special case of (2), setting
z
= 433, which
reduces it to the 2D problem of finding positive integers that satisfy
≈
f
(
x, y
)=
x
2
+
y
2
+ 433
2
−
1299
xy
=0
.
(3)
Part of the function landscape for the above problem is plotted (logarithmically)
in figure 2. We use the full 3D Markoff equation (2) as our second test problem,
and a variant considered by Mordell [Mordell 1969], namely
