Genetic Algorithms
Both genetic algorithms and simulated annealing are evolutionary processes that
may be utilized to solve search space and optimization problems. However, genetic
algorithms differ substantially from simulated annealing.
Simulated annealing is based on a thermodynamic evolutionary process, whereas
genetic algorithms are based on the principles of Darwin’s theory of evolution and the
field of biology. Two features introduced by GAs, which distinguish them from simulated
annealing, are the inclusion of a population and the use of a genetic operator
called “crossover” or recombination.
A key component of evolution is natural selection. Organisms poorly suited to their
environment tend to die off, while organisms better suited to their current environment
are more likely to survive. The surviving organisms produce offspring that have
many of the better qualities possessed by their parents. As a result, these children
tend to be “better suited” to their environment, and are more likely to survive, mate,
and produce future generations. This process is analogous to Darwin’s “survival of the
fittest” theory, an ongoing process of evolution in which life continues to improve over
time. The same concepts that apply to natural selection apply to genetic algorithms as
well.
When discussing evolution, it is important to note that sometimes a distinction
is made between microevolution and macroevolution. Microevolution refers to small
changes that occur in the overall genetic makeup of a population over a relatively short
period of time. These changes are generally small adaptations to an existing species,
and not the introduction of a whole new species. Microevolution is caused by factors
such as natural selection and mutation. Macroevolution refers to significant changes
in a population over a long period of time. These changes may result in a new species.
The concepts of genetic algorithms are consistent with microevolution.
Background of Genetic Algorithms
John Holland, a professor at the University of Michigan, developed the concepts
associated with genetic algorithms through research with his colleagues and students.
In 1975, he published a book, Adaptation in Natural and Artificial Systems, in which
he presents the theory behind genetic algorithms and explores their practical application.
Holland is considered the father of genetic algorithms.
Another significant contributor to the area of genetic algorithms is David Goldberg.
Goldberg studied under Holland at the University of Michigan and has written
a collection of books, including Genetic Algorithms in Search, Optimization, and Machine
Learning (1989), and more recently, The Design of Innovation (2002).
Uses for Genetic Algorithms
Genetic algorithms are adaptive search algorithms, which can be used for many
purposes in many fields, such as science, business, engineering, and medicine. GAs are
adept at searching large, nonlinear search spaces. A nonlinear search space problem
has a large number of potential solutions and the optimal solution cannot be solved by
conventional iterative means. GAs are most efficient and appropriate for situations in
which:
• the search space is large, complex, or not easily understood;
• there is no programmatic method that can be used to narrow the search space;
• traditional optimization methods are inadequate.
Many optimization problems are nonlinear in behavior and are too complex for
traditional methods. The set of possible solutions for such a problem can be enormous
(e.g., determining the optimum route for a traveling salesperson or determining the
optimum design for an electrical circuit layout). A genetic algorithm possesses the
ability to search large and complex search spaces to efficiently determine near optimal
solutions in a reasonable time frame by simulating biological evolution. Now that you
have been introduced to some of the uses for genetic algorithms, we must examine how
to actually construct one.
Understanding Genetic Algorithms
Genetic algorithms closely resemble the biological model of chromosomes and
genes. Individual organisms in a genetic algorithm generally consist of a single chromosome.
These chromosomes are composed of genes. By manipulating the genes, new
chromosomes are created, which possess different traits. These manipulations occur
through crossover and mutation, just as they occur in nature. Crossover is analogous
to the biological process of mating, and mutation is one way in which new information
can be introduced into an existing population.
Understanding Genes
In a genetic algorithm, genes represent individual components of a solution. This
is a very important concept in the analysis of a problem for which a genetic algorithm
is to be used. To effectively solve a problem, you must determine a way to break it into
its related components, or genes. The genes will then be linked together to form a chromosome.
Life forms in this simulation consist of a single chromosome; therefore, each
chromosome will represent one possible solution to a problem.
It is important to note that there is a finite number of genes that are used. Individual
genes are not modified as the organisms evolve. It is the chromosomes that evolve
when the order and makeup of their genes are changed.
Understanding Chromosomes
As explained above, each organism in our genetic algorithm contains one chromosome.
As a result, each chromosome can be thought of as an “individual” or a solution
composed of a collection of parameters to be optimized. These parameters are
genes, which you learned about in the previous section. Each chromosome is initially
assigned a random solution or collection of genes. This solution is used to calculate a
“fitness” level, which determines the chromosome’s suitability or “fitness” to survive—
as in Darwin’s theory of natural selection. If a chromosome has a high level of “fitness,”
it has a higher probability of mating and staying alive.
How Genetic Algorithms Work
A genetic algorithm begins by creating an initial population of chromosomes that
are given a random collection of genes. It then continues as follows:
1. Create an initial population of chromosomes.
2. Evaluate the fitness or “suitability” of each chromosome that makes up the
population.
3. Based on the fitness level of each chromosome, select the chromosomes that
will mate, or those that have the “privilege” to mate.
4. Crossover (or mate) the selected chromosomes and produce offspring.
5. Randomly mutate some of the genes of the chromosomes.
6. Repeat steps three through five until a new population is created.
7. The algorithm ends when the best solution has not changed for a preset number
of generations.
Genetic algorithms strive to determine the optimal solution to a problem by utilizing
three genetic operators. These operators are selection, crossover, and mutation.
GAs search for the optimal solution until specific criteria are met and the process
terminates. The results of the process include good solutions, as compared to one “optimal”
solution, for complex problems (such as “NP-hard” problems). NP-hard refers
to problems which cannot be solved in polynomial time. Most problems solved with
computers today are not NP-hard and can be solved in polynomial time. A polynomial
is a mathematical expression involving exponents and variables. A P-Problem, or
polynomial problem, is a problem for which the number of steps to find the answer is
bounded by a polynomial. An NP-hard problem does not increase exponentially, but
often increases at a much greater rate, described by the factorial operator (n!).
Initial Population
To recap, the population of a genetic algorithm is comprised of organisms, each of
which usually contains a single chromosome. Chromosomes are comprised of genes,
and these genes are usually initialized to random values based on defined boundaries.
Each chromosome represents one complete solution to the defined problem. The
genetic algorithm must create the initial population, which is comprised of multiple
chromosomes or solutions.
Each chromosome in the initial population must be evaluated. This is done by evaluating
its “fitness” or the quality of its solution. The fitness is determined through the
use of a function specified for the problem the genetic algorithm is designed to solve.
Suitability and the Privilege to Mate
In a genetic algorithm, mating is used to create a new and improved population.
The “suitability” to mate refers to whether or not chromosomes are qualified to mate,
or whether they have the “privilege” to mate.
Determining the specific chromosomes that will mate is based upon each individual
chromosome’s fitness. The chromosomes are selected from the old population,
mated, and children are produced, which are new chromosomes. These new children
are added to the existing population. The updated population is used for selection of
chromosomes for the subsequent mating.
Mating
We will now examine the crossover process used in genetic algorithms to accomplish
mating. Mating is achieved by selecting two parents and taking a “splice” from
each of their gene sequences. These splices effectively divide the chromosomes’ gene
sequences into three parts. The children are then created based on genes from each of
these three sections.
The process of mating combines genes from two parents into new offspring chromosomes.
This is useful in that it allows new chromosomes to inherit traits from each
parent. However, this method can also lead to a problem in which no new genetic material
is introduced into the population. To introduce new genetic material, the process
of mutation is used.
Mutation
Mutation is used to introduce new genetic material into a population. Mutation
can be thought of as natural experiments. These experiments introduce a new, somewhat
random, sequence of genes into a chromosome. It is completely unknown whether
or not this mutation will produce a desirable attribute, and it does not really matter,
since natural selection will determine the fate of the mutated chromosome.
If the fitness of the mutated chromosome is higher than the general population,
it will survive and likely be allowed to mate with other chromosomes. If the genetic
mutation produces an undesirable feature, then natural selection will ensure that the
chromosome does not live to mate.
An important consideration for any genetic algorithm is the mutation level that
will be used. The mutation level is generally expressed as a percentage.
Selection of a mutation level has many ramifications. For example, if you choose a
mutation level that is too high, you will be performing nothing more than a random
search. There will be no adaptation; instead, a completely new solution will be tested
until no better solution can be found.
References:
Introduction to Neural Networks for C#, Second Edition
Second Edition
by Jeff Heaton
Heaton Research, Inc.
St. Louis