Introduction to Genetic

Algorithms

Dr. Subrajeet Mohapatra

Assistant Professor
Department of Computer Science & Engineering,
BIT Mesra, Ranchi
Jharkhand
 Copyright Information

• The course materials is intended only for instructional purpose of students of

BIT Mesra
• Students can take notes and make copies of course materials only for
individual use
• Enrolled students should not reproduce, distribute or display
(post/upload) lecture notes or recordings or course materials in any other way
without my express written consent
• The teacher in-charge for this course material will not be responsible for
violation of above policies by the students
• Students violating the above policies may be subject to student conduct
proceedings
 Disclaimer & Fair Dealing Statement

• The author of this course material will not be held personally responsible, nor
liable for any damages, actual or consequential, for any posts by third parties
which may violate any law.
• This course material may contain copyrighted material the use of which has not
always been specifically authorized by the copyright owner
• Use of materials in the presentation constitutes a ‘fair dealing of any such
copyrighted material
• The material contained in this presentation is used without profit for research
and educational purposes only
 Introduction to
Solving Optimization Problems
 Introduction to Optimization
• An optimization problem is the problem of finding the best
solution from all feasible solutions.
• The act of obtaining the best result under given circumstances.
• Defined as the process of finding the conditions that give the
maximum or minimum of a function.
• Finding an optimum value that is either minimum or maximum
value.
• The optimum seeking methods are also known as mathematical
programming techniques and are generally studied as a part of
operations research.
 Defining an Optimization Problem
• Economics is filled with optimization problems

Consumers make Businesses make Businesses make

buying decisions to hiring/capital pricing decisions to
maximize utility investment decisions maximize profits
to minimize costs

We need some
tools to analyze
these
optimization
problems

Consumers make Consumers make

labor decisions to savings decisions to
maximize utility maximize utility
 Concept of Optimization Problem
• Optimization basically means determining optimum value that
is either minimum or maximum value.

A function can be mathematically represented as : y = F(x)

Example:
2x − 6y = 11
or
y = (2x − 11) ÷ 6
Can we determine an optimum value for y?
Similarly, in the following case
3x + 4y ≥ 56.

These are really not related to optimization problem!

 Defining an Optimization Problem
• Requirement :
• To design an optimal pointer made of some material with density ρ.
• Pointer should be as large as possible, no mechanical breakage and
deflection of pointing at end should be negligible.
• Goal : Select the best pointer out of all possible pointers.
Defining an Optimization Problem
Defining an Optimization Problem
 Types of Optimization Problems
• Constrained & Unconstrained Optimization Problem
• Integer Programming, Real Valued and Mixed Integer
Programming Optimization Problem
• Linear & Non-Linear Optimization Problem
 Types of Optimization Problems
Unconstrained Optimization Problem
Problem is without any functional constraint.
 Types of Optimization Problems
Constrained Optimization Problem
Optimization problem with one or more functional constraint(s).
 Types of Optimization Problems
Integer Programming Problem

If all the design variables take some integer values.

 Types of Optimization Problems
Real-valued problem
If all the design variables are bound to take real values.

Mixed-integer programming problem

Some of the design variables are integers and the rest of the variables take
real values.
 Types of Optimization Problems
Linear Optimization Problem
Both objective functions as well as all constraints are found to be some
linear functions of design variables.
 Types of Optimization Problems
Non-linear optimization problem
If either the objective function or any one of the functional constraints are
non-linear function of design variables.
Traditional Approaches to Solve
Optimization Problems
 Interpreting Solutions
• A feasible solution is a set of values for the decision
variables that satisfies all of the constraints in an
optimization problem.
• The set of all feasible solutions defines the feasible region of
the problem.
• Most optimization algorithms operate by first trying to locate
any feasible solution, and then attempting to find another
(better) feasible solution that improves the value of the
objective function.
• The process of trying to find improving feasible solutions
repeats until either no further improvement is possible or
some other stopping criteria is met.
Interpreting Solutions
Example : Analytical Method
 Example : Analytical Method
