Information Technology Reference
In-Depth Information
x
2
+
y
2
+
z
2
+2
xyz
−
5=0
,
(4)
as the third test problem.
14
12
10
1
200
2
400
3
600
4
800
1000
5
Fig. 2.
Contour plot of the function ln
|f
(
x, y
)
|
,with
f
as in equation (3), for positive
integer values of
x
≤
1000 along the sections
y
=1
,
2
,
3
,
4
,
5
Our fourth, and hardest, problem is a Diophantine equation related to se-
quences of points on an elliptic curve (and associated with some integer sequences
suggested by Michael Somos [Gale 1991]), which is given by
z
2
+(9
x
2
37
y
)
xz
+9
y
2
(
y
+2
x
2
)=0
.
−
(5)
For this last problem, we do not explicitly know how to generate all the solutions,
although an obvious one is (
x, y, z
)=(1
,
1
,
1). We explain how we applied the
BCA to these four problems in the next section, and how the diculty of the
problems led us to suggest various ways of making modifications to the algorithm.
4
Experimental Setup
For the first and second problems we applied the BCA to search between 0 and
1023 for each variable, in 2D and 3D respectively. For the more dicult three-
dimensional problems for which solutions exist with negative integer values, a full
16 bit integer was used for each variable, giving a search space of size 65536
3
≈
10
14
. On the simplest 2D problem the algorithm performed reasonably well,
finding a solution within 100 iterations more than 95% of the time. However in
the other cases, the algorithm would often get stuck at a local optimum with a
small value of the objective function
g
, and would make very slow progress until
much of the search space had been searched. For example, for the first problem for
equation (3) in 2D, the points (
x, y
)=(1
,
165) and (165
,
1) are two local minima
3
×
