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

equally spaced sample points in the range [-2, 2]
of the error function E(x) = (f”(x)-5f'(x)+6f(x)) 2 .
This is essentially the squared deviation from
agreement with the differential equation. This
function is to be minimized, and the algorithm
continues until 1,000,000 mating events have
taken place (this did not happen in practice) or
until the fitness function summed over all 100
sample points drops below 0.001. The initial
population is composed of randomly generated
trees. Crossover was performed by the usual
subtree exchange (Koza, 1992). If this produced
a tree with more than 22 nodes, then a subtree of
the root node iteratively replaced the root node
until the tree had n nodes or less. This operation
is called chopping . Mutation was performed by
replacing a subtree picked uniformly at random
with a new random subtree of the same size for
each new tree produced. A constant mutation was
also applied to each new parse tree. For a tree that
contains one or more constants in either a terminal
or as part of a unary scaling operation, one of the
constants is selected with a uniform distribution
and a number uniformly distributed in the region
[-0.1, 0.1] is added to it. These constants are initial-
ized in the range of [-1, 1], but may go outside this
range by the constant mutation operator. Local
elite fitness proportional mating was used for the
differential equation solution problem.
The PORS problem is a maximization problem
in genetic programming with a small operation
set and a calculator style memory (Ashlock &
Lathrop, 1998). The goal is to find a parse tree
with n nodes that generates the largest possible
integer value when it is evaluated. There are two
operations: integer addition and a store function
that places the current value in an external memory
location. There are also two terminals: the integer
one and a terminal that recalls the value from the
external memory. There are four distinct build-
ing blocks using these nodes: one that evaluates
to an integer value of 2, one that evaluates to an
integer value of 3, one that doubles the input value,

and one that triples the input value. By properly
combining these building blocks, the maximum
value for a given number of nodes can be found.
The difficulty of the PORS problem varies by
which building blocks are necessary and is tied
to the congruence class (mod 3) of the number
of nodes permitted. The cases for n = 15, n = 16
and n=17 nodes, respectively representatives of
the hardest, easiest and intermediate difficulty
classes, were used in this study. The n=15 case
has a single solution comprised of smaller build-
ing blocks, giving it a deceptive nature, while
the PORS 16 problem has several solutions that
are relatively easy to find. The initial popula-
tion was composed of randomly generated trees
with exactly n nodes. A successful individual
was defined to be a tree that produces the largest
possible number (these numbers are computed
in (Ashlock & Lathrop, 1998)). Crossover was
performed by the usual subtree exchange (Koza,
1992). If this produced a tree with more than n
nodes, then a chopping operation was performed.
Mutation was performed by replacing a subtree
picked uniformly at random with a new random
subtree of the same size.
The third genetic programming problem
examined was the odd-parity problem (Banzhaf
et al., 1998). The objective of the problem is to
find the truth value (boolean) of the proposition
“an odd number of the input variables are true.”
Two representations were used to investigate this
problem: simple parse trees and function stacks.
The simple parse tree representation used no
ADFs, logical operations, and the same variation
operators as the PORS problem. The function
stack representation is derived from Cartesian
Genetic Programming (Miller & Thomson, 2000),
where the parse tree is replaced with a directed
acyclic graph that has its vertices stored in a linear
chromosome. For both representations, the fitness
is the number of cases of the odd-parity problem
computed correctly.