Genetic Algorithms

Source
1. Presentation of Dr. Chhavi
Kashyap
2. Presentation of Dr. Son
Kuswadi
3. Others

1
Heuristic Approach
 A technique designed for solving a problem quicker
when classic methods are too slow.
 It can quickly produce a solution that is good enough for
solving the problem at hand, as opposed to finding
exact solution in a prohibitively long time.
 Bio-inspired heuristic approach:
 Genetic Algorithm (GA)
 Particle Swarm Optimization (PSO)
 Ant Colony Optimization (ACO)
 Bee Colony Optimization (BCO)
 ….
 Introduction To
Genetic Algorithms
(GAs)

3
What Are Genetic
Algorithms (GAs)?

Genetic Algorithms are search and

optimization techniques based on Darwin’s
Principle of Natural Selection.

4
Darwin’s Principle Of Natural
Selection
 IF there are organisms that reproduce, and
 IF offsprings inherit traits (genetically determined
characteristics) from their progenitors (ancestors or
parents), and
 IF there is variability of traits, and
 IF the environment cannot support all members of a
growing population,
 THEN those members of the population with less-
adaptive traits (determined by the environment) will die
out, and
 THEN those members with more-adaptive traits
(determined by the environment) will thrive.

5
 Basic Idea Of Principle Of
Natural Selection

“Select The Best, Discard The Rest”

6
 An Example of Natural
 Selection
Giraffes have long necks.
Giraffes with slightly longer necks could feed on leaves of higher
branches when all lower ones had been eaten off.
 They had a better chance of survival.
 Favorable behaviors propagated through generations of
giraffes.
 Now, evolved species has long necks.

NOTE: Longer necks may have been a deviant characteristic

(mutation) initially but since it was favorable, was propagated over
generations.

So, some mutations are beneficial.

7
Evolution Through Natural
InitialSelection
Population Of Animals

Struggle For Existence-Survival Of the Fittest

Surviving Individuals Reproduce, Propagate Favorable

Characteristics

Millions Of Years

Evolved Species
(Favorable Characteristic Now A Trait Of Species)

8
 Genetic Algorithms Implement
Optimization Strategies By Simulating
Evolution Of Species Through Natural
Selection.

9
Working Mechanism Of GAs
Begin

Initialize
population

Evaluate
Solutions

T =0

Optimum N
Solution?

Selection
Y

T=T+1 Stop Crossover

Mutation

10
The Cycle of Evolution

11
 Simple Genetic Algorithm
Simple_Genetic_Algorithm()
{
Initialize the Population;
Calculate Fitness Function;

While(Fitness Value != Optimal Value)

{
Selection;//Natural Selection, Survival Of
Fittest
Crossover;//Reproduction, Propagate
favorable characteristics

Mutation;//Mutation
Calculate Fitness Function;
}
}

12
 Nature to Computer
Mapping

Nature Computer

Population Set of solutions.

Individual Solution to a problem.
Fitness Quality of a solution.
Chromosome Encoding for a Solution.
Gene Part of the encoding of a solution.
Reproduction Crossover

13
GA Operators and
Parameters

14
Genetic Algorithm

 Encoding
 Selection
 Crossover
 Mutation

15
 Encoding
The process of representing the solution in the
form of a string that conveys the necessary
information.

Just as in a chromosome, each gene controls a particular

characteristic of the individual, similarly, each bit in the string
represents a characteristic of the solution.

 Binary encoding
 Permutation encoding
 Value encoding
 Tree encoding
 ….
16
 Encoding Methods
 Binary Encoding – Most common method of
encoding. Chromosomes are strings of 1s and 0s and
each position in the chromosome represents a particular
characteristic of the problem.

Chromosome A 10110010110011100101
Chromosome B 11111110000000011111

Example of Problem: Knapsack problem

The problem: There are things with given value and size. The knapsack has
given capacity. Select things to maximize the value of things in knapsack,
but do not extend knapsack capacity.
Encoding: Each bit says, whether the corresponding thing is in knapsack.

17
Encoding Methods (contd.)
 Permutation Encoding– Useful in ordering
