fo

.in
rs
de
SC – GA – Introduction

ea
• Search Optimization Algorithms

yr
.m
w
w
Fig. below shows different types of Search Optimization algorithms.
,w
ty
or
ab

Search
kr
ha

Optimization
C
C
R

Calculus Guided Random Search Enumerative

Based techniques Techniques
Techniques

Indirect Direct
method Uninformed Informed
method
Search Search

Newton Finonacci

Tabu Hill Simulated Evolutionary

Search Climbing Annealing Algorithms

Genetic Genetic
Programming Algorithms

Fig. Taxonomy of Search Optimization techniques

We are interested in evolutionary search algorithms.

Our main concern is to understand the evolutionary algorithms :
- how to describe the process of search,
- how to implement and carry out search,
- what are the elements required to carry out search,
and
- the different search strategies

The Evolutionary Algorithms include :

- Genetic Algorithms and
- Genetic Programming

07
 fo
.in
rs
de
SC – GA - Introduction

ea
1.3 Evolutionary Algorithm (EAs)

yr
.m
w
w
Evolutionary Algorithm (EA) is a subset of Evolutionary Computation (EC) which is
,w
ty
or

a subfield of Artificial Intelligence (AI).

ab
kr
ha
C

Evolutionary Computation (EC) is a general term for several

C
R

computational techniques. Evolutionary Computation represents powerful

search and optimization paradigm influenced by biological mechanisms of
evolution : that of natural selection and genetic.

Evolutionary Algorithms (EAs) refers to Evolutionary Computational models

using randomness and genetic inspired operations. EAs involve selection,
recombination, random variation and competition of the individuals in a
population of adequately represented potential solutions. The candidate
solutions are referred as chromosomes or individuals.

Genetic Algorithms (GAs) represent the main paradigm of Evolutionary

Computation.
-GAs simulate natural evolution, mimicking processes the nature uses :

Selection, Crosses over, Mutation and Accepting.

-GAs simulate the survival of the
fittest among individuals over consecutive generation for
solving a problem.

Development History
EC = GP + ES + EP + GA
Evolutionary Genetic Evolution Evolutionary Genetic
Computing Programming Strategies Programming Algorithms

Rechenberg Koza Rechenberg Fogel Holland

1960 1992 1965 1970
1962
08
 fo
.in
rs
de
SC – GA - Introduction

ea
• Biological Background – Basic Genetics

yr
.m
w
w
‡ Every organism has a set of rules, describing how that organism is built.
,w
ty

All living organisms consist of cells.

or
ab
kr
ha

‡ In each cell there is same set of chromosomes. Chromosomes are

C
C
R

strings of DNA and serve as a model for the whole organism.

‡ A chromosome consists of genes, blocks of DNA.

‡ Each gene encodes a particular protein that represents a trait

(feature), e.g., color of eyes.

‡ Possible settings for a trait (e.g. blue, brown) are called alleles.

‡ Each gene has its own position in the chromosome called its locus.

‡ Complete set of genetic material (all chromosomes) is called a

genome.

‡ Particular set of genes in a genome is called genotype.

‡ The physical expression of the genotype (the organism itself after birth) is
called the phenotype, its physical and mental characteristics, such as eye
color, intelligence etc.
‡ When two organisms mate they share their genes; the resultant offspring
may end up having half the genes from one parent and half from the
other. This process is called recombination (cross over) .

‡ The new created offspring can then be mutated. Mutation means, that
the elements of DNA are a bit changed. This changes are mainly caused
by errors in copying genes from parents.

‡ The fitness of an organism is measured by success of the organism in its

life (survival).

10
 fo
.in
rs
de
SC – GA - Introduction

ea
[ continued from previous slide - Biological background ]

yr
.m
w Below shown, the general scheme of in genetic
w
,w
ty

evolutionary process along with pseudo-code.

or
ab
kr
ha

Parents
C
C

Parents
R

Initialization
Recombination
Population
Mutation
Termination
Offspring
Survivor
Fig. General Scheme of Evolutionary process

Pseudo-Code

BEGIN
INITIALISE population with random candidate solution.

EVALUATE each candidate;

REPEAT UNTIL (termination condition ) is satisfied DO

1. SELECT parents;
2. RECOMBINE pairs of parents;
3. MUTATE the resulting offspring;
4. SELECT individuals or the next generation;
END.
11
 fo
.in
rs
de
SC – GA - Introduction

ea
• Search Space

yr
.m
w
w
In solving problems, some solution will be the best among others. The space
,w
ty
or

of all feasible solutions (among which the desired solution resides) is called
ab
kr

search space (also called state space).

ha
C
C

Each point in the search space represents one possible solution.

R

Each possible solution can be "marked" by its value (or

fitness) for the problem.
The GA looks for the best solution among a number of possible solutions

represented by one point in the search space.

Looking for a solution is then equal to looking for some extreme value

(minimum or maximum) in the search space.

At times the search space may be well defined, but usually only a few points

in the search space are known.