Note:
• An inflection point is a point, that is, neither a maximum nor a
minimum at that point.
• Following figure explains the concepts of minimum, maximum
and saddle point.
Duality Principle
 Limitations of Traditional Optimization
Approaches
• Computationally expensive
• For a discontinuous objective function, methods may fail
• Method may not be suitable for parallel computing
• Discrete (integer) variables are difficult to handle
• Methods may not necessarily adaptive

Soft Computing techniques have been evolved to address the above

mentioned limitations of solving optimization problem with traditional
approaches.
 Evolutionary Algorithms
The algorithms, which follow some biological and physical
behaviors:
Biologic Behaviors:
Genetics and Evolution –> Genetic Algorithms (GA)
Behavior of Ant colony –> Ant Colony Optimization (ACO)
Behavior of Bee colony –> Bee Colony Optimization (BCO)
Human nervous system –> Artificial Neural Network (ANN)

Physical Behaviors:
Annealing process –> Simulated Annealing (SA)
Swarming of particle –> Particle Swarming Optimization (PSO)
 Evolution
The process by which modern organisms have descended
from ancient ones

Microevolution

Microevolution is evolution within a single population; (a

population is a group of organisms that share the same
gene pool). Often this kind of evolution is looked upon as
change in gene frequency within a population
 Evolution
For evolution to occur

Heredity
Information needs to be passed on from one generation
to the next

Genetic Variation
There has to be differences in the characteristics of
individuals in order for change to occur

Differential Reproduction
Some individuals need to (get to) reproduce more than
others thereby increasing the frequency of their genes in
the next generation
 Evolution
Heredity

Heredity is the transfer of characteristics (or traits) from

parent to offspring through genes
 Evolution
Genetic Variation

Is about variety in the population and hence presence of

genetic variation improves chances of coming up with
“something new”

The primary mechanisms of achieving genetic variation are:

Mutations Gene Flow Reproduction

 Evolution
Mutation

It is a random change in DNA

It can be beneficial, neutral or harmful to the organism

Not all mutations matter to evolution

 Evolution
Gene Flow
Migration of genes from one population to another

If the migrating genes did not exist previously in

the incident population then such a migration adds
to the gene pool
 Evolution
Reproduction

This type of producing young one can introduce new

gene combinations through genetic shuffling
 Evolution
Differential Reproduction

As the genes show up as traits (phenotype) the

individuals get affected by what is around; some die
young while others live

Those who live compete for mates; only the winners pass
on their gene to the next generation

In some sense the fitter (with respect to the current

environment) gets to leave more of his/her genes in the
next population; often the term fitness is used to
describe the relative ability of individuals to pass on
their genes
 Evolution

Variation Heredity

Differential Reproduction
A brief account on Evolution : Natural Selection

Four primary premises:

1. Information propagation: An offspring has many of its
characteristics of its parents (i.e. information passes from
parent to its offspring). [Heredity]
2. Population diversity: Variation in characteristics in the
next generation. [Diversity]
3. Survival for existence: Only a small percentage of the
offspring produced survive to adulthood.
4. [Selection] Survival of the best: Offspring survived depends
on their inherited characteristics. [Ranking]
 A brief account on Genetics
• The basic building blocks in living bodies are cells.
• Each cell carries the basic unit of heredity, called gene.

For a particular species, number of chromosomes is fixed.

Examples :
• Mosquito: 6
• Frogs: 26
• Human: 46
• Goldfish: 94 etc.
 A brief account on Genetics
Genetic Code

• Spiral helix of protein substance is called DNA.

• For each species, DNA code is unique, that is, vary uniquely
from one to other.
• DNA code (inherits some characteristics from one generation
to next generation) and is used as biometric trait.
 A brief account on Genetics
Reproduction
 A brief account on Genetics
Crossover
 A brief account on Genetics
Mutation

• A mutation is a change that

