Biomedical Engineering Reference
In-Depth Information
bACkGROUND TECHNIQUES
are selected with a probability proportional to
their fitness, related to the purpose of the study.
Once the chromosomes have been selected, a
crossover procedure is used to partially exchange
genetic information between two parent chro-
mosomes. Chromosomes from the parent pool
are randomly paired up and are tested to deter-
mine if an exchange will take place based on a
crossover probability. If an exchange is to take
place, a crossover site is selected at random for
the two chromosomes and the genetic material
(genes) after the crossover site is then exchanged
between the two parent strings. In so doing, two
child chromosomes are produced, which form the
members of a new population. If an exchange is
not to take place (i.e. the crossover probability is
less than the crossover probability parameter),
then the two parents enter the new population
unchanged. Mutation has the purpose of keeping
the population diverse and preventing the GA from
prematurely converging onto a local minimum.
Each chromosome is tested on a probability basis
to determine if it will be mutated. In the most
commonly used form of mutation, the probability
that each bit in the chromosome will be mutated
is determined by the mutation probability pa-
rameter. If a bit is to be mutated, then this occurs
by flipping its value (i.e. a '0' will become a '1'
and vice versa). The application of the mutation
operator marks the end of one GA cycle. The GA
is usually allowed to run for a specified number
of generations, or until some stopping criterion
is met, such as convergence of the population to
a single solution.
A GA differs from many other optimisation
methods by virtue of the fact that a population,
or collection of possible solutions, is used rather
than a single solution. It does not need knowledge
of the problem domain, but it requires a fitness
function to evaluate the fitness of a solution. The
GA techniques have a solid theoretical founda-
tion, which is based on the Schema Theorem. A
comprehensive description of GAs can be found
in Goldberg (1989) and Holland (1992).
Before describing the specific details of GNMM,
some relevant Intelligence Systems concepts are
reviewed below.
Genetic Algorithms (GAs)
GAs are a powerful optimisation technique,
based upon the underlying principles of natural
evolution and selection (Holland, 1992). GAs are
well suited to the task of selecting an appropriate
combination of inputs to a model as they have
the ability to search through large numbers of
combinations, where interdependencies between
variables may exist (Michalewicz, 1996; Reeves
& Rowe, 2003; Rothlauf, 2006).
The main procedures in the GA optimisation
process are shown in Figure 1. The basic idea
is to maintain a population of chromosomes,
representing candidate solutions to the concrete
problem being solved. The possible solutions are
generally coded as binary strings and these strings
are equivalent to biological chromosomes. Other
non-binary codings have proven to be useful in
some applications (Gardner, Boilot, & Hines,
2005; Srinivasa, Venugopal, & Patnaik, 2007).
Each bit of the binary string (chromosome) is
referred to as a gene. A GA starts off with a
population of randomly generated chromosomes
and advances towards better chromosomes by ap-
plying genetic operators that are based on genetic
processes occurring in nature (i.e., selection,
crossover and mutation) (Haupt & Haupt, 2004;
Mitchell, 1996).
The search is initialized with a random
population of chromosomes, each representing
a possible solution. Next, each chromosome in
the population is decoded into a solution and its
fitness is evaluated using an objective function.
During successive iterations, or
generations
, the
adaptation or associated fitness of chromosomes
in the population is quantified by means of fitness
functions. Chromosomes for the new population
Search WWH ::
Custom Search