problems such as the Traveling Salesman Problem
(TSP). Example. In TSP, every chromosome is a string
of numbers, each of which represents a city to be
visited.

Chromosome A 1 5 3 2 6 4 7 9 8
Chromosome B 8 5 6 7 2 3 1 4 9

18
Encoding Methods (contd.)
 Value Encoding – Used in problems where
complicated values, such as real numbers, are used and
where binary encoding would not suffice.
Good for some problems, but often necessary to develop
some specific crossover and mutation techniques for
these chromosomes.

Chromosome A 1.235 5.323 0.454 2.321 2.454

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

19
 Fitness Function
A fitness function quantifies the optimality of a
solution (chromosome) so that particular solution
may be ranked against all the other solutions.
 A fitness value is assigned to each solution depending
on how close it actually is to solving the problem.

 Ideal fitness function correlates closely to goal + quickly

computable.

 Example. In TSP, f(x) is sum of distances between the

cities in solution. The lesser the value, the fitter the
solution is.

20
Selection
 After deciding on an encoding, the next step
is to decide how to perform selection.
 That means how to choose individuals in
the population that will create offspring for the
next generation.
 The purpose of selection is to emphasize
fitter individuals in the population in hopes
that their off springs have better fitness.

21
 Selection
The process that determines which solutions are
to be preserved and allowed to reproduce and
which ones deserve to die out.

 The primary objective is to emphasize the good solutions

and eliminate the bad solutions in a population, while
keeping the population size constant.

 “Selects The Best, Discards The Rest”.

22
 Selection

 Identify the good solutions in a population.

 Make multiple solutions from the good

solutions.

 Eliminate bad solutions from the population

so that multiple copies of good solutions
can be placed in the population.

23
Selection Methods

 Roulette Wheel Selection

 Rank Selection
 Tournament Selection
 ….

24
Roulette Wheel Selection

 Parents are selected according to their

fitness.
 The better the chromosomes are, the more
chances to be selected they have.

25
 Roulette Wheel Selection
 Each current string in the population has a slot assigned
to it which is in proportion to it’s fitness.

 We spin the weighted roulette wheel thus defined n

times (where n is the total number of solutions).

 Each time Roulette Wheel stops, the string

corresponding to that slot is created.

Strings that are fitter are assigned a larger slot and

hence have a better chance of appearing in the new
population.

26
Example Of Roulette Wheel
Selection
No. String Fitness % Of Total

1 01101 169 14.4

2 11000 576 49.2

3 01000 64 5.5

10011 361 30.9

4
Total 1170 100.0

27
Roulette Wheel For
Example

28
Roulette Wheel Selection
 Imagine a roulette wheel where all chromosomes in the
population are placed, each cromosome has its place big
accordingly to its fitness function, like on the following
picture.

Then a marble is thrown there and selects the chromosome. Chromosome

with bigger fitness will be selected more times.

29
Roulette Wheel Selection
 This selection will have problems when the
finesses differs very much.
 Outstanding individuals will introduce a bias in
the beginning of the search that may cause a
premature convergence and a loss of diversity.

30
Roulette Wheel Selection
 For example, if an initial population contains one
or two very fit but not the best individuals and
the rest of the population are not good, then
these fit individuals will quickly dominate the
whole population and prevent the population
from exploring other potentially better
individuals.
 Such a strong domination causes a very high
loss of genetic diversity which is definitely not
advantageous for the optimization process.
31
Rank Selection

 Rank selection first ranks the population and

then every chromosome receives fitness from
this ranking.
 The worst will have fitness 1, second worst 2
etc. and the best will have fitness N (number
of chromosomes in population).

32
Rank Selection

33
Rank Selection
 After this all the chromosomes have a chance to be
selected.
 Rank-based selection schemes can avoid premature
convergence.
 But can be computationally expensive because it sorts
the populations based on fitness value.
 But this method can lead to slower convergence,
because the best chromosomes do not differ so much
from other ones.

34
Tournament Selection

 Tournament selection is a method of

selecting an individual from a population of
individuals.
 Tournament selection involves running
several "tournaments" among a few
individuals chosen at random from the
population.