occurs in our DNA sequence,
either due to mistakes when the
DNA is copied or as the result
of environmental factors.
• Mutations contribute to genetic
variation within species.
• Results in changes in
the proteins that are made and
this can be a bad or a good
thing.
Complete Biological Process
 Genetic Algorithms : Quick Overview
Definition of GA : Genetic algorithm is a population-based probabilistic
search and optimization techniques, which works based on the
mechanisms of natural genetics and natural evolution.

• Developed: USA in the 1970’s

• Early names: J. Holland, K. DeJong, D. Goldberg
• Typically applied to:
– discrete optimization
• Attributed features:
– not too fast
– good heuristic for combinatorial problems
• Special Features:
– Traditionally emphasizes combining information from good parents
(crossover)
– many variants, e.g., reproduction models, operators
 Genetic Algorithms : Quick Overview

• It is a subset of evolutionary algorithm:

• Ant Colony optimization
• Swarm Particle Optimization
• Models biological processes:
• Genetics : Gregor Johan Mendel (1865)
• Evolution : Charles Darwin (1875)
• Holland’s original GA is now known as the simple genetic
algorithm (SGA)
• Other GAs use different:
– Representations
– Mutations
– Crossovers
– Selection mechanisms
 Genetic Algorithms : Working Framework

Note:
• GA is an iterative process.
• It is a searching technique.
• Working cycle with /
without convergence.
• Solution is not necessarily
guaranteed.
Genetic Algorithms : Detailed Framework
 Optimization Problem Solving using GA
• For solving the optimization problem using GA, it is required to
identify the following:
• Objective function(s)
• Constraint(s)
• Input parameters
• Fitness evaluation (it may be algorithm or mathematical formula)
• Encoding
• Decoding
 Salient Features of Simple GA

• Have overlapping generation (Only fraction of individuals are

replaced).
• Computationally expensive.
• Good when initial population size is large.
• In general, gives better results.
• Selection is biased toward more highly fit individuals (The average
fitness (of overall population) is expected to increase in each
succession).
• The best individual may appear in any iteration.
 Genetic Operators
• Genetic operators guide the algorithm towards a solution to a
given problem.
• Different types of genetic operators
• Mutation
• Crossover
• Selection
• All the operators work in conjunction with one another in order
for the algorithm to be successful (reach global optimum).
• Other important terms related to GA
• Encoding
• Convergence Test
• Mating pool
• Fitness Evaluation
 Different Encoding Schemes
Different GAs
• Simple Genetic Algorithm (SGA)
• Steady State Genetic Algorithm (SSGA)
• Messy Genetic Algorithm (MGA)
Encoding Schemes
• Binary encoding
• Real value encoding
• Order encoding
• Tree encoding
 Different Encoding Schemes
• Genetic Algorithms are specified according to the encoding
scheme it follows.
Encoding Scheme
• Binary encoding -- Binary Coded GA or simply Binary GA
• Real value encoding -- Real Coded GA or simply Real GA
• Order encoding -- Order GA (or Permuted GA)
• Tree encoding
 Encoding Schemes in GA
• GA uses metaphor consisting of two distinct elements :
• Individual Population -- a single solution
• Population – A set of individuals at an instant of searching process.
• An individual is defined by a chromosome.
• A chromosome stores genetic information (called phenotype) for
an individual.
• Genotype--Particular set of genes in a genome (chromosome)
• Phenotype --Observable physical characteristic of the genotype
(E.g.: smart, beautiful, healthy, etc.)
 Individual Representation :
Phenotype and Genotype
• A gene is the GA’s
representation of a single
factor (i.e. a design
parameter), which has a
domain of values
(continuous, discontinuous,
discrete etc.) symbol,
numbering etc.
• In GA, there is a mapping
from genotype to phenotype.
• This eventually decides the
performance (namely speed
and accuracy) of the
problem solving
 Different Encoding Schemes

1. Binary encoding: Representing a gene in terms of bits (0s and 1s).