In using GA, the process of finding solutions generates other points (possible
solutions) as evolution proceeds.

12
 fo
.in
rs
de
SC – GA - Introduction

ea
• Working Principles

yr
.m
w
w
Before getting into GAs, it is necessary to explain few terms.
,w
ty
or
ab

Chromosome : a set of genes; a chromosome contains the solution in form of

kr
ha

genes.
C
C
R

Gene : a part of chromosome; a gene contains a part of solution. It

determines the solution. e.g. 16743 is a chromosome and 1, 6, 7, 4 and 3 are

its genes.
Individual : same as chromosome.
Population: number of individuals present with same length of chromosome.

Fitness : the value assigned to an individual based on how far or close a

individual is from the solution; greater the fitness value better
the solution it contains.
Fitness function : a function that assigns fitness value to the individual. It is

problem specific.
Breeding : taking two fit individuals and then intermingling there

chromosome to create new two individuals.

Mutation : changing a random gene in an individual.
Selection : selecting individuals for creating the next generation.

Working principles :
Genetic algorithm begins with a set
of solutions (representedby chromosomes) called the
population.
Solutions from one population are taken and used to form a new population.

This is motivated by the possibility that the new population will be better than
the old one.
Solutions are selected according to their fitness to form new solutions

(offspring); more suitable they are, more chances they have to

reproduce.
This is repeated until some condition (e.g. number of populations or

improvement of the best solution) is satisfied.

13
 SC – GA - Introduction
• Outline of the Basic Genetic Algorithm
1. [Start] Generate random population of n chromosomes (i.e. suitable
solutions for the problem).
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the
population.
3. [New population] Create a new population by repeating following
S teps until the new population is complete.
(a)[Selection] Select two parent chromosomes from a population
according to their fitness (better the fitness, bigger the chance to be
selected)
(b)[Crossover] With a crossover probability, cross over the parents to form
new offspring (children). If no crossover was performed, offspring is the
exact copy of parents.
(c)[Mutation] With a mutation probability, mutate new offspring at
each locus (position in chromosome).
(d) Place new offspring in the new population
4. [Accepting] new generated population for a further run of the
[Replace]
5. Use
algorithm
6. [Test] If the end condition is satisfied, stop, and return the best solution in
current population
[Loop] Go to step 2

Note : The genetic algorithm's performance is largely influenced by two

14
operators called crossover and mutation. These two operators are the most
important parts of GA.
 fo
.in
rs
de
SC – GA – Introduction

ea
• Flow Chart for Genetic Programming

yr
.m
w
w
,w

Start
ty
or
ab
kr
ha

Seed Population
C

Genesis
C

Generate N individuals
R

Scoring : assign fitness

to each individual

Natural Select two individuals

Selection (Parent 1 Parent 2)

No
Reproduction Use crossover operator
Recombination to produce off- springs Crossover

Scoring : assign fitness Crossover

to off- springs Finished?

Yes
Survival of Fittest
Natural Select one off-spring
Apply replacement Yes No
operator to incorporate Selection
new individual into
population
Apply Mutation operator
Mutation to produce Mutated
offspring
No

Terminate?
Mutation Scoring : assign
Finished? fitness to off- spring
Yes

Finish

Fig. Genetic algorithm – program flow chart

15
 fo
.in
rs
de
SC – GA – Encoding

ea
2. Encoding

yr
.m
w
Before a genetic algorithm can be put to work on any problem, a method is needed to
w
,w
ty

encode potential solutions to that problem in a form so that a computer can

or
ab
kr

process.
ha
C

 One common approach is to encode solutions as binary strings: sequences

C
R

of 1's and 0's, where the digit at each position represents some the value of
aspect of the solution.
Example :
A Gene represents some data (eye color, hair color, sight, etc.). A
chromosome is an array of genes. In binary form
a Gene looks like : (11100010)

a Chromosome looks like: Gene1 Gene2 Gene3 Gene4

(11000010, 00001110, 001111010, 10100011)

A chromosome should in some way contain

information about solution
which it represents; it thus requires encoding. The
most popular way of encoding is a binary string
like :
Chromosome 1 : 1101100100110110
Chromosome 2 : 1101111000011110

Each bit in the string represent some

characteristics of the solution.

 There are many other ways of encoding, e.g.,

encoding values as integer or real numbers or
some permutations and so on.
 The virtue of these encoding method depends on
the problem to work on .

16
 fo
.in
rs
de
SC – GA - Encoding

ea
• Binary Encoding

yr
.m
w
w
Binary encoding is the most common to represent information contained. In
,w
ty
or

genetic algorithms, it was first used because of its relative simplicity.

ab
kr
ha
C

In binary encoding, every chromosome is a string of bits : 0 or 1, like

C
R

Chromosome 1: 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1
Chromosome 2: 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1

 Binary encoding gives many possible chromosomes even with a small

number of alleles ie possible settings for a trait (features).

 This encoding is often not natural for many problems and sometimes

corrections must be made after crossover and/or mutation.

Example 1:

One variable function, say 0 to 15 numbers, numeric values,

represented by 4 bit binary string.

Numeric 4–bit Numeric 4–bit Numeric 4–bit

value string value string value string

0 0000 6 0110 12 1100

1 0001 7 0111 13 1101
2 0010 8 1000 14 1110
3 0011 9 1001 15 1111
4 0100 10 1010
5 0101 11 1011

17
 fo
.in
rs
de
SC – GA – Encoding

ea
[ continued binary encoding ]

yr
.m
w
w Example 2 :
,w

Two variable function represented by 4 bit string for each variable.

ty
or
ab

Let two variables X1 , X2 as (1011 0110) .

kr
ha
C

Every variable will have both upper and lower limits as L  Xi U

C

Xi Xi
R


Because 4-bit string can represent integers from 0 to 15,
so (0000 0000) and (1111 1111) represent the points for X1 , X2 as

( X L , L ) and U
( X1 , X
U
2
) respectively.
1 X 2

Thus, an n-bit string can represent integers from

0 to 2n -1, i.e. 2n integers.
Binary Coding Equivalent integer Decoded binary substring
Let Xi is coded as a substring
2 10 Remainder
1 0 1 0
2 5 Si of length ni. Then decoded
0
0 x 20 = 0
2 2 1 binary substring Si is as
1 x 21 = 2
1 0 K=ni - 1
0 x 22 = 0

1 x 23 = 8
 2 k Sk
k=0
10
where Si can be 0 or 1 and the
string S is represented as

Sn-1 . . . . S3 S2 S1 S0

Example : Decoding value Consider a 4-bit string (0111),

the decoded value is equal to

23 x 0 + 22 x 1 + 21 x 1 + 20 x 1 = 7
Knowing L
and U
corresponding to (0000) and (1111) ,
X X
i i

the equivalent value for any 4-bit string can be obtained as

(X U − Xi
L
)
i
Xi L + --------------- x (decoded value of string)
=X i
( 2ni − 1 )

 For e.g. a variable Xi ; let L = 2 , and X

U
= 17, find what value the
Xi i

4-bit string Xi = (1010) would represent. First get decoded value for
Si = 1010 = 23 x 1 + 22 x 0 + 21 x 1 + 20 x 0 = 10 then
(17 -2)
Xi = 2 + ----------- x 10 = 12
(24 - 1)

The accuracy obtained with a 4-bit code is 1/16 of search space.

By increasing the string length by 1-bit , accuracy increases to 1/32.
18
 fo
.in
rs
de
SC – GA – Encoding

ea
• Value Encoding

yr
.m
w
w
The Value encoding can be used in problems where values such as real
,w
ty
or

numbers are used. Use of binary encoding for this type of problems would be
ab
kr
ha

difficult.
C
C
R

1. In value encoding, every chromosome is a sequence of some values.

2. The Values can be anything connected to the problem, such as : real

numbers, characters or objects.

Examples :
Chromosome A 1.2324 5.3243 0.4556 2.3293 2.4545

Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT

Chromosome C (back), (back), (right), (forward), (left)

3. Value encoding is often necessary to develop some new types of

crossovers and mutations specific for the problem.

19
 fo
.in
rs
de
SC – GA – Encoding

ea
• Permutation Encoding

yr
.m
w
w
Permutation encoding can be used in ordering problems, such as traveling
,w
ty
or

salesman problem or task ordering problem.

ab
kr
ha

1. In permutation encoding, every chromosome is a string of numbers

C
C
R

that represent a position 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

2. Permutation encoding is useful for ordering problems. For some

problems, crossover and mutation corrections must be made to leave the
chromosome consistent.

Examples :

1. The Traveling Salesman problem:

There are cities and given distances between them. Traveling salesman
has to visit all of them, but he does not want to travel more than
necessary. Find a sequence of cities with a minimal traveled distance.
Here, encoded chromosomes describe the order of cities the salesman
visits.

2. The Eight Queens problem :

There are eight queens. Find a way to place them on a chess board so
that no two queens attack each other. Here, encoding describes the
position of a queen on each row.

20
 fo
.in
rs
de
SC – GA - Encoding

ea
• Tree Encoding

yr
.m
w
w
Tree encoding is used mainly for evolving programs or expressions. For
,w
ty
or

genetic programming :
ab
kr

In tree encoding, every chromosome is a tree of some objects, such as

ha
C
C
R

functions or commands in programming language.

Tree encoding is useful for evolving programs or any other structures that can

be encoded in trees.
The crossover and mutation can be done relatively easy way .

Example :

Chromosome A Chromosome B

+
do untill

x /
step wall

5 y

(+ x(/ 5y)) ( do until step wall )

Fig. Example of Chromosomes with tree encoding

Note : Tree encoding is good for evolving programs. The

programming language LISP is often used. Programs in LISP can be
easily parsed as a tree, so the crossover and mutation is relatively
easy.
21
 fo
.in
rs
de
SC – GA - Operators

ea
3. Operators of Genetic Algorithm