35
Tournament Selection
 The winner of each tournament (the one with the
best fitness) is selected for crossover.
 When the tournament size is smaller, Tournament
selection also gives a chance to all individuals to
be selected and thus it preserves diversity,
although keeping diversity may degrade the
convergence speed.
 But if the tournament size is larger, weak
individuals have a smaller chance to be
selected causes loss of diversity .

36
 Crossover
It is the process in which two chromosomes
(strings) combine their genetic material (bits) to
produce a new offspring which possesses both
their characteristics.

 Two strings are picked from the mating pool at random

to cross over.

 The method chosen depends on the Encoding Method

such as special crossover for TSP.

37
 Crossover Methods
 Single Point Crossover- A random point is
chosen on the individual chromosomes (strings) and
the genetic material is exchanged at this point.

38
 Crossover Methods (contd.)
 Single Point Crossover

Chromosome1 11011 | 00100110110

Chromosome 2 11011 | 11000011110

Offspring 1 11011 | 11000011110

Offspring 2 11011 | 00100110110

39
Single point crossover

 More likely to keep together genes that are near

each other
 Can never keep together genes from opposite
ends of string
 This is known as Positional Bias
 Crossover Methods (contd.)
 Multi-Point Crossover- This crossover method is
widely used to shuffle the different characteristics of an
individual.
 Two point crossover.
 N-point crossover

41
 Crossover Methods (contd.)
 Two-Point Crossover- Two random points are
chosen on the individual chromosomes (strings) and
the genetic material is exchanged at these points.

Chromosome1 11011 | 00100 | 110110

Chromosome 2 10101 | 11000 | 011110

Offspring 1 10101 | 00100 | 011110

Offspring 2 11011 | 11000 | 110110

42
 n-point crossover
 Choose n random crossover points
 Split along those points
 Glue parts, alternating between parents
 Crossover Methods (contd.)
 Uniform Crossover- Each gene (bit) is selected
randomly from one of the corresponding genes of the
parent chromosomes.

Chromosome1 1101100100110110

Chromosome 2 1010111000011110

Offspring 1 1011100000110110

Offspring 2 1110111100011110

44
 Uniform Crossover
 The Uniform Crossover uses a fixed mixing ratio between
two parents.
 Unlike one- and two-point crossover, the Uniform
Crossover enables the parent chromosomes to contribute
the gene level rather than the segment level.
 If the mixing ratio is 0.5, the offspring has approximately
half of the genes from first parent and the other half from
second parent.

45
Three Parent Crossover

 Three parents are randomly chosen.

 Each bit of the first parent is compared with
the bit of the second parent.
 If both are the same, the bit is taken for the
offspring otherwise; the bit from the third
parent is taken for the offspring.

46
Three Parent Crossover

47
Crossover Probability
 Crossover probability is a parameter to describe how
often crossover will be performed.
 If there is no crossover, offspring are exact copies of
parents
 If there is crossover, offspring are made from parts of
both parent’s chromosome.
 If crossover probability is 100%, then all offspring are
made by crossover.
 If it is 0%, whole new generation is made from exact
copies of chromosomes from old population

48
 Mutation
Mutation is a genetic operator used to maintain
genetic diversity from one generation of a population
of genetic algorithm chromosomes to the next.

We saw in the giraffes’ example, that mutations could be

beneficial.

Mutation Probability- determines how often the parts of a

chromosome will be mutated.

49
 Example Of Mutation

 Flipping: For chromosomes using Binary Encoding,

randomly selected bits are inverted.

Offspring 11011 00100 110110

Mutated Offspring 11010 00100 100110

50
Mutation

 Interchanging: Two random positions of the

string are chosen and the bits corresponding
to those positions are interchanged.

51
Mutation

 Reversing: A random position is chosen and

the bits next to that position are reversed and
child chromosome is produced.

52
Mutation Probability

 The mutation probability decides how often

parts of chromosome will be mutated.
 If there is no mutation, offspring are
generated immediately after crossover
without any change.
 If mutation probability is 100%, whole
chromosome is changed, if it is 0%, nothing
is changed.

53
 Exploration and
