Biomedical Engineering Reference
In-Depth Information
cities while remaining lighter in rural England. The darker color was ''naturally selected'' in urban
populations. Since the passage of the Clean Air Act and the resulting reduction of coal burning,
numbers of light colored moths are now increasing in England's industrial towns.
There are many differences between natural processes and genetic algorithms. In nature, fitness
varies across species, across space, and over time. The fittest individuals of a particular species
18,000 years ago during the last ice age changed as climate warmed and the environment changed,
and as different species' ranges shifted with the warming climate. In a sense, ''fitness'' is a moving
target in nature. However, in genetic algorithms the fit function is well defined and does not change
over time.
Another major difference between natural evolution and genetic algorithms is that in nature
there is interaction between different species while none exists in genetic algorithms. In the moth
case, if there is an increase in the bird population, more moths are eaten. In nature, an important
measure of fitness relates to survival from predators. In genetic algorithms, there is only one defined
''species'' and the evolution occurs in a vacuum.
In genetic algorithms, when two combinations are compared, a mechanism for determining
which one is ''better'' is needed. This criterion is called the ''fit function'' named after the concept
of the survival of the fittest in nature. Typically, this fit function is the objective function. The
general framework of genetic algorithms is an evolving population of selected combinations.
A starting population (typically randomly generated) of combinations is established. Each gener-
ation follows a sequence of steps:
1.
Two population members are selected as parents. In most algorithms the two parents are randomly
selected but the selection may be governed by some other rule.
2.
The two parents are ''merged'' (mate) and produce an offspring. A successful merging process for
producing an offspring is probably the most important feature of a genetic algorithm.
3.
The population is updated. Some offspring are added to the population as some members are
removed. The rules by which offspring are added to the population and population members
''die'' also affect the effectiveness of the algorithm.
The process continues for a prespecified number of generations and the best member of the final
population is the result of the algorithm.
5.3
MODIFICATIONS OF THE GENETIC ALGORITHM FRAMEWORK
Over the years a variety of modifications have been proposed to the basic genetic algorithm
described above. It remains essential to design a good merging process for a successful genetic
algorithm. Once a satisfactory merging process is designed, these modifications may improve even
a good genetic algorithm.
Typically, as the population evolves, the genetic diversity among members declines and the
population becomes more homogeneous. This is because a ''good'' trait tends to remain in the
population and is transferred to new offspring who are more likely to join the population. ''Bad''
traits tend to disappear from the population because offspring with bad traits are less likely to
survive and join the population, and if they do join the population, they are more likely to be
discarded from it later in the evolutionary process. Most proposed modifications tend to increase
genetic diversity among population members thereby slow down the convergence of the population
to similar members. Increasing genetic diversity slows down the convergence as it increases the
chance to obtain the global optimum. If one of the necessary traits required for the global optimum
is missing from the population, the global optimum will be missed. Higher diversity increases the
probability that all necessary traits do exist in the population gene pool (possibly in different
members, though). If all traits exist in the gene pool, the combination that is needed for creating
the global optimum is more likely to be obtained by mating the ''right'' parents. On the other hand,
Search WWH ::
Custom Search