Genetic Algorithm
An Evolutionary Approach
Genetic Algorithm
Elements of a Genetic Algorithm
⚫ Population Initialization
⚫ Fitness Evaluation:
Elements of a Genetic Algorithm
Problem 1
A cylindrical ‘can’ is to be designed with two parameters —
diameter (d) and height (h). Let us consider that the can
needs to have a volume of at least 300 ml and the objective
of the design is to minimize the cost of ‘can’ material.
Contd … Problem
Corresponding Nonlinear Programming Problem (NLP):
The parameter ‘c’ is the cost of ‘can’ material per squared cm,
and diameter ‘d’ and height ‘h’ are allowed to vary in [dmin,
dmax] and [hmin, hmax] cm, respectively.
Representing a solution
To find the optimal parameter values of ‘d’ and ‘h’ which
satisfies the constraint ‘g1’ and minimizes ‘f’, we first need to
represent the parameter values in binary strings.
Let us assume that we shall use five bits to code each of the
two design parameters ‘d’ and ‘h’, thereby making the overall
string length equal to 10.
The following string represents a can of diameter 8 cm and
height 10 cm:
Contd … Representing a solution
• With five bits to represent a parameter, exactly 32 different
solutions are possible
•Choosing the lower and upper bounds like that allows GAs
to consider only integer values in the range [0, 31].
• However, GAs are not restricted to use only integer values
in the above range, in fact GAs can be assigned to use any
other integer or non-integer values just by changing the string
length and lower and upper bounds:
Where ‘li’ is the string length used to code i-th parameter
and DV(si) is the decoded value of the string si.
Contd … Representing a solution
The above mapping function allows following properties to
achieve in the parameter values:
1. Any arbitrary precision can be achieved in the parameter
values by using along enough string.
2. Different parameters can have different precision by simply
using different string lengths.
3. Parameters are allowed to take positive and negative
values.
Assigning fitness to a solution
• GAs work with strings representing design parameters,
instead of parameters themselves
• Once a string (or a solution) is created by genetic operators,
it is necessary to evaluate the solution, particularly in the
context of the underlying objective and constraint functions
• In the absence of constraints, the fitness of a string is
assigned a value which is a function of the solution’s objective
function value
• In most cases, however, the fitness is made equal to the
objective function value. For example, the fitness of the above
can represented by the10-bit string is
Contd . . . Assigning fitness to a solution
Since the objective of the optimization is to minimize the
objective function, it is to be noted that a solution with a
smaller fitness value compared to another solution is better.
Genetic Algorithm
Initial Population
The figure below shows a random population of six ‘cans’.
The fitness of each ‘can’ is marked on the ‘can’. It is
interesting to note that two solutions do not have 300ml
volume inside and thus have been penalized by adding an
extra artificial cost.
Reproduction or Selection Operator
• The primary objective of the reproduction operator
• To emphasize good solutions and eliminate bad solutions in
a population, while keeping the population size constant
• This is achieved by performing the following tasks:
1. Identify good (usually above-average) solutions in a
population.
2. Make multiple copies of good solutions.
3. Eliminate bad solutions from the population so that multiple
copies of good solutions can be placed in the population.
• There exist a number of ways to achieve the above tasks
• Tournament selection
• Ranking selection etc.
Reproduction or Selection Operator
Reproduction or Selection Operator
Crossover Operator
• Crossover operator is applied next to the strings of the
mating pool
• A little thought will indicate that the reproduction operator
can not create any new solutions in the population
• It only made more copies of good solutions at the expense
of not-so-good solutions
• Creation of new solutions is performed in crossover and
mutation operators.
Contd . . . Crossover operator
• It is true that every crossover between any two solutions from
the new population is not likely to find children solutions better
than parent solutions
• But the chance of creating better solutions is far better than
random
• It is true because parent strings being crossed are not any two
arbitrary random solutions, they have survived during the
reproduction phase
• Thus, they are expected to have some good bit combinations in
their string representations
•Though, every crossover may not create better solutions, but we
do not worry about it too much. If bad solutions are created, they
will get eliminated in the next reproduction operator and hence
will have a short life - Elitism
Mutation
• The need for mutation is to keep diversity in the population
• Figure below shows how a string obtained after
reproduction and crossover operators has been mutated to
another string, representing a slightly different can.
• Once again, the solution obtained is better than that the
original solution. Although, it may not happen all the times
•Mutating a string with a small probability is not a random
operation since the process has a bias for creating a few
solutions in the neighborhood of the original solution