Exploitation
Exploration: Discovering promising areas in the search
space, i.e. gaining information on the problem
Exploitation: Optimising within a promising area, i.e. using
information
 Mutation is explorative, It is used for introducing diversity
in the population. It helps to explore new areas and to
avoid local minimum.
 Cross-over operators are widely used to lead population
to converge on the good solutions find so far (exploitation).
Exploration and Exploitation
 Too high mutation rate increases the probability of
searching more areas in search space, however,
prevents population to converge to any optimum
solution.
 On the other hand, too small mutation rate may result
to premature convergence (falling to local optima instead
of global optimum).
 In other words, too high mutation rate reduces the
search ability of GA to a simple random walk while for a
too small mutation rate, GA almost always fails to a local
optimum.

55
Exploration and Exploitation

 Selection and Crossover operators will tend

to cause the algorithms to converge on a
good but sub-optimal solution
 Mutation alone induces a random walk
through the search space which helps to
jump out of sub-optimal solution.

56
 Elitism
Elitism is a method which copies the best
chromosome to the new offspring population
before crossover and mutation.

 When creating a new population by crossover or

mutation the best chromosome might be lost.

 Forces GAs to retain some number of the best

individuals at each generation.

 Has been found that elitism significantly improves

performance.

57
Elitism

58
Genetic Algorithms To
Solve The Traveling
Salesman Problem
(TSP)
 The Problem
The Traveling Salesman Problem is defined
as:

‘We are given a set of cities and a symmetric distance

matrix that indicates the cost of travel from each city to
every other city.
The goal is to find the shortest circular tour, visiting
every city exactly once, so as to minimize the total
travel cost, which includes the cost of traveling from the
last city back to the first city’.

Traveling Salesman Problem

TSP example

 Problem:
• Given n cities
• Find a complete tour with
minimal length
 Encoding:
• Label the cities 1, 2, … , n
• One complete tour is one
permutation (e.g. for n =4
[1,2,3,4], [3,4,2,1] are OK)
 Search space is BIG:
for 30 cities there are 30!  1032
possible tours
 Encoding
 Represent every city with an integer.

 Consider 6 Indian cities –

Mumbai, Nagpur , Calcutta, Delhi , Bangalore and
Chennai and assign a number to each.

Mumbai 1
Nagpur 2
Calcutta 3
Delhi 4
Bangalore 5
Chennai 6
 Encoding(contd.)
 Thus a path would be represented as a sequence of
integers from 1 to 6.

 The path [1 2 3 4 5 6 ] represents a path from Mumbai to

Nagpur, Nagpur to Calcutta, Calcutta to Delhi, Delhi to
Bangalore, Bangalore to Chennai, and finally from
Chennai to Mumbai.

 This is an example of Permutation Encoding as the

position of the elements determines the fitness of the
solution.
 Fitness Function
 The fitness function will be the total cost of the tour
represented by each chromosome.

 This can be calculated as the sum of the distances

traversed in each travel segment.

The Lesser The Sum, The Fitter The Solution

Represented By That Chromosome.
 Distance/Cost Matrix For
1 2
TSP 3 4 5 6

1 0 863 1987 1407 998 1369

2 863 0 1124 1012 1049 1083

3 1987 1124 0 1461 1881 1676

4 1407 1012 1461 0 2061 2095

5 998 1049 1881 2061 0 331

6 1369 1083 1676 2095 331 0

Cost matrix for six city example.

Distances in Kilometers
 Fitness Function (contd.)
 So, for a chromosome [4 1 3 2 5 6], the total cost of
travel or fitness will be calculated as shown below

 Fitness = 1407 + 1987 + 1124 + 1049 + 331+ 2095

= 7993 kms.

 Since our objective is to Minimize the distance, the

lesser the total distance, the fitter the solution.
 Selection Operator
May use Tournament Selection.

As the name suggests tournaments are played between

two solutions and the better solution is chosen and
placed in the mating pool.

Two other solutions are picked again and another slot in

the mating pool is filled up with the better solution.
Tournament Selection
7993
(contd.)
Mating Pool
6872
4 1 3 2 5 6
6872
4 3 2 1 5 6
8971
4 3 2 1 5 6 8673 3 6 4 1 2 5
5 2 6 4 3 1 8673
5 2 6 4 3 1
8971
3 6 4 1 2 5 7993

