GENETIC ALGORITHM

APPLICATIONS OF
GENETIC ALGORITHMS
• I m a g e Proc ess in g —GAs are used for various digital image processing (DIP) tasks
as well like dense pixel matching.

• Vehicle routing problems - With multiple soft time windows, multiple depots and
a heterogeneous fleet.

• Scheduling applications —GAs are used to solve various scheduling problems as

well, particularly the time tabling problem.

• Machine Learning — as already discussed, genetics based machine learning

(GBML) is a niche area in machine learning.

• Robot Trajectory Generation GAs have been used to plan the path which a
robot arm takes by moving from one point to another.

• Parametric Design of Aircraft — GAs have been used to design aircrafts by

varying the parameters and evolving better solutions.

• DNA Analysis —GAs have been used to determine the structure of DNA using
spectrometric data about the sample.

• Multimodal Optimization — GAs are obviously very good approaches for

multimodal optimization in which we have to find multiple optimum solutions.

• Traveling salesman problem and its applications —GAs have been used to
solve the TSP, which is a well-known combinatorial problem using novel crossover
and packing strategies.
Genetic Algorithm– Basic Algorithm
➢ Starting with a subset of n randomly chosen solutions from the
search space (i.e. chromosomes).
This is the population.

➢ This population is used to produce a next generation of

individuals by reproduction.

➢ Individuals with a higher fitness have more chance to reproduce

(i.e. natural selection).
Comparison of Natural and GA Terminology

Natural Genetic Algorithm

Chromosome String
Gene Feature or character
Allele Feature value
Locus String position
Genotype Structure
Phenotype Parameter set, a decoded structure
 C mmosome

POPULATION
(set of chromosomes)
 • All individuals in population
evaluated by fitness function.

• Individuals allowed to
reproduce (selection),
crossover, mutate.

Flowchart of GA
Genetic Algorithm (3) – Basic Algorithm

Outline of the basic algorithm

1 START : Create random population of n chromosomes

2 FITNESS : Evaluate fitness f(x) of each chromosome in the
population
2 NEW POPULATION
1 REPRODUCTION/SELECTION : Based on f(x)
2 CROSS OVER : Cross-over chromosomes
3 MUTATION : Mutate chromosomes

3 REPLACE : Replace old with new population: the new generation

4 TEST : Test problem criterium
5 LOOP : Continue step 1 – 4 untill criterium is satisfied
 OPERATORS IN GA

• Coding
• Selection
• Crossover/Recombination
• Mutation
 ENCODING/CODING
• Process of representing individual gene
• Depends mainly on solving the problem
• Different coding techniques are
– Binary encoding
– Octal encoding
– Hexadecimal encoding
– Permutation/Real number Encoding
– Value encoding
– Tree encoding
 Binary Encoding
• Each chromosome encodes a binary string
• Each bit represent some characteristics

CHROMOSOME 1 110100011010
CHROMOSOME 2 110111111010
 Octal Encoding
• Each chromosome encodes an octal string
• From 0- 7

CHROMOSOME 1 03467216
CHROMOSOME 2 72561423
 Hexadecimal Encoding
• Each chromosome encodes a hexadecimal string
• From 0- 9,A-F

CHROMOSOME 1 9CE7
CHROMOSOME 2 3DBA
 Permutation Encoding
• Each chromosome encodes a string of numbers
represented in sequence
• Only useful for ordering problem
CHROMOSOME 1 153264798
CHROMOSOME 2 856723149
 Value Encoding
• Each chromosome encodes a string of values and
values can be anything concerning the problem

CHROMOSOME 1 1.2354 3.5687 4.7894 5.897461

CHROMOSOME 2 ASDFGERTYUILKJGF
CHROMOSOME 3 (back),(back),(forward), (right), (left)
 SELECTION
• Selection is the process of choosing 2 parents
from population for crossing
• After deciding an encoding next step is to
decide how to perform selection
• Selection is the method that randomly pick
chromosomes out of the population according
to their evaluation function
• The higher the fitness function value , the better
chance that an individual will be selected
 SELECTION
• The selection pressure is defined as the degree to which the
better individuals are favored
• The higher the selection pressured, the more the individuals are
favored
• The convergence rate of GA is largely determined by the
magnitude of the selection pressure
• Higher selection pressure resulting in the higher convergence
rate
• If the selection pressure is too low, the convergence rate will be
slow and the GA will take unnecessarily longer to find the
optimal solution
• If the selection pressure is too high , there is an increased change
of the GA prematurely converging to an incorrect solution
 SELECTION
• Two type of selection scheme
– Proportionate based selection
• Pick out the individuals based upon their fitness values
relative to the fitness of other individuals in the
population
• Selection pressure depends on the fitness
– Ordinal based selection
• Not based on their fitness value
• Upon the rank within the population
• Selection pressure is independent of the fitness
 SELECTION
• Various selection methods are
– Roulette Wheel Selection
– Random Selection
– Rank Selection
– Tournament Selection
– Boltzmann Selection
– Stochastic Universal Sampling
Roulette Wheel Selection
 Roulette Wheel Selection