yr
.m
w
w
Genetic operators used in genetic algorithms maintain genetic
,w
ty
or

diversity. diversity or variation is a necessity for the process of evolution.

ab
kr
ha

Genetic operators are analogous to those which occur in the natural world:
C
C

 Reproduction (or Selection) ;

R

 Crossover (or Recombination); and

Genetic
 Mutation.

In addition to these operators, there are some parameters of GA. One important
parameter is Population size.

 Population size says how many chromosomes are in population (in one

generation).

 If there are only few chromosomes, then GA would have a few possibilities to

perform crossover and only a small part of search space is explored.

 If there are many chromosomes, then GA slows down.

 Research shows that after some limit, it is not useful to increase population

size, because it does not help in solving the problem faster. The population size
depends on the type of encoding and the problem.

22
 fo
.in
rs
de
SC – GA – Operators

ea
3.1 Reproduction, or Selection

yr
.m
w
w
Reproduction is usually the first operator applied on population. From the
,w
ty
or

population, the chromosomes are selected to be parents to crossover and produce

ab
kr

offspring.
ha
C
C
R

The problem is how to select these chromosomes ?

According to Darwin's evolution theory "survival of the fittest" – the best ones
should survive and create new offspring.

The Reproduction operators are also called Selection operators.

Selection means extract a subset of genes from an existing population, according

to any definition of quality. Every gene has a meaning, so

one can derive from the gene a kind of quality measurement called fitness

function. Following this quality (fitness value), selection can be performed.

Fitness function quantifies the optimality of a solution (chromosome) so that a

particular solution may be ranked against all the other solutions.

The function depicts the closeness of a given ‘solution’ to the desired result.

Many reproduction operators exists and they all essentially do same thing. They
pick from current population the strings of above average and insert their multiple
copies in the mating pool in a probabilistic manner.

The most commonly used methods of selecting chromosomes for parents to

crossover are :

 Roulette wheel selection,  Rank selection

 Boltzmann selection,  Steady state selection.

 Tournament selection,

The Roulette wheel and Boltzmann selections methods are illustrated next.
23
 fo
.in
rs
de
SC – GA – Operators

ea
• Example of Selection

yr
.m
w
w
,w

Evolutionary Algorithms is to maximize the function f(x) = x2 with x in the

ty
or

integer interval [0 , 31], i.e., x = 0, 1, . . . 30, 31.

ab
kr
ha
C

[Link] first step is encoding of chromosomes; use binary representation for

C
R

integers; 5-bits are used to represent integers up to 31.

[Link] that the population size is 4.

[Link] initial population at

random. They are chromosomes or genotypes; e.g., 01101, 11000, 01000,
10011.

[Link] fitness value for each individual.

(a) Decode the individual into an integer (called phenotypes),
01101  13; 11000  24; 01000  8; 10011  19;

(b) Evaluate the fitness according to f(x) = x2 ,

13  169; 24  576; 8  64; 19  361.

[Link] parents (two individuals) for crossover based on their fitness in pi.
Out of many methods for selecting the best
n
in the population is
chromosomes, pi = F i / (if  Fj) , where
j=1
roulette-wheel selection is used, then the probability of the i th string
F i is fitness for the string i in the population, expressed as f(x) pi is

probability of the string i being selected,

n is no of individuals in the population, is population size,

n=4 n * pi is expected count

String No Initial X value Fitness Fi p i Expected count

Population f(x) = x2 N * Prob i

1 01101 13 169 0.14 0.58

2 11000 24 576 0.49 1.97
3 01000 8 64 0.06 0.22
4 10011 19 361 0.31 1.23
Sum 1170 1.00 4.00
Average 293 0.25 1.00
Max 576 0.49 1.97

The string no 2 has maximum chance of selection.

24
 fo
.in
rs
de
SC – GA – Operators

ea
• Roulette wheel selection (Fitness-Proportionate Selection)

yr
.m
w
w
,w

Roulette-wheel selection, also known as Fitness Proportionate Selection, is a

ty
or

genetic operator, used for selecting potentially useful solutions for

ab
kr
ha

recombination.
C
C
R

In fitness-proportionate selection :
the chance of an individual's being selected is proportional to its fitness,

greater or less than its competitors' fitness.

conceptually, this can be thought as a game of Roulette.

The Roulette-wheel simulates 8

1
5% 2 individuals with fitness values
8 Fi,
20% 9%
marked at its circumference; e.g.,

3  the 5th individual a higher

13% has
7 fitness than others, so the wheel
8%
would choose the 5th individual

6 more than other individuals .

8%  the
17% fitness of the individuals is
4 calculated as the wheel is spun n = 8
20%
times, each time selecting
5
an instance, of the string, chosen by
Fig. Roulette-wheel
Shows 8 individual the wheel pointer.
with fitness
n
Probability of i th string is pi = F i / (  F j ) , where
j=1
n = no of individuals, called population size; pi = probability of ith
string being selected; Fi = fitness for ith string in the population.
Because the circumference of the wheel is marked according to a
string's fitness, the Roulette-wheel mechanism is expected to
F
make copies of the ith string.
F

