Problems with the Genetic Algorithm
Problems with the Genetic Algorithm
The genetic algorithm is not without its problems. This section
will discuss some of the issues that should be
understood
when
applying the genetic algorithm.
Premature Convergence
The problem of premature convergence is one of a lack of
diversity within the population. When a majority of the chromosomes
in the population is similar, the selection process has less
material to work with and the rate of fitness increase slows.
Premature convergence can be
detected
by comparing the average
fitness of the population with the maximum fitness. If they are
fairly
close to one another, then premature convergence has
occurred.
The most common reason for premature convergence is a population
that is too small for the problem. Increasing the
size
of the
population easily
solves
this problem. Another common reason is the
selection algorithm used. If an elitist algorithm is used, only the
highest-fit chromosomes may be selected, leading to a population
that is likely
descendent
from a small percentage of the initial
population. One solution here is called
restart.
This simply
means that if the population has prematurely
converged
without
finding a decent solution, simply start over. The
desire
is that by
restarting, new material will be introduced into the population
that may not have a small number of dominating chromosomes.
Epistasis
Epistasis is defined as the
interdependence
among the
variables
(genes) encoded in the chromosome. If no gene is
related
to another
in the chromosome, epistasis is small or non-existent. If genes are
dependent on one another, epistasis is high and can create
difficulties for the recombination algorithms.
A common solution to the problem is to keep genes (variables)
that are related close to one another in the chromosome. Grouping
the dependent genes means they are much less likely to be disrupted
during operators such as crossover.
The "No-Free-Lunch" Theorem
The "No-Free-Lunch" theorem is based upon the idea that there is
no optimal optimization method. Any encoding, selection-method, and
set of parameter probabilities will not blindly work for all
classes of problems. The key is to use knowledge of the problem at
hand to choose the best approach [Shaffer 1993].
Other Applications
The genetic algorithm can be used in a variety of optimization
problems. Since the
usefulness
of the genetic algorithm depends
most highly on the representation of the solution, any number of
numerical and symbolic problems may be optimized. For example, in
addition to simple function optimization, symbolic problems such as
the Towers of Hanoi problem can be very easily
solved
.
Genetic algorithms have been applied to many other practical
applications, such as:
The author has applied the genetic algorithm, as part of star
tracker research, to the problem of absolute attitude determination
using a star tracker. In this application, star quadrilaterals were
matched from an onboard star catalog to a set of stars in the
star-tracker's field of view to determine where the spacecraft was
pointing.
Summary
In this chapter, we've had our first look at the genetic
algorithm. We discussed the general operation of the algorithm and
a saw sample run through the algorithm to
demonstrate
initialization, fitness evaluation, selection, and recombination.
We then discussed source code that implements an evolver for
instruction sequences and
looked
at some of the sample equations
that were
solved
with it. Since the GA
knows
nothing about the
equations
themselves
, only if it's correct in solving them, the GA
provides alternate solutions to the problem (within the defined
instruction set) that demonstrated an optimization of the actual
algorithm. Finally, we discussed the parameters that can be tweaked
for the genetic algorithm and some of the problems that the
algorithm
presents
.