• Consider a circular wheel.
• The wheel is divided into n pies, where n is the number
of individuals in the population.
• Each individual gets a portion of the circle which is
proportional to its fitness value.
• In a roulette wheel selection, the circular wheel is
divided as described before.
• A fixed point is chosen on the wheel circumference as
shown and the wheel is rotated.
• The region of the wheel which comes in front of the
fixed point is chosen as the parent.
• For the second parent, the same process is repeated.
 Roulette Wheel Selection
• It is clear that a fitter individual has a greater pie on
the wheel and therefore a greater chance of landing
in front of the fixed point when the wheel is
rotated.
• Therefore, the probability of choosing an individual
depends directly on its fitness.
• Implementation wise, we use the following steps –
– Calculate S = the sum of a fitnesses.
– Generate a random number between 0 and S.
– Starting from the top of the population, keep adding the
finesses to the partial sum P, till P<S.
– The individual for which P exceeds S is the chosen
individual.
 Roulette Wheel Selection

• Easier to implement
• But Noisy
• Depends on the variance of fitness in the
population
 Random Selection
• Randomly selects a parent from the population
• A little more disruptive
 Rank Selection
• Rank selection ranks the population and every
chromosome receives fitness from the ranking
• The worst has fitness 1 and the best has fitness N
• It results in slow convergence but prevents too
quick convergence
• It also keep up selection pressure when the
fitness variance is low
• Preserve diversity
 Rank Selection
• There are many ways for rank selection
– Select a pair of individual at random. Generate a
random number R between 0 and 1 . If R<r use the
first individual as parent. This is repeated to select the
second parent. The value of r is a parameter to this
method
– Select two individuals at random. The individual with
a highest evaluation become the parent. Repeat to
find the second parent
Tournament Selection
 Tournament Selection
• In K-Way tournament selection, we select K
individuals from the population at random and
select the best out of these to become a parent.
• The same process is repeated for selecting the
next parent.
• Tournament Selection is also extremely popular
in literature as it can even work with negative
fitness values.
 Boltzmann Selection
• This method simulates the process of slow cooling of molten
metal to achieve the minimum function value in a
minimization problem
• Controlling a temperature like parameter introduced with the
concept of Boltzmann probability distribution simulate the
cooling phenomenon
• In Boltzmann selection, a continuously varying temperature
controls the rate of selection according to a preset schedule
• The temperature start out high, which means that the
selection pressure is low
• The temperature is gradually lowered, which gradually
increase the selection pressure
• Thereby allowing the GA to narrow in more closely to the
best part of the search space
 Stochastic Universal Sampling
• Stochastic Universal Sampling is quite similar to
Roulette wheel selection, however instead of having
just one fixed point, we have multiple fixed points as
shown in the following image.
• Therefore, all the parents are chosen in just one spin
of the wheel.
• Also, such a setup encourages the highly fit
individuals to be chosen at least once.
 CROSSOVER
• Cross over is a process of taking two parent
solution and producing from them a child
• After the selection process the population is
enriched with better individuals
• Reproduction makes the clone of good strings
but does not create new one
• Crossover operator is applied to the matting
pool with a hope that it creates a better
offspring
 CROSSOVER
• Cross over is a recombination operator that
proceeds in three steps
1. The reproduction operator select at random a
pair of 2 individual strings for the matting
2. A cross site is selected at random along the
string length
3. Finally, the position values are swapped
between the two strings following the cross
site
 CROSSOVER
• Various crossover techniques are
– Single- point Crossover
– Two- point crossover
– Multipoint cross over/N point cross over
– Uniform Crossover
– Three parent Crossover
– Crossover with reduced Surrogate
– Shuffle crossover
– Precedence Preservative Crossover
– Ordered crossover
– Partially matched crossover
 Single-Point Crossover
• In this one-point crossover, a random crossover point is
selected and the tails of its two parents are swapped to
get new off-springs.
 Two-Point Crossover
• Two crossover points are chosen and the content between
these points are exchanged between two matted parents
 Two-Point Crossover
• But with one point cross over , the head and tail of
one chromosome cannot be passed together to the
offspring
• If both the head and tail of chromosome contain
good genetic information, none of the offspring
obtain directly with the one point crossover
• Using two point crossover one can overcome these
drawbacks so it is better than one point cross over
 Multi-Point Crossover/
(N-Point crossover)
• Multi point crossover is a generalization of the one-point
crossover wherein alternating segments are swapped to
get new off-springs.
 Uniform Crossover

PARENT 1 10110011
PARENT 2 00011010
MASK 11010110
CHILD 1 10011010
CHILD 2 00110011
 Uniform Crossover
• Each gene in the offspring is created by copying the corresponding
gene from the one or other parent chosen according to the random
generated binary crossover mask of same length as the
chromosome
• Where there is a 1 in the crossover point, the gene is copied from
the first parent
• Where there is a 0 in the mask , the gene is copied from the second
parent
• A new crossover mask is generated for each parent pair
• Offspring therefore contain a mixture of gene from each parent
• The number of effective crossing point is not fixed , but will be the
average of L/2 where L is the chromosome length
Uniform Crossover
Genetic Algorithm – Uniform Crossover
Generate uniformly random number.