Average fitness = F Fj/n ; Expected count = (n =8 ) x pi

N=5

Cumulative Probability5 =  pi
i=1

25
 fo
.in
rs
de
SC – GA – Operators

ea
• Boltzmann Selection

yr
.m
w
w
Simulated annealing is a method used to minimize or maximize a function.
,w
ty
or
ab

This method simulates the process of slow cooling of molten metal to achieve
kr
ha
C

the minimum function value in a minimization problem.

C
R

The cooling phenomena is simulated by controlling a temperature like

parameter introduced with the concept of Boltzmann probability distribution.

The system in thermal equilibrium at a temperature T has its energy

distribution based on the probability defined by

P(E) = exp ( - E / kT ) were k is Boltzmann constant.

This expression suggests that a system at a higher temperature has almost

uniform probability at any energy state, but at lower temperature it has a

small probability of being at a higher energy state.

Thus, by controlling the temperature T and assuming that the search process

follows Boltzmann probability distribution, the convergence of the algorithm

is controlled.

26
 fo
.in
rs
de
SC – GA – Operators

ea
2. Crossover

yr
.m
w
w
Crossover is a genetic operator that combines (mates) two chromosomes
,w
ty
or

(parents) to produce a new chromosome (offspring). The idea behind

ab
kr
ha

crossover is that the new chromosome may be better than both of the
C
C
R

parents if it takes the best characteristics from each of the parents. Crossover
occurs during evolution according to a user-definable crossover probability.
Crossover selects genes from parent chromosomes and creates a new
offspring.

The Crossover operators are of many types.

 one simple way is, One-Point crossover.

 the others are Two Point, Uniform, Arithmetic, and Heuristic crossovers.

The operators are selected based on the way chromosomes are encoded.

27
x2 example: selection
X2 example: crossover
X2 example: mutation
 fo
.in
rs
de
SC – GA – Operators

ea
• One-Point Crossover

yr
.m
w
w
One-Point crossover operator randomly selects one crossover point and then
,w
ty
or

copy everything before this point from the first parent and then everything
ab
kr
ha

after the crossover point copy from the second parent. The Crossover would
C
C
R

then look as shown below.

Consider the two parents selected for crossover.

Parent 1 11011|00100110110
Parent 2 11011|11000011110

Interchanging the parents chromosomes after the crossover points - The

Offspring produced are :

Offspring 1 11011 |1100001111 0

Offspring 2 11011 |0010011011 0

Note : The symbol, a vertical line, | is the chosen crossover point.

28
 fo
.in
rs
de
SC – GA – Operators

ea
• Two-Point Crossover

yr
.m
w
w
Two-Point crossover operator randomly selects two crossover points within a
,w
ty
or

chromosome then interchanges the two parent chromosomes between these

ab
kr
ha

points to produce two new offspring.

C
C
R

Consider the two parents selected for crossover :

Parent 1 11011|0010011|011 0
Parent 2 11011|1100001|111 0

Interchanging the parents chromosomes between the crossover points - The

Offspring produced are :

Offspring 1 11011 |001001 1 |0110

Offspring 2 11011 |001001 1 |0110

29
 fo
.in
rs
de
SC – GA – Operators

ea
• Uniform Crossover

yr
.m
w
w
Uniform crossover operator decides (with some probability – know as the
,w
ty
or

mixing ratio) which parent will contribute how the gene values in the
ab
kr
ha

offspring chromosomes. The crossover operator allows the parent

C
C
R

chromosomes to be mixed at the gene level rather than the segment level (as
with one and two point crossover).

Consider the two parents selected for crossover.

Parent 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0
Parent 2 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0

If the mixing ratio is 0.5 approximately, then half of the genes in the offspring
will come from parent 1 and other half will come from parent 2. The possible
set of offspring after uniform crossover would be:

Offspring 1 11 12 02 11 11 12 12 02 01 01 02 11 12 11 11 02
Offspring 2 12 11 01 12 12 01 01 11 02 02 11 12 01 12 12 01

Note: The subscripts indicate which parent the gene came from.
30
 fo
.in
rs
de
SC – GA – Operators

ea
• Arithmetic

yr
.m
w
w
Arithmetic crossover operator linearly combines two parent chromosome
,w
ty
or

vectors to produce two new offspring according to the equations:

ab
kr
ha

Offspring1 = a Parent1 + (1- a) Parent2 Offspring2 = (1 – a) Parent1 + a Parent2

C

* * * *
C
R

where a is a random weighting factor chosen before each crossover

operation.

Consider two parents (each of 4 float genes) selected for crossover:

Parent 1 (0.3) (1.4) (0.2) (7.4)

Parent 2 (0.5) (4.5) (0.1) (5.6)

Applying the above two equations and assuming the

weighting factor a = 0.7, applying above equations, we get two resulting
offspring. The possible set of offspring after arithmetic crossover would be:

