Biomedical Engineering Reference
In-Depth Information
The amount of diversity present in a population
initially is related to population size, but, even
in a large population, this initial diversity can
disappear rapidly. Graph based evolutionary
algorithms impose restrictions on mating and
placement within the evolving population (new
structures are placed in their parents' graph neigh-
borhood). This simulates natural obstacles (like
geography) or social obstacles (like the mating
dances of some bird species) to mating (Kimura
& Crow, 1963; Wright, 1986).
The GBEA technique differs from other AI
enhancements to search and optimization in
that they are a minor algorithmic modification
that can be added to any evolutionary algorithm
without requiring complex pre-calculation, costly
additional data structures, or extensive modifica-
tions of the algorithm being enhanced. Only the
adjacency matrix of a combinatorial graph need
be added, and it is used only to limit mate choice
- typically replacing a single call to a random-
ization algorithm. GBEAs are an exceptionally
simple enhancement, provided the correct graph
for a given problem is known.
When Evolutionary Algorithms (EAs) are
used as an optimization process, populations of
potential solutions are evolved to search a solution
space for an acceptable answer. This often avoids
problems with convergence to local optima that
are found in gradient search methods (Goldberg,
1989) and enables the search of discrete spaces.
These methods have provided novel and superior
solutions for a wide range of problems in physics,
engineering, biology, economics and many other
areas (Blaize, Knight, & Rasheed, 1998; Fabbri,
1997; Keane, 1994; Vavak, Jukes, & Fogarty,
1997). A key issue when applying EAs is how
to maintain sufficient diversity. When diversity
loss is too rapid, an ineffective search of the
solution space may occur, leading to premature
convergence. When diversity is preserved too
aggressively, the algorithm may converge slowly
or not at all. The right amount of diversity is
problem specific. A rule of thumb is that the
need to preserve diversity increases with problem
complexity and deceptiveness (Bryden, Ashlock,
Corns, & Willson, 2006).
There are several available methods for pre-
serving diversity, including EcoGAs (Davidor,
1993), island GAs (Whitley & Starkweather,
1990), niching (Goldberg, 1989), and taboo search
(Goldberg, 1989). EcoGAs and Island GAs are
essentially the same as a type of GBEA, albeit
using a less diverse class of graphs. EcoGAs use
a grid shaped graph, and Island GAs use clusters
of complete graphs connected through controlled
migration events. Niching and taboo search
require comparison of solutions in the evolving
population either to all other solutions in the
population or a taboo list, and so incur additional
computational costs. GBEAs have exceedingly
low computational overhead because of the fashion
in which they mimic passive methods of diversity
preservation found in nature.
Carefully choosing the connectivity of the
combinatorial graphs used permits the level of
diversity preservation to be increased or decreased
(Bryden et al., 2006). Greater diversity causes
more candidate solutions to evolve within the
population. They may compete or cooperate (by
juxtaposing compatible sub-structures) as they
explore the search space. This can also result
in finding multiple solutions for multi-modal
problems.
An unexpected and welcome outcome of re-
search on GBEAs has been that, by examining
the effects that different graph structures have on
the time to solution for different problems, it was
observed that similar problems grouped together.
This makes it possible to use the performance on
different graphs as a taxonomic character, giving
a similarity measure with which to compare prob-
lems. These graph-based characters of problems
make it possible to generate and evaluate test
suites that ensure a thorough evaluation of new
techniques or algorithms. In addition, having
a database of problems that documents the best
graph for each problem allows the user to make
Search WWH ::
Custom Search