7993 4 1 3 2 5 6
4 1 3 2 5 6 8142
8479
6 3 4 5 2 1
2 6 3 4 5 1
8142
6872 2 6 3 4 5 1
4 3 2 1 5 6 6872
8479 4 3 2 1 5 6 8673
6 3 4 5 2 1
8142 5 2 6 4 3 1
2 6 3 4 5 1 8142
2 6 3 4 5 1
 Why we cannot use single-
point crossover:
 Single point crossover method randomly selects a crossover
point in the string and swaps the substrings.
 This may produce some invalid offsprings as shown below.

4 1 3 2 5 6 4 1 3 1 5 6

4 3 2 1 5 6 4 3 2 2 5 6
Mutation operators for TSP
 Normal mutation operators lead to
inadmissible solutions
 e.g. bit-wise mutation : let gene i have value j
 changing to some other value k would mean
that k occurred twice and j no longer occurred
Insert Mutation for TSP

 Pick two allele values at random

 Move the second to follow the first, shifting
the rest along to accommodate
 Note that this preserves most of the order (3
links are broken) and the adjacency
information
Swap mutation for
permutations
 Pick two alleles at random and swap their
positions
 Preserves most of adjacency information (4
links broken), disrupts order more
 Inversion mutation for TSP
 Pick two alleles at random and then invert the
substring between them.
 Preserves most adjacency information (only
breaks two links) but disruptive of order
information
 Scramble mutation for TSP
 Pick a subset of genes at random
 Randomly rearrange the alleles in those
positions
Crossover operators for TSP

“Normal” crossover operators will often lead
to inacurrate solutions

12345 12321
54321 54345

 Many specialised operators have been

devised which focus on combining order or
adjacency information from the two parents
Order 1 crossover
 Idea is to preserve relative order that elements occur
 Informal procedure:
1. Choose an arbitrary part from the first parent
2. Copy this part to the first child
3. Copy the numbers that are not in the first part,
to the first child:
 starting right from cut point of the copied part,
 using the order of the second parent
 and wrapping around at the end
4. Analogous for the second child, with parent
roles reversed
Order 1 crossover example
 Copy randomly selected set from first parent

 Copy rest from second parent in order 1,9,3,8,2

Partially Mapped Crossover (PMX)

Informal procedure for parents P1 and P2:

1. Choose random segment and copy it from P1
2. Starting from the first crossover point look for elements in that
segment of P2 that have not been copied
3. For each of these i look in the offspring to see what element j has
been copied in its place from P1
4. Place i into the position occupied j in P2, since we know that we will
not be putting j there (as is already in offspring)
5. If the place occupied by j in P2 has already been filled in the
offspring k, put i in the position occupied by k in P2
6. Having dealt with the elements from the crossover segment, the
rest of the offspring can be filled from P2.
Second child is created analogously
PMX example

 Step 1

 Step 2

 Step 3
PMX example

 Step 1

 Step 2

 Step 3
PMX example

 Step 1

 Step 2

 Step 3
Cycle crossover
Basic idea:
Each allele comes from one parent together with its position.
Informal procedure:
1. Make a cycle of alleles from P1 in the following way.
(a) Start with the first allele of P1.
(b) Look at the allele at the same position in P2.
(c) Go to the position with the same allele in P1.
(d) Add this allele to the cycle.
(e) Repeat step b through d until you arrive at the first allele of P1.
2. Put the alleles of the cycle in the first child on the
positions they have in the first parent.
3. Take next cycle from second parent
Cycle crossover example

 Step 1: identify cycles

Cycle crossover example

 Step 1: identify cycles

 Step 2: copy alternate cycles into offspring

 Crossover Operator
 Used the Enhanced Edge Recombination operator
([Link], et al, 'A Comparison of Genetic
Sequencing Operators, International Conference of GAs,
1991).

 This operator is different from other genetic sequencing

operators in that it emphasizes adjacency information
instead of the order or position of items in the sequence.

 The algorithm for the Edge-Recombination Operator

involves constructing an Edge Table first.
 Edge Table

