Graph Based Evolutionary Algorithms - Advancing Artificial Intelligence Through Biological Process Applications - page 320

of the grid and using the chromosome to dictate
moves. The chromosome specifies a walk , with
moves leaving the grid ignored. The fitness of a
chromosome is the number of cells visited at least
once. Since there are a number of moves equal
to the number of cells minus the first, and since
revisiting a cell earns no additional fitness, the
optimal solution does not revisit any squares and
is thus self-avoiding . Every problem has a known
best fitness equal to the number of cells, making
detection of optimal solutions simpler than previ-
ous string problems of variable difficulty such as
n-k landscapes (Kauffman & Levin, 1987). For
the instances of SAW problems in our studies,
two-point crossover and single character mutation
(which replaces a character selected at random
with a random character) are used.
Two ordered gene problems are used in this
study; sorting a list into order and maximizing the
period of a permutation (Ashlock, 2006). Both
crossover and mutation operators are used in the
problem, with the crossover operator retaining
the entries after the crossover point, but changing
their order of occurrence to match the co-parent's.
The mutation operator changes two entries in the
permutation chosen uniformly at random. For
both problems, the crossover and mutation rates
are set at 100%. The list ordering problem was
run for lists of length 8, 9 and 10, and the period
maximization problem used lengths of 30, 32,
34 and 36.

a kind of six dimensional ziggurat. Function F4
is a fourth-order paraboloid in thirty dimensions,
with distinct diameters in different numbers of
dimensions, made more complex by adding Gauss-
ian noise. Function F5 is the “Shekel's Foxholes”
function with many narrow local optima placed
on a grid. A detailed description can be found in
(Bryden et al., 2006). The Griewangk function
is a sum of quadratic bowls with cosine terms to
add noise. The functions are translated to be a
positive function, and one is described in each
dimension. The cosine term inserts many local
optima, but as the dimension of the function
increases it becomes smoother and hence less
challenging (Whitely et al., 1996). For this reason
we include this function in five cases of relatively
low dimension, N = 3, 4 . . . 7.

Genetic Programming Problems

Three genetic programming problems were stud-
ied: a differential equation solution problem, the
plus-one-recall-store (PORS) problem (Ashlock,
2006), and the parity problem (Koza, 1992). In
addition to solving a differential equation within
a GBEA, we also modify the usual GP technique
by extracting the derivatives needed to compute
fitness symbolically. This method is described
more completely in (Kirstukas, Bryden, & Ash-
lock, 2004).
We solve the differential equation:

Real variable Problems

y” - 5y' + 6y = 0 (1)

The real-variable problems examined are the
five functions proposed by DeJong (denoted F1
- F5) as well as the Griewangk function (Whitley,
Mathias, Rana, & Dzubera, 1996) in 3-7 dimen-
sions. The function F1 is a three dimensional
bowl. DeJong's function F2 is a fourth degree
bivariate polynomial surface featuring a broad
sub-optimal peak. Function F3 is a sum of integer
parts of five independent variables, creating a
function that is flat where it is not discontinuous,

which is a simple homogeneous equation with
the two dimensional solution space,

y = Ae 2t + Be 3t (2)

for any constants A, B. The parse tree language
used has operations and terminals given in Table 2.
Trees were initialized to have six total operations
and terminals. Fitness for a parse tree coding a
function f(x) was computed as the sum over 100