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

the edges), and edges are created between those
within a specified distance from one another. This
distance is chosen to give an average degree of
about 6. After generation, the graph is checked
to see if it is connected. Graphs that are not
connected are rejected. Hence, the graphs used
were chosen at random from connected random
toroidal graphs. These graphs are denoted R(r, i),
where r is the radius for edge creation, and i = 1,
2, 3 is the instance of the graph in this study.

the parent if it is at least as it. Figure 2 gives a
flowchart representation of the algorithm.
Graph connectivity is roughly inversely re-
lated to the graph's ability to preserve diversity.
Highly connected graphs provide the highest rate
of information transfer and thus lower diversity
preservation. The complete graph is the most
highly connected graph, which permits a GBEA
to simulate a standard evolutionary algorithm.
Highly connected graphs have superior time to
convergence when used for simple uni-modal
problems, such as the one-max problem (Bryden
et al., 2006). As the number of optima and decep-
tiveness of the problem increases, graphs which
are more sparsely connected have superior mean
acceptable solution times. Sparse graphs have
been found to perform well in deceptive genetic
programming problems, e.g. the PORS problem
(Bryden et al., 2006), and the problem of locat-
ing DNA error correcting codes (Ashlock, Guo,
& Qiu, 2002). To date, use of the correct graph
has resulted in a decrease in time to convergence
to an optimal solution by as much as 63-fold for
the most difficult problem tried. The impact
varies substantially with the problem, and about
half of all problems tested show a benefit from
using a GBEA.
Closely related to the graph connectivity is
population size, since both can impact population
diversity. For a given type of graph, diameter
increases with population size; graphs of low
degree exhibit the sharpest increase. When the
results for all problems were plotted, it was found
that, for all but the most trivial problems, there
was an optimal population size for each type of
graph, such as in the PORS 16 problem (Figure
3). Using a sparse graph typically preformed
well for small population sizes as the initial
amount of diversity doesn't have to be as large
when a diversity preserving graph is used. By
using a diversity preserving graph on problems
with expensive fitness evaluations, the time to
convergence can be greatly reduced. In addi-
tion, when the proper graph is combined with

A graph used to constrain mating in a popula-
tion is called the population structure of a GBEA.
It specifies the geography on which a population
lives, permitting mating only between neighbors.
The goal is to find graphs that preserve diversity
without hindering progress. To date, twenty-six
graphs have been tested to investigate how the
different underlying structures affect information
spread (Corns, Bryden, & Ashlock, 2003; Corns,
Bryden, & Ashlock, 2005a; Corns, Bryden, &
Ashlock, 2005b).

GRAPH bASED EvOLUTIONARy
ALGORITHMS

This section carefully defines graph based evolu-
tionary algorithms. GBEAs are a simple exten-
sion of evolutionary algorithms that distribute the
population members on a combinatorial graph,
placing one solution on each vertex of the graph.
It is only possible for population members to mate
with or, after mating has generated new solutions,
replace graph neighbors. For the local mating rules
used here, a steady state evolutionary algorithm
is used, in which evolution occurs one mating
event at a time (Reynolds, 1992; Syswerda, 1991;
Whitley, 1989). A mating event is performed by
randomly selecting a population member (the
parent ), and then using fitness proportional selec-
tion to determine a mate (the co - parent ) from the
parent's neighbors. A single child is generated
and compared to the parent. The child replaces