Genetic Algorithm 2
Genetic Algorithm 2
Genetic Algorithm 2
Evolutionary Computation
−Swarm intelligence
comprising ant colony optimization and particle swarm
optimization)
Advantages of EC
• Conceptual Simplicity
• Broad Applicability
• Hybridization with Other Methods
• Parallelism
• Robust to Dynamic Changes
• Solves Problems that have no Solutions
Genetic Algorithms
• Genetic algorithms are inspired by Darwin's theory of
natural evolution.
• In the natural world, organisms that are poorly suited for
an environment die off, while those well-suited, prosper.
• Genetic algorithms search the space of individuals for
good candidates.
• The chance of an individual's being selected is proportional
to the amount by which its fitness is greater or less than its
competitors' fitness.
Contd..
• Algorithm begins with a set of initial solutions (represented by
set of chromosomes) called population.
• A chromosome is a string of elements called genes.
• Solutions from one population are taken and are used to form a
new population by generating offsprings.
• New population is formed using old population and offspring
based on their fitness value.
• Promising candidates are kept and allowed to reproduce
• This is motivated by a hope, that the new population will be
better than the old one.
• Genetic algorithms are broadly applicable and have the
advantage that they require little knowledge encoded in the
system.
Outline of the Basic Genetic Algorithm
• [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.
• Repeat until terminating condition is satisfied
− [Selection] Select two parent chromosomes from a
population according to their fitness (the better fitness, the
bigger chance to be selected).
− [Crossover] Crossover the parents to form new offsprings
(children). If no crossover was performed, offspring is
the exact copy of parents.
− [Mutation] Mutate new offspring at selected position(s) in
chromosome).
− [Accepting] Generate new population by placing new
offsprings.
• Return the best solution in current population
Issues involved
11001011+11011111 = 11001111
Contd…
Two point crossover:
• two crossover points are selected,
• binary string from the beginning of the chromosome to
the first crossover point is copied from the first parent,
• the part from the first to the second crossover point is
copied from the other parent and
• the rest is copied from the first parent again
2. Mutation
Bit inversion: selected bits are inverted
11010011 => 11110010
Permutation Encoding
1. Crossover : Single point crossover -
• one crossover point is selected,
• the genes are copied from the first parent till the crossover
point, then
• the other parent is scanned and if the gene is not yet copied
in the offspring, it is added
• Note: there are more ways to produce the rest after
crossover point
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) =
(1 2 3 4 5 6 8 9 7)
2. Mutation: Order changing -
• two numbers are selected and exchanged
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
Value Encoding
1. Crossover
All crossovers methods from binary encoding can be used
2. Mutation
Adding (for real value encoding) - a small number is added to
(or subtracted from) selected values
(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)
Tree Encoding
1. Crossover
Tree crossover - one crossover point is selected in both parents,
and the parts below crossover points are exchanged to produce
new offspring
2. Mutation
Changing operator, number - selected nodes are changed
Advantages and Disadvantages of GA
• Applicable when little knowledge is encoded in
the system.
• Effective way of finding a reasonable solution to a
complex problem quickly.
• NP-complete problems can be solved in efficient
way.
• Parallelism and easy implementation is an
advantage.
• However, they give very poor performance on
some problems as might be expected from
knowledge-poor approaches.
Contd..
• There are NP-complete problems that can not be solved
algorithmically in efficient way.
• NP stands for nondeterministic polynomial and it means
that it is possible to guess the solution and then check it in
polynomial time.
• If we have some mechanism to guess a solution, then we
would be able to find a solution in some reasonable or
polynomial time .
• The characteristic for NP-problems is that algorithm is
usually O(2n) and it is not usable when n is large.
• For such problems, GA works well.
• But the disadvantage of GAs is in their computational
time.
• They can be slower than some other methods.
• Some of the problems are listed below
Choosing encoding and fitness function can be difficult.
GAs may have a tendency to converge towards local
optima or even arbitrary points rather than the global
optimum in many problems..
• GAs cannot effectively solve problems in which
the only fitness measure is right/wrong, as there is
no way to converge on the solution.
• In these cases, a random search may find a
solution as quickly as a GA.
GA Applications
• Control
• Design
• Scheduling
• Robotics
• Machine Learning
• Signal Processing
• Game Playing
• Combinatorial Optimization
More Specific Applications of GA
plus
x minus
10 y
Fitness Function
• The most difficult and important concept of GP is
the fitness function.
• The fitness function determines how well a
program is able to solve the problem.
• It varies greatly from one type of program to the
next.
• For example, if one were to create a genetic
program to set the time of a clock, the fitness
function would simply be the amount of time that
the clock is wrong.
Crossover Operation on two parents
Chromosome A Chromosome B
x + (10 – y) (plus x (minus 10 y)) (x + 5) * y (mult (plus x 5) y)
plus mult
x minus plus y
10 y x 5
Offspring 1 Offspring 2
x + (y + 5) (plus x (plus y 5)) (10 – y) * x (mult (minus 10 y) x)
plus mult
x plus minus x
y 5 10 y
Crossover Operation with identical parents
Chromosome A Chromosome B
x * y + (4 – y) (plus (mult x y) (minus 4 y)) x * y + (4 – y) (plus (mult x y)
(minus 4 y))
plus
plus
mult minus
mult minus
x y 4 y
x y 4 y
Offspring 1 Offspring 2
x *y + x * y (plus (mult x y) (mult x y))) (4 – y) + (4 – y) (plus (minus 4 y)
(minus 4 y))
plus
plus
mult mult
minus minus
x y x y
4 y 4 y
Advantages of genetic programming over genetic algorithm is that identical parents can yield different offsprings, while in
genetic algorithms identical parents would yield identical offspring.
Mutation
Chromosome
x * y + (4 – y) (plus (mult x y) (minus 4 y))
plus
mult minus
x y 4 y
Mutated chromosome with variable ‘y’ replaced by variable ‘x’
x * y + (4 – x) (plus (mult x y) (minus 4 x))
plus
mult minus
x y 4 x
Mutated chromosome with function ‘mult’ replaced by function ‘plus’
x * y + (4 – y) (plus (mult x y) (minus 4 y))
plus
plus minus
x y 4 x