X1 = 0110001010
X2 = 1100000111
Uniformly generated = 1 0 0 0 0 0 1 0 0 0
As a result, the new population becomes,

X1 = 1110000010

X2 = 0100001111
Three- Parent Crossover

PARENT 1 11010001
PARENT 2 01101001
PARENT 3 01101100
CHILD 01101001
 Three- Parent Crossover
• Three parents are randomly chosen
• Each bit of the first parent is compared with
the bit of second parent.
• If both are same, the bit is taken for the
offspring
• Otherwise bit from the third parent is taken
for the offspring
Crossover with Reduced Surrogate
The reduced surrogate operator constrains
crossover to always produce new individuals
wherever possible.

This is implemented by restricting the location of

crossover points such that crossover points
only occur where gene values differ.
 Shuffle Crossover
Shuffle crossover is related to uniform crossover.
A single crossover position (as in single-point
crossover) is selected.
But before the variables are exchanged, they are
randomly shuffled in both parents.

After recombination, the variables in the

offspring are un shuffled.

This removes positional bias as the variables are

randomly reassigned each time crossover is
performed.
Precedence Preservative Crossover
(PPX)
• Developed for vehicle routing problems
• The operator passes on precedence relation of
operations given in two parental permutations to
one offspring at the same rate, while no new
precedence relations are introduced
1. A vector of length Sigma, sub i=1to mi, representing the
number of operations involved in the problem, is randomly
filled with elements of the set {1, 2}.
2. This vector defines the order in which the operations are
successively drawn from parent 1 and parent 2.
3. We can also consider the parent and offspring
permutations as lists, for which the operations ‘append’
and ‘delete’ are defined.
4. First we start by initializing an empty offspring.
5. The leftmost operation in one of the two parents is selected
in accordance with the order of parents given in the vector.
6. After an operation is selected it is deleted in both parents.
7. Finally the selected operation is appended to the offspring.
8. This step is repeated until both parents are empty and the
offspring contains all operations involved.
Precedence Preservative Crossover
(PPX)
 Ordered Crossover
• Ordered two-point crossover is used when the problem is of
order based, for example in U-shaped assembly line
balancing etc.
• Given two parent chromosomes, two random crossover
points are selected partitioning them into a left, middle and
right portion.
• The ordered two-point crossover behaves in the following
way:
child 1 inherits its left and right section from parent 1,
and its middle section is determined by the genes in the
middle section of parent 1 in the order in which the values
appear in parent 2.
• A similar process is applied to determine child 2.
 Mutation
➢ After crossover, the strings are subjected to mutation.
Mutation prevents the algorithm to be trapped in a
local minimum.
➢ Mutation plays the role of recovering the lost genetic
materials as well as for randomly disturbing genetic
information.
➢ It is an insurance policy against the irreversible loss of
genetic material. Mutation has traditionally considered
as a simple search operator.
➢ If crossover is supposed to exploit the current solution
to find better ones, mutation is supposed to help for the
exploration of the whole search space.
➢ Mutation of a bit involves flipping a bit, changing 0 to 1
and vice-versa.
 Mutation Methods
➢Flipping
➢Interchanging
➢Reversing
 Flipping
Flipping of a bit involves changing 0 to 1 and 1 to
0 based on a mutation chromosome generated.
A parent is considered and a mutation
chromosome is randomly generated.
 Interchanging
Two random positions of the string are
chosen and the bits corresponding to
those positions are interchanged.
 Reversing
A random position is chosen and the bits
next to that position are reversed and
child chromosome is produced.
 Mutation Probability
➢ The important parameter in the mutation technique is
the mutation probability (Pm).
➢ The mutation probability decides how often parts of
chromosome will be mutated.
➢ If there is no mutation, offspring are generated
immediately after crossover (or directly copied)
without any change.
➢ If mutation is performed, one or more parts of a
chromosome are changed. If mutation probability is
100%, whole chromosome is changed.
➢ if it is 0%, nothing is changed.
➢ Mutation generally prevents the GA from falling into
local extremes.
➢ Mutation should not occur very often, because then GA
will in fact change to random search.
 Stopping condition for GA flow
➢ Best Individual: A best individual convergence criterion
stops the search once the minimum fitness in the
population drops below the convergence value. This brings
the search to a faster conclusion guaranteeing at least one
good solution.
➢ Worst individual: Worst individual terminates the search
when the least fit individuals in the population have fitness
less than the convergence criteria. This guarantees the
entire population to be of minimum standard, although the
best individual may not be significantly better than the
worst. In this case, a stringent convergence value may
never be met, in which case the search will terminate after
the maximum has been exceeded.
 Stopping condition for GA flow
➢ Sum of Fitness: In this termination scheme, the
search is considered to have satisfaction
converged when the sum of the fitness in the
entire population is less than or equal to the
convergence value in the population record.
➢ Median Fitness: Here at least half of the
individuals will be better than or equal to the
convergence value, which should give a good range
of solutions to choose from.