Biomedical Engineering Reference
In-Depth Information
average distances by the number of original taxa
they are formed from.
The distances found using UPGMA are then
used to form a cladogram representing how
distant the corresponding problem vectors are
in Euclidean space (Figure 4). The horizontal
distances on this figure are proportional to the
distance between problems or the averages of
problems that form the interior nodes. Problems
that are separated by a small horizontal distance
are similar to one another, while problems that
have a wider separation are dissimilar.
that have dissimilar characteristics to obtain an
effective test suite. While the taxonomy is by
no means complete, it already provides useful
information on problem relatedness. Referring
to Figures 4 and 5, it can be seen that many of the
problems that were used in the early development
of evolutionary algorithms, such as the DeJong
and Greiwangk functions, show a great deal of
similarity. This matches (Whitely et al., 1996).
While this does not completely discount their
value in a test suite, it does show that they do not
adequately represent the diverse set of problems
that can be examined by evolutionary computa-
tion techniques. Of the problems listed earlier,
the PORS and SAW problems represent the most
diverse groups of test problems. The instances of
these problem studied exhibit a broad diversity of
best and worst graphs, indicating that each form a
broad set of test problems and may be acceptable
for use in a test suite.
Nonlinear Projection
Nonlinear projection (Ashlock & Schonfeld, 2005)
is used to create a two-dimensional representation
of an n-dimensional data set. The Euclidean two-
space distances in the projection are as similar
as possible to the Euclidean n-space distances,
making the method similar in application to the
principle components method. Nonlinear projec-
tion is more general because all projections on
the data points in two dimensional real space are
searched rather than just the linear ones. Figure 5
shows a nonlinear projection of the 40 problems
in this study, resulting in a topology showing
similarity/dissimilarity.
OTHER APPLICATIONS OF GbEAs
Graph based evolutionary algorithms have been
applied successfully to several engineering and
biological problems. They have been applied to
stove designs (Bryden, Ashlock, McCorkle, & Ur-
ban, 2003), DNA error correcting codes (Ashlock
et al., 2002), a hydraulic mixing nozzle problem
(Xiao et al., 2003) and to a multi-objective problem
for finding antibiotic treatment regimens (Corns,
Hurd, Hoffman, & Bryden, 2006b) that benefit
swine growth and minimize antibiotic resistance
in potentially hazardous GI tract bacteria. Each
of these problems received the most benefit from
using a different graph.
The stove design problem is a uni-modal design
problem, and was best solved using a complete or
hypercube graph. Like most uni-modal problems,
the solution is at the top of a hill in design space,
and so, if the problem is non-deceptive, the faster
the algorithm converges the better. The DNA er-
ror correcting code problem is quite difficult and
EvALUATING TEST SUITES
Another application of GBEAs is in the devel-
opment of test suites. When a new method or
algorithm is developed, it is necessary to compare
it to existing methods. To do this comparison in
a meaningful way, a suitable test suite of prob-
lems needs to be solved with both the proposed
algorithm and the pre-existing methods. A good
test suite is composed of problems that among
other things are widely different from each
other (Whitely et al., 1996). Using the taxonomy
of problems constructed by comparing graph
performance, it is possible to select problems
Search WWH ::
Custom Search