The Edge Table is an adjacency table that lists links into

and out of a city found in the two parent sequences.

If an item is already in the edge table and we are trying to

insert it again, that element of a sequence must be a
common edge and is represented by inverting it's sign.
Finding The Edge Table
Parent 1 4 1 3 2 5 6
Parent 2 4 3 2 1 5 6

1 4 3 2 5

2 -3 5 1

3 1 -2 4

4 -6 1 3

5 1 2 -6

6 -5 -4
 Enhanced Edge Recombination
1.
Algorithm
Choose the initial city from one of the two parent tours. (It can be
chosen randomly). This is the current city.

2. Remove all occurrences of the current city from the left hand side
of the edge table.( These can be found by referring to the edge-list
for the current city).

3. If the current city has entries in it's edge-list, go to step 4 otherwise

go to step 5.

4. Determine which of the cities in the edge-list of the current city has
the fewest entries in it's own edge-list. The city with fewest entries
becomes the current city. In case a negative integer is present, it is
given preference. Ties are broken randomly. Go to step 2.

5. If there are no remaining unvisited cities, then stop. Otherwise,

randomly choose an unvisited city and go to step 2.
Example Of Enhanced Edge
Recombination Operator
Step 1 Step 2

1 4 3 2 5
1 3 2 5

2 -3 5 1
2 -3 5 1

3 1 -2 4
3 1 -2

4 -6 1 3
4 -6 1 3

5 1 2 -6
5 1 2 -6

6 -5 -4
6 -5

4 4 6
Example Of Enhanced Edge
Recombination Operator
Step 3 (contd.)Step 4
1 3 2 5 1 3 2

2 -3 5 1
2 -3 1

3 1 -2
3 1 -2

4 1 3
4 1 3

5 1 2
5 1 2

6 -5 6

4 6 5 4 6 5 1
Example Of Enhanced Edge
Recombination Operator
Step 5 (contd.) Step 6
1 3 2 1 2

2 -3 2

3 -2 3 -2

4 3 4

5 1 2 5 2

6 6

4 6 5 1 3 2
4 6 5 1 3
 Mutation Operator
 The mutation operator induces a change in the solution,
so as to maintain diversity in the population and prevent
Premature Convergence.
 In this project, the string is mutated by randomly
selecting any two cities and interchanging their positions
in the solution, thus giving rise to a new tour.

4 1 3 2 5 6

4 5 3 2 1 6
When to Use a GA
 Alternate solutions are too slow.
 The search space is large, complex or poorly
understood.
 No mathematical analysis is available.
 Problem is similar to one that has already been
successfully solved by using a GA
 Want to hybridize with an existing approach, such as
Particle Swarm Optimization (PSO) embeds in GA.
 Traditional search methods fail.
Aspects of Genetic Algorithms

 Concept is easy to understand

 Supports multi-objective optimization
 Always an answer; answer gets better with
time
 Inherently parallel; easily distributed
 Advantages Of GAs
 Global Search Methods: GAs search for the
function optimum starting from a population of points of
the function domain, not a single one. This characteristic
suggests that GAs are global search methods. They can,
in fact, climb many peaks in parallel, reducing the
probability of finding local minima, which is one of the
drawbacks of traditional optimization methods.

95
 Advantages of GAs (contd.)

 Blind Search Methods: GAs only use the

information about the objective function. They do not
require knowledge of any other auxiliary information,
allowing a number of problems to be solved without the
need to formulate restrictive assumptions. For this
reason, GAs are often called blind search methods.

96
 Advantages of GAs (contd.)

 GAs can be easily used in parallel machines-

Since in real-world design optimization problems, most
computational time is spent in evaluating a solution, with
multiple processors all solutions in a population can be
evaluated in a distributed manner. This reduces the
overall computational time substantially.

97
probabilistic not
deterministic
 Notice that, in the previous examples, we

formed the child organisms randomly

 We did not try to choose the “best” genes from each
parent
 This is how natural (biological) evolution works
 Biological evolution is not directed—there is no “goal”
 Genetic algorithms use biology as inspiration, not as
a set of rules to be followed.
 GA is probabilistic not deterministic.

98