Offspring 1 (0.36) (2.33) (0.17) (6.87)

Offspring 2 (0.402) (2.981) (0.149) (5.842)

31
 fo
.in
rs
de
SC – GA – Operators

ea
• Heuristic

yr
.m
w
w
Heuristic crossover operator uses the fitness values of the two parent
,w
ty
or

chromosomes to determine the direction of the search.

ab
kr
ha
C

The offspring are created according to the equations:

C
R

Offspring1 = BestParent + r * (BestParent − WorstParent)

Offspring2 = BestParent
where r is a random number between 0 and 1.

It is possible that offspring1 will not be feasible. It can happen if r is chosen

such that one or more of its genes fall outside of the allowable upper or lower
bounds. For this reason, heuristic crossover has a user defined parameter n
for the number of times to try and find an r that results in a feasible
chromosome. If a feasible chromosome is not produced after n tries, the
worst parent is returned as offspring1.

32
 fo
.in
rs
de
SC – GA – Operators

ea
3.3 Mutation

yr
.m
w
w
After a crossover is performed, mutation takes place.
,w
ty
or

Mutation is a genetic operator used to maintain genetic diversity from one

ab
kr
ha

generation of a population of chromosomes to the next.

C
C
R

Mutation occurs during evolution according to a user-definable mutation

probability, usually set to fairly low value, say 0.01 a good first choice.

Mutation alters one or more gene values in a chromosome from its initial state.
This can result in entirely new gene values being added to the gene pool. With the
new gene values, the genetic algorithm may be able to arrive at better solution
than was previously possible.

Mutation is an important part of the genetic search, helps to prevent the

population from stagnating at any local optima. Mutation is intended to prevent
the search falling into a local optimum of the state space.

The Mutation operators are of many type.

one simple way is, Flip Bit.

the others are Boundary, Non-Uniform, Uniform, and Gaussian.

The operators are selected based on the way chromosomes are encoded .

33
 fo
.in
rs
de
SC – GA - Operators

ea
• Flip Bit

yr
.m
w
w
The mutation operator simply inverts the value of the chosen gene.
,w
ty
or

i.e. 0 goes to 1 1 goes to 0.

ab
kr
ha

and This can only be used for binary genes.

C
C
R

mutation operator
Consider the two original off-springs selected for mutation.

Original offspring 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0
Original offspring 2 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0

Invert the value of the chosen gene as 0 to 1 and 1 to 0

The Mutated Off-spring produced are :

Mutated offspring 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 0
Mutated offspring 2 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0

34
 fo
.in
rs
de
SC – GA - Operators

ea
• Boundary

yr
.m
w The mutation operator replaces the value of the chosen gene with either the
w
,w
ty

upper or lower bound for that gene (chosen randomly).

or
ab
kr

This mutation operator can only be used for integer and float genes.
ha
C
C
R

• Non-Uniform
The mutation operator increases the probability such that the amount of the
mutation will be close to 0 as the generation number increases. This mutation
operator prevents the population from stagnating in the early stages of the
evolution then allows the genetic algorithm to fine tune the solution in the
later stages of evolution.
This mutation operator can only be used for integer and float genes.

• Uniform
The mutation operator replaces the value of the chosen gene with a uniform
random value selected between the user-specified upper and lower bounds
for that gene.
This mutation operator can only be used for integer and float genes.

• Gaussian
The mutation operator adds a unit Gaussian distributed random value to the
chosen gene. The new gene value is clipped if it falls outside of the user-
specified lower or upper bounds for that gene.
This mutation operator can only be used for integer and float genes.

35
 fo
.in
rs
de
SC – GA – Examples

ea
4. Basic Genetic Algorithm :

yr
.m
w
w
Examples to demonstrate and explain : Random population, Fitness, Selection,
,w
ty
or

Crossover, Mutation, and Accepting.

ab
kr
ha

•
C

Example 1 :
C
R

Maximize the function f(x) = x2 over the range of integers from 0 . . . 31.

Note : This function could be solved by a variety of traditional methods such

as a hill-climbing algorithm which uses the derivative.
One way is to :
 Start from any integer x in the domain of f
 Evaluate at this point x the derivative f’
 Observing that the derivative is +ve, pick a new x which is at a small distance in
the +ve direction from current x
 Repeat until x = 31

See, how a genetic algorithm would approach this problem ?

36
 fo
.in
rs
de
SC – GA – Examples

ea
[ continued from previous slide ]

yr
.m
w Genetic Algorithm Approach to problem - Maximize the function f(x) = x2
w
,w
ty
or

1. Devise a means to represent a solution to the problem :

ab
kr
ha

Assume, we represent x with five-digit unsigned binary integers. Devise a

C
C

2. heuristic for evaluating the fitness of any particular solution : The function
R

f(x) is simple, so it is easy to use the f(x) value itself to rate the fitness of a
solution; else we might have considered a more simpler heuristic that would
more or less serve the same purpose.
3. Coding - Binary and the String length :