2. Real value encoding: Representing a gene in terms of values or
symbols or string.
3. Permutation (or Order) encoding: Representing a sequence of
elements)
4. Tree encoding: Representing in the form of a tree of objects.
 Binary Encoding Scheme
• A gene or chromosome is represented by a string (fixed or variable
length) of binary bits (0’s and 1’s)
 Binary Encoding Scheme
• Example 1:
 Binary Encoding Scheme
• Example 2:
 Binary Encoding Scheme
• Merits and Demerits

• Limitations
• Needs an effort to convert into binary from
• Accuracy depends on the binary representation
• Advantages
• Since operations with binary representation is faster, it provide a
faster implementations of all GA operators.
• Any optimization problem has it binary-coded GA implementation
 Real Value Encoding

• The real-coded GA is most suitable for optimization in a

continuous search space.
• Uses the direct representations of the design parameters.
• Avoids any intermediate encoding and decoding steps.
Fitness Evaluation and Selection
Essential Genetic Algorithm Operations

• Encoding
• Fitness Evaluation and Selection
• Mating pool
• Crossover Mutation
• Inversion
• Convergence test
 Genetic Algorithm Selection
• Objective of GA selection
• Perform selection from a set of population,
• Choose the individuals in the population that will create
offspring for the next generation and how many offspring
each will create.
• Identify fittest individuals in the population in hopes that
their offspring will in turn have even higher fitness.
 Fitness Evaluation in GA
• In GA, there is a necessity to create next generation
• The next generation should be such that it is toward the (global)
optimum solution
• Random population generation may not be a wiser strategy
• Better strategy follows the biological process: Selection
• Selection involves:
• Survival of the fittest
• Struggle for the existence
• Fitness evaluation is to evaluate the survivability of each
individual in the current population
 Selection Operation in GA

• Selection is the process for creating the population for next

generation from the current generation.
• Steps to generate new population: Breeding in GA
• Create a mating pool
• Select a pair
• Reproduce
 Fitness Evaluation in GA
How to evaluate the fitness of an individual?
• A simplest strategy could be to take the confidence of the
value(s) of the objective function(s)
• Simple, if there is a single objective function
• But, needs a different treatment if there are two or more objective
functions
• They may be in different scales
• All of them may not be same significant level in the fitness
calculation . . . etc.
Example
 Selection Strategies in Genetic Algorithm
• Canonical selection
• Roulette Wheel selection
• Rank-based selection
• Tournament selection
• Steady-state selection
• Boltzman selection
Canonical Selection
 Canonical Selection
• In an iteration, we calculate fi /F¯ for all individuals in the
current population.
• In Canonical selection, the probability that individuals in the
current population are copied and placed in the mating pool is
proportional to their fitness.

Note :
• Here, the size of the mating pool is p% × N, for some p
• Convergence rate depends on p.
 Roulette-Wheel Selection
• In this scheme, the probability for an individual being selected in
the mating pool is considered to be proportional to its fitness.
• It is implemented with the help of a wheel as shown
Roulette-Wheel Selection Mechanism
Roulette-Wheel Selection Mechanism
Roulette-Wheel Selection Mechanism : An Example
 Roulette-Wheel Selection : Implementation
Input: A Population of size N with their fitness values
Output: A mating pool of size Np
Steps:
 Roulette-Wheel Selection : Example
The probability that i-th individual will be pointed is
 Roulette-Wheel Selection

Does the selection is sensitive to ordering, say in

ascending order of their fitness values?
 Roulette-Wheel Selection : Limitations

• Suppose, there are only four binary string in a population,

whose fitness values are f1, f2, f3 and f4.
• If their values are 80%, 10%, 6% and 4%, respectively.

What is the expected count of selecting f3, f4, f2 or f1?

 Roulette-Wheel Selection : Limitations
The limitations in the Roulette-Wheel selection scheme can be
better illustrated with the following figure.

