|
|
 |
 |
Genetic algorithms are general-purpose search algorithms based
upon the principles of evolution observed in nature. Genetic algorithms
combine selection, crossover, and mutation operators with the goal
of finding the best solution to a problem. Genetic algorithms search
for this optimal solution until a specified termination criterion
is met.
|
The
solution to a problem is called a chromosome. A chromosome
is made up of a collection of genes which are simply the parameters
to be optimized. A genetic algorithm creates an initial population
(a collection of chromosomes), evaluates this population,
then evolves the population through multiple generations (using
the genetic operators discussed above) in the search for a
good solution for the problem at hand.
Genetic
algorithms can be applied to a wide variety of
|
|
|
| optimization
problems such as scheduling, computer games, stock market trading,
|
| medical,
adaptive control, transportation, the traveling salesmen problem,
etc |
Despite
their superficial differences, the four main approaches to evolutionary
computing share the same basic template. Whether you favor genetic
algorithms, evolutionary programming, evolution strategies or genetic
programming, you will have to start with a random or semi random
population of candidate solutions and you will have to devise a
'fitness function'.
The
fitness function is a feedback system to measure how well each individual
within the population performs in terms of the designated task or
problem. Individuals that do well have a greater probability of
passing their genetic information onto the next generation. The
rules governing how offspring are generated from parents are encoded
in the genetic operators. These cover:
- reproduction
(how exactly candidates are selected for breeding)
- mutation
(whether, and at what rate, random changes will occur in genetic
information)
- recombination
(when this operator is used, successful individuals exchange genetic
information with other successful individuals to form offspring).
- What
chiefly distinguishes one evolutionary approach from another is
choice of representation and choice of genetic operator.
Consider
the problem of maximizing the function f(x) = x2, for x between
0 and 31.
-
The
decision variable must be encoded : since x may take any value
between 0 and 31, it will be coded as a five-bit, binary unsigned
integer.
-
The
initial population is generated at random.
-
Fitness
values are calculated for each string in the initial population,
merely by calculating f(x) for each decoded value of x. e.g.
'01000' decodes to '8', fitness is calculated as x2, which is
82 = 64.
-
The
next generation of the genetic algorithm begins with reproduction.
This is a simple copying operation, subject to weightings derived
from the fitness values. Candidates with high fitness will have
a greater probability of being reproduced in the succeeding
generation and those with worst fitness will tend to die off.
-
The
crossover procedure has two steps.
-
Strings
are mated randomly.
-
Mated
string couples cross over, using randomly selected crossing
sites
-
The
last operator, mutation, is performed on a bit-by-bit basis.
Assuming arbitrarily that the probability of mutation is 0.001,
with 20 transferred bit positions, we should expect 20x0.001
= 0.02 bits to undergo mutation during a given generation.
-
The
new population is now ready to be assigned fitness values, and
tested.
Evolutionary
computing harnesses the power of natural selection to turn computers
into automatic optimization and design tools. The three mechanisms
that drive evolution forward are reproduction, mutation and the
Darwinian principle of survival of the fittest. In the biological
world these mechanisms enable life forms to adapt to a particular
environment over successive generations. The camel's hump, the eagle's
eye, the dolphin's sonar, the crafty human brain itself; all these
solutions to environmental problems were generated by evolution.
All bear witness to its power as a universal optimizer. Like evolution
in nature, evolutionary computing also breeds progressively better
solutions to a wide variety of complex problems.
White
papers on our products and technologies are available upon request.
E-mail us at innovation@bluetronix.net
or call 440.247.3434.
|
