Friday, July 26, 2013
Table of Contents
1.
Abstract-----------------------------------------------------------------2
2.
Introduction------------------------------------------------------------2
3.
How do Genetic
Algorithms work?---------------------------------2
4.
Search
Space-----------------------------------------------------------3
5.
Operators of
GA-------------------------------------------------------4
6.
Parameters of
GA-----------------------------------------------------5
7.
Data
representation and Operation Semantics--------------------6
8.
Recommendations----------------------------------------------------8
9.
Applications-----------------------------------------------------------9
10.
When to use
Genetic Algorithms?--------------------------------10
11.
When not to use
Genetic Algorithms?---------------------------10
12.
Conclusion-----------------------------------------------------------10
13.
Bibliography---------------------------------------------------------11
Genetic
Algorithms
Abstract:
Genetic
Algorithms are a part of evolutionary computing, which is a rapidly growing
area of artificial intelligence. Genetic Algorithms are inspired by Darwin’s
theory about evolution. The solution to a problem solved using genetic
algorithms is evolved. Algorithm is started with a set of solutions
(represented by chromosomes) called population. Solutions from
one population are taken and used to form a new population. This is motivated
by a hope, that the new population will be better than the old one. Solutions
that are selected to form new solutions (offspring) are selected
according to their fitness - the more suitable they are the more chances they
have to reproduce.
Introduction:
Genetic Algorithms
(GAs) are optimization techniques based on the concepts of natural selection
and genetics. In this approach the variables are represented as genes on
a chromosome. GAs feature a group of candidate solutions (population) on
the response surface. Through natural selection and the genetic operators – mutation
and recombination, chromosomes with better fitness are found. Natural
selection guarantees that chromosomes with the best fitness will propagate in
future populations.
Using the recombination
operator, the GA combines genes from two parent chromosomes to form two new
chromosomes (children) that have a high probability of having better fitness
than their parents. Mutation allows new areas of the response surface to
be explored. GAs offer a generational improvement in the fitness of the
chromosomes and after many generations will create chromosomes containing the optimized
variable settings.
How
do Genetic Algorithms work?
- [Start] Generate random population of n chromosomes (suitable solutions for the problem)
- [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
- [New population] Create a new population by repeating following steps until the new population is complete
- [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
- [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
- [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
- [Accepting] Place new offspring in a new population
- [Replace] Use new generated population for a further run of algorithm
- [Test] If the end condition is satisfied, stop, and return the best solution in current population
- [Loop] Go to step 2
Search Space:
If we are solving some problem, we are usually looking
for a solution, which will be the best among others. The space of all feasible
solutions ( it means objects among those the desired solution is) is called search
space ( also state space). Each point in the search space represents one
feasible solution. Each solution can be “marked” by its value or fitness for
the problem. We are looking for our solution, which is one point (or more)
among feasible solutions - that is one point in the search space.
The looking for a solution is then equal to a looking for
some extreme (minimum or maximum) in the search space. The search space can be
whole known by the time of solving a problem, but usually we know only a few
points from it and we are generating other points as the process of finding
solution continues.
The problem is that the search can
be very complicated. One does not know where to look for the solution and where
to start. There are many methods, how to find some suitable solution
(ie. not necessarily the best solution) – one among them is Genetic
Algorithms. The solution found by
these methods is often considered as a good solution, because it is not often
possible to prove what is the real optimum.
Operators of GA:
1.
Encoding of a chromosome: The chromosome should in some way contain information about
solution, which it represents. The most used way of encoding is a binary
string. The chromosome then could look like this:
|
Chromosome 1
|
1101100100110110
|
|
Chromosome 2
|
1101111000011110
|
Each chromosome has one binary string. Each bit in this string can
represent some characteristic of the solution.
2.
Crossover: Crossover selects genes from parent chromosomes and creates a new
offspring. The simplest way of how to do this is to choose randomly some
crossover point and everything before this point is copied from the first
parent and then everything after the crossover point is copied from the second
parent.
Crossover can then look like this ( | is the crossover point):
|
Chromosome 1
|
11011 | 00100110110
|
|
Chromosome 2
|
11011 | 11000011110
|
|
Offspring 1
|
11011 | 11000011110
|
|
Offspring 2
|
11011 | 00100110110
|
There are other ways how to make crossover, for example we can choose
more crossover points. Crossover can be rather complicated and very depends on
encoding of the encoding of chromosome. Specific crossover made for a specific
problem can improve performance of the genetic algorithm.
3.
Mutation: After a crossover is
performed, mutation takes place. This is to prevent grouping all solutions in
population into a local optimum of the problem to be solved. Mutation changes
randomly the new offspring. For binary encoding we can switch a few randomly
chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:
|
Original offspring 1
|
1101111000011110
|
|
Original offspring 2
|
1101100100110110
|
|
Mutated offspring 1
|
1100111000011110
|
|
Mutated offspring 2
|
1101101100110110
|
The mutation depends on the encoding as well as the crossover. For
example when we are encoding permutations, mutation could be exchanging two
genes.
Parameters
of GA:
There are two basic parameters of GA - crossover probability and
mutation probability. Population size is also another parameter.
1.
Crossover probability: says how often will be crossover performed. If there is no
crossover, offspring is exact copy of parents. If there is a crossover,
offspring is made from parts of parents' chromosome. If crossover probability
is 100%, then all offspring is made by crossover. If it is 0%,
whole new generation is made from exact copies of chromosomes from old
population. Crossover is made in hope that new chromosomes will have good parts
of old chromosomes and maybe the new chromosomes will be better. However it is
good to leave some part of population survive to next generation.
2.
Mutation probability: says how often parts of
chromosome will be mutated. If there is no mutation, offspring is taken after
crossover (or copy) without any change. If mutation is performed, part of
chromosome is changed. If mutation probability is 100%, whole chromosome
is changed, if it is 0%, nothing is changed.
Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to random search.
Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to random search.
3.
Population size:
says how many chromosomes are in population (in one
generation). If there are too few chromosomes, GA has a few possibilities to
perform crossover and only a small part of search space is explored. On the
other hand, if there are too many chromosomes, GA slows down.
Data
Representation and Operation Semantics
Selection: chromosomes are selected from the population to be parents to
crossover. The problem is how to select these chromosomes. According to
Darwin's evolution theory the best ones should survive and create new
offspring. There are many methods how to select the best chromosomes, for
example roulette wheel selection, Boltzman selection, tournament selection,
rank selection, steady state selection etc.
Encoding:
1.
Binary Encoding: In binary encoding every chromosome is a string of bits,
0 or 1.
|
Chromosome A
|
101100101100101011100101
|
|
Chromosome B
|
111111100000110000011111
|
Example of chromosomes with binary encoding
Binary encoding gives many possible chromosomes even with a small
number of alleles. On the other hand, this encoding is often not natural for
many problems and sometimes corrections must be made after crossover and/or
mutation.
2.
Permutation Encoding: In permutation encoding, every chromosome is a string of
numbers, which represents number in a sequence.
|
Chromosome A
|
1 5 3 2 6 4 7 9 8
|
|
Chromosome B
|
8 5 6 7 2 3 1 4 9
|
Example of chromosomes with permutation encoding
Permutation encoding is only useful for ordering problems.
3.
Value Encoding: In value encoding, every chromosome is a string of some
values. Values can be anything connected to problem, form numbers, real numbers
or chars to some complicated objects.
|
Chromosome A
|
1.2324 5.3243 0.4556 2.3293 2.4545
|
|
Chromosome B
|
ABDJEIFJDHDIERJFDLDFLFEGT
|
|
Chromosome C
|
(back),
(back), (right), (forward), (left)
|
Example of chromosomes with value encoding
Value encoding is very good for some special problems. On the other
hand, for this encoding it is often necessary to develop some new crossover and
mutation specific for the problem.
4.
Tree Encoding: In tree encoding every chromosome is a tree of some objects,
such as functions or commands in programming language.
|
Chromosome A
|
Chromosome B
|
 |
 |
|
( + x
( / 5 y ) )
|
( do_until
step wall )
|
Example of chromosomes with tree encoding
Tree encoding is good for evolving programs. Programming language
LISP is often used to this, because programs in it are represented in this form
and can be easily parsed as a tree, so the crossover and mutation can be done
relatively easily.
Crossover
and Mutation: Crossover and mutation are two basic
operators of GA. Performance of GA very much depends on them. Type and
implementation of operators depends on encoding and also on a problem.
Recommendations
- Crossover rate
Crossover rate generally should be high, about 80%-95%. - Mutation rate
On the other side, mutation rate should be very low. Best rates reported are about 0.5%-1%. - Population size
Good population size is about 20-30, however sometimes sizes 50-100 are reported as best. Best population size depends on encoding, on size of encoded string. - Selection
Basic roulette wheel selection can be used, but sometimes, rank selection can be better. There is also some more sophisticated method, which changes parameters of selection during run of GA. - Encoding
Encoding depends on the problem and also on the size of instance of the problem. - Crossover and mutation type
Operators depend on encoding and on the problem.
Applications
of GA
Genetic algorithms have been used for difficult problems (such as
NP-hard problems), for machine learning and also for evolving simple programs.
Advantage of GAs is in their parallelism. GA is traveling in a
search space with more individuals so they are less likely to get stuck in a
local extreme like some other methods.
Disadvantage of GAs is in their computational time. They can be
slower than some other methods. But with today’s computers it is not so big
problem.
Some
Applications:
- Nonlinear dynamical systems - predicting, data analysis
- Designing neural networks, both architecture and weights
- Robot trajectory
- Evolving LISP programs (genetic programming)
- Strategy planning
- Finding shape of protein molecules
- TSP and sequence scheduling
- Functions for creating images
When to use Genetic Algorithms?
- When not much is known about the response surface
- GAs do not optimize directly on the variables but on their representations
- GAs are an optimal choice in situations where the variables being optimized are very different from each other (i.e. a mixture of integers, binary values, and floating points numbers)
When not to use Genetic Algorithms?
- Applications which require that the exact global optimum be found may be a challenge for a GA. GAs are best at reaching the global optimum region but sometimes have trouble reaching the exact optimum location.
- One of the most commonly cited difficulties with GAs is that compared to hill-climbing techniques they generally require more response (fitness) function evaluations.
Conclusion:
Genetic Algorithms are more than just another optimization method.
GAs may be used to study how evolution occurs and also in understanding other
esoteric concepts. A genetic algorithm once written may be reused for another
situation just by changing the fitness function according to the new
requirements.
Bibliography:
1.
Introduction to genetic
algorithms with Java applets -- http://cs.felk.cvut.cz/~xobitko/ga/
2.
Practical Guide to Genetic
Algorithms –
http://chemdiv-www.nrl.navy.mil/6110/sensors/chemometrics/practga.html