• The observation is that the individual with higher fitness values will
guard the other to be selected for mating.
• This leads to a lesser diversity and hence fewer scope toward exploring
the alternative solution and also premature convergence or early
convergence with local optimal solution
 Comparing Selection Strategies
• Usually, a selection scheme follows Darwin’s principle of ”Survival
of the fittest”.
• In other words, a selection strategy in GA is a process that favours
the selection of better individuals in the population for the
matting pool (so that better genes are inherited to the new
offspring) and hence search leads to the global optima.

There are two issues to decide the effectiveness of any selection

scheme.
• Population diversity
• Selection pressure
 Effectiveness of Selection Strategies
• Population diversity :
• Similar to the concept of exploration.
• The population diversity means that the genes from the already
discovered good individuals are exploited while permitting the
new area of search space continue to be explored.
• Selection pressure :
• Similar to the concept of exploitation.
• It is defined as the degree to which the better individuals are
favoured.
Crossover Techniques in Genetic Algorithm
Essential Genetic Algorithm Operations

• Encoding
• Fitness Evaluation and Selection
• Mating pool
• Crossover
• Mutation
• Inversion
• Convergence test
 Reproduction Operation in Genetic Algorithm

Reproduction:
• Crossover
• Mutation
• Inversion
Mating Pool: Prior to crossover operation
• A mating pair (each pair consists of two strings) are selected at random.
Thus, if the size of mating pool is N, then N 2 mating pairs are formed.
[Random Mating]
• The pairs are checked, whether they will participate in reproduction or
not by tossing a coin, whose probability being pc. If pc is head, then the
parent will participate in reproduction. Otherwise, they will remain intact
in the population.
 Crossover Operation

Once, a pool of mating pair are selected, they undergo crossover

operations.
1. In crossover, there is an exchange of properties between two parents
and as a result of which two offspring solutions are produced.
2. The crossover point(s) (also called k-point(s)) is(are) decided using a
random number generator generating integer(s) in between 1 and L,
where L is the length of the chromosome.
3. Then we perform exchange of gene values with respect to the k-
point(s)

There are different exchange mechanisms and hence crossover

schemes.
 Crossover Techniques in Binary Coded GA

1. Single point crossover

2. Two-point crossover
3. Multi-point crossover (also called n-point crossover)
4. Uniform crossover (UX)
5. Half-uniform crossover (HUX)
6. Shuffle crossover
7. Matrix crossover (Tow-dimensional crossover)
8. Three parent crossover
 Single Point Crossover

1. Here, we select the K-point lying between 1 and L. Let it be k.

2. A single crossover point at k on both parent’s strings is
selected.
3. All data beyond that point in either string is swapped between
the two parents.
4. The resulting strings are the chromosomes of the offsprings
produced.
Single Point Crossover
 Two Point Crossover

1. In this scheme, we select two different crossover points k1

and k2 lying between 1 and L at random such that k1≠k2.
2. The middle parts are swapped between the two strings.
3. Alternatively, left and right parts also can be swapped
Two Point Crossover
 Multi-Point Crossover
• In case of multi-point crossover, a number of crossover
points are selected along the length of the string, at random.
• The bits lying between alternate pairs of sites are then
swapped.
 Uniform Crossover
• Uniform crossover is a more general version of the multipoint
crossover.
• In this scheme, at each bit position of the parent string, we
toss a coin (with a certain probability ps) to determine whether
there will be swap of the bits or not.
• The two bits are then swapped or remain unaltered,
accordingly
Uniform Crossover
 Uniform Crossover with Crossover Mask

• Here, each gene is created in the offspring by copying the

corresponding gene from one or the other parent chosen
according to a random generated binary crossover mask of the
same length as the chromosome.
• Where there is a 1 in the mask, the gene is copied from the first
parent
• Where there is a 0 in the mask, the gene is copied from the
second parent.
• The reverse is followed to create another offsprings.
Uniform Crossover with Crossover Mask
That’s it !!!!!

Thank you