GAs often process binary representations of solutions. This works well, because
crossover and mutation can be clearly defined for binary solutions. A Binary string
of length 5 can represents 32 numbers (0 to 31).
4. Randomly generate a set of solutions :

Here, considered a population of four solutions. However, larger populations are

used in real applications to explore a larger part of the search. Assume, four
randomly generated solutions as : 01101, 11000, 01000, 10011. These are
chromosomes or genotypes.
5. Evaluate the fitness of each member of the population :

The calculated fitness values for each individual are -

(a)Decode the individual into an integer (called phenotypes),
01101  13; 11000  24; 01000  8; 10011  19;

(b)Evaluate the fitness according to f(x) = x 2 ,

13  169; 24  576; 8 19  361.
64;
N is the number of
(c) Expected count = N * Prob i , where
individuals in the population called population size, here N = 4.
Thus the evaluation of the initial population summarized in table below .

String No i Initial X value Fitness Prob i Expected count

Population (Pheno f(x) = x2 (fraction N * Prob i
(chromosome) types) of total)
1 0 1 1 0 1 13 169 0.14 0.58
2 1 1 0 0 0 24 576 0.49 1.97
3 0 1 0 0 0 8 64 0.06 0.22
4 1 0 0 1 1 19 361 0.31 1.23
Total (sum) 1170 1.00 4.00
Average 293 0.25 1.00
Max 576 0.49 1.97

Thus, the string no 2 has maximum chance of selection.

37
 fo
.in
rs
de
SC – GA – Examples

ea
6. Produce a new

yr
.m
generation of
w
w
solutions by
,w

picking from the

ty
or

existing
ab
kr
ha

pool of solutions
C
C
R

Strings Prob i Associated Bin with a preference

01101 0.14 0.0 ... for solutions which

0.14
11000 0.49 0.14 ...
are better suited
0.63
than others:
01000 0.06 0.63 ...
0.69 Webin
divide
By generating 4 uniform (0, 1) random values and seeing which theythe
fallrange
into
10011 0.31 0.69 ...
into four bins, sized
1.00for the next generation.
we pick the four strings that will form the basis
Random No Falls into bin Chosen string according to the
relative fitness of
0.08 0.0 . . . 0.14 0 1 1 0 1
0.24 0.14 . . . 0.63 1 1 0 0 0 the solutions which
0.52 0.14 . . . 0.63 1 1 0 0 0
0.87 0.69 . . . 1.00 1 0 0 1 1 they represent.

7. Randomly pair the members of the new generation

Random number generator decides for us to mate the first two strings together
and the second two strings together.

8. Within each pair swap parts of the members solutions to create offspring

which are a mixture of the parents :

For the first pair of strings: 011 01 ,11000
 We randomly select the crossover point to be after the fourth digit. Crossing

these two strings at that point yields:

01101  0 1 1 0 |1  01100

1100 0  1 1 0 0 |0  11
001
110 00 , 10011
For the second pair of strings:
 We randomly select the crossover point to be after the second digit. Crossing

these two strings at that point yields:

11000 1 1 |0 0 0  11011


10011 1 0 |0 1 1  10000

38
 fo
.in
rs
de
SC – GA – Examples

ea
9. Randomly mutate

yr
.m
a very small
w
w
fraction of genes in
,w

the population :
ty
or
ab

With a typical
kr
ha

10. Go back and re-evaluate fitness of the population (new generation) : This
C

mutation probability
C
R

would be the first step in generating a new generation of solutions.

of per However it is
bit it happens
also useful in showing the way that a single iteration of the genetic algorithm
that none of the has
bits
improved this sample. in our population are
String No Initial X value Fitness Prob i Expected count
Population (Pheno f(x) = x2 (fraction mutated.
(chromosome) types) of total)
1 0 1 1 0 0 12 144 0.082 0.328
2 1 1 0 0 1 25 625 0.356 1.424
3 1 1 0 1 1 27 729 0.415 1.660
4 1 0 0 0 0 16 256 0.145 0.580
Total (sum) 1754 1.000 4.000
Average 439 0.250 1.000
Max 729 0.415 1.660

Observe that :
[Link] populations : At start step 5 were
01101, 11000, 01000,10011

After one cycle, new populations, at step 10 to act as initial population

01100, 11001, 1 1 0 11 , 10000

[Link] total fitness has gone from 1170 to 1754 in a single generation.

[Link] algorithm has already come up with the string 11011 (i.e x = 27) as a
possible solution.

39
 fo
.in
rs
de
SC – GA – Examples

ea
• Example 2 : Two bar pendulum

yr
.m
w
w
Two uniform bars are connected by pins at A and B and supported force
,w
ty
or

at A. Let a horizontal P acts at C.

ab
kr
ha

A Given : Force P = 2, Length of bars ℓ1 = 2 ,

C

y ℓ2 = 2, Bar weights W1= 2, W2 = 2 . angles = Xi

C
R

ℓ1
1 Find : Equilibrium configuration of the system if fiction at
B all joints are neglected ?
ℓ2 C
2
P Solution : Since there are two unknowns 1 and
2 , we use 4 – bit binary for each unknown.
W1
XU - XL 90 - 0
W2 Accuracy = ----------- = --------- = 60
24 - 1 15
Fig. Two bar pendulum
Hence, the binary coding and the corresponding angles Xi are given as
XiU - XiL
th
Xi = XiL + ----------- Si where Si is decoded Value of the i
chromosome.
2 - 1
4
e.g. the 6th chromosome binary code (0 1 0 1) would have the corresponding
angle given by Si = 0 1 0 1 = 23 x 0 + 22 x 1 + 21 x 0 + 20 x 1 = 5
90 - 0
Xi = 0 + ----------- x 5 = 30
15
The binary coding and the angles are given in the table below.

S. No. Binary code Angle S. No. Binary code Angle

Si Xi Si Xi
1 0000 0 9 1 0 0 0 48
2 0001 6 10 1 0 0 1 54
3 0010 12 11 1 0 1 0 60
4 0011 18 12 1 0 1 1 66
5 0100 24 13 1 1 0 0 72
6 0101 30 14 1 1 0 1 78
7 0110 36 15 1 1 1 0 84
8 0111 42 16 1 1 1 1 90

Note : The total potential for two bar pendulum is written as

∏ = - P[(ℓ1 sin1 + ℓ2 sin2 )] - (W1 ℓ1 /2)cos1 - W2 [(ℓ2 /2) cos2 + ℓ1 cos1] (Eq.1)

Substituting the values for P, W1 ,

W 2 , ℓ1 ,
ℓ2 all as 2 , we get ,

∏ (1 , 2 ) = - 4 sin1 - 6 cos1 - 4 sin2 - 2 cos2 = function f (Eq. 2)

1 , 2 lies between 0 and 90 both inclusive ie
0 ≤ 1 , 2 ≤
90 (Eq. 3)

Equilibrium configuration is the one which makes ∏ a minimum .

Since the objective function is –ve , instead of minimizing the function f let us
Hence the fitness
maximize function F is given by
-f = f ’ .
F= –f–7= f’ –7 ([Link]
4)
48
maximum value of f ’ = 8 when 1 and 2 are zero.
 fo
.in
rs
de
SC – GA - Examples

ea
[ continued from previous slide ]

yr
.m
w First randomly generate 8 population with 8 bit strings as shown in table below.
w
,w
ty

Population Population of 8 bit strings Corresponding Angles F=–f–7

or

No. (Randomly generated) (from table above)

ab
kr

1 ,
ha

2
C
C

1 0 0 0 0 0 0 0 0 0 0 1
R

2 0 0 1 0 0 0 0 0 12 6 2.1
3 0 0 0 1 0 0 0 0 6 30 3.11
4 0 0 1 0 1 0 0 0 12 48 4.01
5 0 1 1 0 1 0 1 0 36 60 4.66
6 1 1 1 0 1 0 0 0 84 48 1.91
7 1 1 1 0 1 1 0 1 84 78 1.93
8 0 1 1 1 1 1 0 0 42 72 4.55
These angles and the corresponding to fitness function are shown below.

F=1 F=2.1 F=3.11

F=3.11

1=0 1=12 1=6 1=12

2=0 2=6 2=30 2=48

F=4.6 F=1.91 F=1.93 F=4.55

1=36 1=84 1=84 1=42

2=60 2=48 2=78 2=72

Fig. Fitness function F for various

population

The above Table and the Fig. illustrates that :

 GA begins with a population of random strings.
 Then, each string is evaluated to find the fitness value.
 The population is then operated by three operators –
Reproduction , Crossover and Mutation, to create new population.
 The new population is further evaluated tested for termination.
 If the termination criteria are not met, the population is iteratively
operated by the three operators and evaluated until the termination
criteria are met.
 One cycle of these operation and the subsequent
evaluation procedure is known as a Generation in GA terminology.
49
 fo
.in
rs
de
Sc – GA – References

ea
5. References : Textbooks

yr
.m
w
w
1. "Genetic Algorithms in Search, Optimization, and Machine Learning", by David E.
,w

Goldberg, (1989), Addison-Wesley, Chapter 1-8, page 1- 432.

ty
or
ab

2. "An Introduction to Genetic Algorithms", by Melanie Mitchell, (1998), MIT Press,

kr

Chapter 1- 6,
ha

page 1- 203,
C
C
R

3. "Genetic Algorithms: Concepts And Designs", by K. F. Man, K. S. and Tang, S. Kwong,

(201), Springer, Chapter 1- 10, page 1- 348,

4. "Genetic algorithms and engineering design", by Mitsuo Gen, and Runwei Cheng,
(1997), John Wiley & Sons Inc, chapter 1- 10, page 1-411.

5. "Practical genetic algorithms", by Randy L. Haupt, (2004), John Wiley & Sons Inc,
Chapter 1- 7, page 1- 251.

6. Related documents from open source, mainly internet. An exhaustive list is being
prepared for inclusion at a later date.

42