SOFT COMPUTING

A7710

Genetic algorithms
General Introduction to
GAs
Genetic algorithms (GAs) are the main paradigm of

evolutionary computing. GAs are inspired by Darwin's theory

about evolution – the "survival of the fittest".

In nature, competition among individuals for scanty

resources results in the fittest individuals dominating over the

weaker ones.
GAs are intelligent exploitation of random search used in

optimization problems.
GAs, although randomized, exploit historical information to
direct the search into the region of better performance
within the search space.

12/12/14 CSE510, Lovely Professional University, Phagwara

General Introduction to GAs
• Genetic algorithms (GAs) are a technique to
solve problems which need optimization.
• GAs are a subclass of Evolutionary Computing and
are random search algorithms.

•History of GAs:

• Evolutionary computing evolved in the 1960s.

• GAs were created by John Holland in the mid-
1970s.
Applications of GA
 Applications of GA
• 1. Neural networks
• Genetic programming in machine learning finds great applications for neural
networks in machine learning. We use it for ‌genetic optimization in neural networks
or use cases like inheriting qualities of neurons, neural network pipeline optimization,
finding the best fit set of parameters for a given neural network, and others.
• 2. Data mining and clustering
• Data mining and clustering use genetic algorithms to find out the centre point of the
clusters with an optimal error rate given to its great searching capability for an
optimal value. It is renowned as an unsupervised learning process in machine
learning, where we categorize the data based on the characteristics of the data
points.
• 3. Image processing
• Image processing tasks, such as image segmentation, are one of the major use cases
of genetic optimization. However, genetic algorithms can also be used in different
areas of image analysis to resolve complex optimization problems.
 Applications of GA
• 4. Wireless sensor network
• A wireless sensor network refers to one which includes dedicated and especially dispersed
centers that maintain the record of the physical conditions of an environment. It further
passes the record created to a central storage system.
• WSN utilizes genetic machine learning to stimulate the sensors. We can optimize and even
customize all the operational stages with the help of the fitness function from genetic
algorithms in wireless sensor networks.
• 5. Traveling salesman problem (TSP)
• TSP or traveling salesman problem is one of the real-life combinatorial optimization
problems that were solved using genetic optimization. It helps in finding an optimal way in
a given map with the distance between two points and with the routes to be covered by
the salesman.
• Several iterations take place that generate offspring solutions after every iteration to
inherit the qualities of parent solutions. In this way we don’t get the solution only one time
that offers you the opportunity to choose the best route structure. It finds application in
real-time processes like planning, manufacturing and logistics.
 Applications of GA
• 6. Vehicle routing problems
• One of the generalisations of the travelling salesman problem discussed above is the
vehicle routing problem. Genetic algorithms help in finding the optimal weight of goods
to be delivered through the optimal set of delivery routes. Factors such as depot points,
wait, distance are taken into consideration while solving such problems if they have any
kind of restrictions. Moreover, the genetic algorithm approach is competitive in terms of
solution quality and time with simulated annealing algorithms and tabu search.
• 7. Mechanical engineering design
• Genetic algorithms find application in many designing procedures of mechanical
components. For instance, consider the following genetic algorithm example where the
aircraft wing design is a kind of designing problem that takes multiple disciplines into
consideration. It requires improvement in the ratio of left to drag for a complex wing.
• The fitness function in genetic optimization is flexible to considerations that come as a
demand for a particular design.
 Applications of GA
• 8. Manufacturing system
• The manufacturing arena includes various examples of the cost function.
Based on the same, the need to find an optimal set of parameters for such
functions poses a problem.
• Genetic optimization performs this task of using the optimized set of
parameters to minimize the cost function. It also finds application in product
manufacturing to achieve optimum production plans by considering dynamic
conditions like capacity, inventories, or material quality.
• 9. Financial markets
• A variety of issues can be solved using genetic optimization in the financial
market. It helps in finding an optimal combination of parameters that can
affect the trades or market rules. You can also find out the near-optimal value
for the optimal set of parameters.
 Applications of GA
• 10. Medical science
• Medical signs have an array of use cases for genetic optimization. The areas of
predictive analysis include protein prediction, RNA structure prediction, operon
prediction, and others.
• Other processes such as protein folding, gene expression profiling analysis,
bioinformatics multiple sequence alignment, or some of the process alignment that
uses genetic optimisation.
• 11. Task scheduling
• Genetic machine learning algorithms are used to derive optimal schedules that
satisfy certain constraints related to a problem.
• For instance: assume that you have to prepare the schedule for the semester
exams for University. The genetic algorithm will find the best optimal schedule for
the university considering all the constraints like the number of classrooms, the
number of students, the total number of courses and subjects, and others.
 Applications of GA
• 12. Economics
• Economics is the study of resource utilization in the production, distribution,
and complete consumption of goods and services over a time period. The
genetic algorithm creates models of demand and supply that derive asset
pricing, game theory, and others.
• 13. Robotics
• Robotics comprises the construction, design, and working of the autonomous
robot. Genetic algorithms contribute to the robotics field by providing the
necessary insight into the decisions made by the robot. It generates optimal
routes for the robot so that it can use the least amount of resources to get to
the desired position.
 Advantages of the genetic algorithm
• The genetic algorithms put a plethora of advantages on the table. Get
acquainted with them in the next segment.
• Genetic algorithms provide solutions or answers that improve over a period.
• It does not need any derivative information and has excellent parallel
capabilities.
• It optimizes several problems, such as continuous functions, discrete
functions, and multi-objective problems.
• It comes as the best choice for a wide variety of optimization problems.
• It has a large and broad space for solutions search ability.
 Biological Background (1) – The Cell
•The center of this all is the cell nucleus.
• The nucleus contains the genetic information.
 Biological Background (2) – Chromosomes

 Every organism has a set of rules, describing how that organism is built. All

living organisms consist of cells.

In each cell there is same set of chromosomes. Chromosomes are strings of DNA

and serve as a model for the whole organism.

• Each chromosome is build of DNA (Deoxyribonucleic

acid).
• Chromosomes in humans form pairs.
• There are 23 pairs.
• The chromosome is divided in parts: genes.
 Biological Background (3) – Chromosomes
 Each gene encodes a particular proteinthat 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.
Biological Background (4) – Genetics
•A genotype develops into a phenotype.
• Alleles can be either dominant or recessive.
• Dominant alleles will always express from the
genotype to the phenotype.
• Recessive alleles can survive in the population for
many generations without being expressed.
Biological Background (5) – Genetics
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).
 Genetic Algorithm (1) – Search Space
• Most often one is looking for the best solution
in a specific subset of solutions.
• This subset is called the search space (or state
space).
• Every point in the search space is a possible
solution.
• Therefore every point has a fitness value,
2.5

depending on the problem definition.

2

• GAs are used to search the 1.5

search space for the best

1

solution, e.g. a minimum.

0.5

• Difficulties are the local 0

0 100 200 300 400 500 600 700 800 900 1000

minima and the starting

Genetic Algorithm (2) – Basic Algorithm
• Starting with a subset of n randomly chosen
solutions from the search space (i.e.
chromosomes).
This is the population.

• This population is used to produce a next

generation of individuals by reproduction.

• Individuals with a higher fitness have more

chance to reproduce (i.e. natural
selection).
Biological Background (2) – Chromosomes
Comparison of Natural and GA Terminology

Natural Genetic Algorithm

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

Chromosome : a set of genes; a chromosome contains

the solution in form of genes.

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.
Working Principles

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.
 Genetic Algorithm– Basic Algorithm
• Outline of the basic algorithm

0 START : Create random population of n chromosomes

1 FITNESS : Evaluate fitness f(x) of each chromosome in
the population
2 NEW POPULATION
1 REPRODUCTION/SELECTION : Based on f(x)
2 CROSS OVER : Cross-over chromosomes
3 MUTATION : Mutate chromosomes
3 REPLACE : Replace old with new population: the new
generation
4 TEST : Test problem criterium
5 LOOP : Continue step 1 – 4 untill criterium is satisfied
Genetic Algorithm– Basic Algorithm
• Outline of the basic algorithm
Encoding
25
https://www.youtube.com/watch?v=INOvj1iQZ14
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
Random Resetting
Random Resetting is an extension of the bit flip for the integer
representation. In this, a random value from the set of
permissible values is assigned to a randomly chosen gene.
Swap Mutation
In swap mutation, we select two positions on the chromosome at
random, and interchange the values. This is common in
permutation based encodings.

12/12/14 CSE510, Lovely Professional University, Phagwara

Scramble Mutation
Scramble mutation is also popular with permutation
representations. In this, from the entire chromosome, a subset of
genes is chosen and their values are scrambled or shuffled
randomly.

Inversion Mutation
In inversion mutation, we select a subset of genes like in
scramble mutation, but instead of shuffling the subset, we
merely invert the entire string in the subset.

12/12/14 CSE510, Lovely Professional University, Phagwara

12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
12/12/14 CSE510, Lovely Professional University, Phagwara
 Example of GA

• Traveling Salesman Problem Solution using Genetic Algorithm

• There are five cities that a salesperson will pass. The cities are A, B, C, D,
and E. The journey starts from A and ends at A as well.

78
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

79
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm
• Try to find the smallest global optimum value. Chromosome
initialization is done.

80
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

81
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

82
Example of GA

• Traveling Salesman Problem Solution using Genetic Algorithm

• Crossover is done to produce children from two mothers who are mated.
• The resulting chromosomes are expected to increase the value of fitness.
• The number of chromosomes that experience crossover is determined by crossover probability.
• The crossover probability value is 0.25.

83
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

84
 Example of GA
•
Traveling Salesman Problem Solution using Genetic Algorithm
• This section will be carried out of the mutation process.
• This mutation works to exchange genes for genes on other chromosomes. Expected results increase the value of
fitness to be achieved.
• If a gene is exchanged at the end of a chromosome, this gene will be exchanged for the first gene.
• There is a parameter to determine how many genes will be mutated. The mutation rate is 0.2.

85
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

86
Example of GA
• Traveling Salesman Problem Solution using Genetic Algorithm

87
 Example of GA
•
Traveling Salesman Problem Solution using Genetic Algorithm
• In the first generation, it has been seen that there is the smallest fitness value that does not change.
• If the calculation is continued up to the Nth generation, then it is assumed that the lowest fitness value will remain
unchanged.
• Although the calculation is sufficiently elaborated up to the 1st generation, a near-optimal solution has been found, from
the genetic algorithm process above, the final result the route with the shortest optimal distance is A, B, D, E, C, A.

88
Checkboard example

• We are given an n by n checkboard in which every field

can have a different colour from a set of four colors.
• Goal is to achieve a checkboard in a way that there are
no neighbours with the same color (not diagonal)

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

10 10

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Checkboard example Cont’d

• Chromosomes represent the way the checkboard is

colored.
• Chromosomes are not represented by bitstrings but by
bitmatrices
• The bits in the bitmatrix can have one of the four values
0, 1, 2 or 3, depending on the color.
• Crossing-over involves matrix manipulation instead of
point wise operating.
• Crossing-over can be combining the parential matrices in
a horizontal, vertical, triangular or square way.
• Mutation remains bitwise changing bits in either one of
the other numbers.
Checkboard example Cont’d

• This problem can be seen as a graph with n nodes and (n-1) edges, so the
fitness f(x) is defined as:

f(x) = 2 · (n-1) ·n
Checkboard example Cont’d
• Fitnesscurves for different cross-over rules:

Lower-Triangular Crossing Over Square Crossing Over

180 180

170 170

160 160
Fitness

150 150

140 140

130 130
0 100 200 300 400 500 0 200 400 600 800

Horizontal Cutting Crossing Over Verical Cutting Crossing Over

180 180

170 170

160 160
Fitness

150 150

140 140

130 130
0 200 400 600 800 0 500 1000 1500
Generations Generations
 Q&A

1. Genetic algorithms are example of

A: heuristic
B: Evolutionary algorithm
C: ACO
D: PSO
 Q&A

1. Genetic algorithms are example of

A: heuristic
B: Evolutionary algorithm
C: ACO
D: PSO
 Q&A

2. Fitness function should be

A: maximum
B: minimum
C: intermediate
D: noneof these
 Q&A

2. Fitness function should be

A: maximum
B: minimum
C: intermediate
D: noneof these
 Q&A

3. Genetic algorithms are example of

A: heuristic
B: Evolutionary algorithm
C: ACO
D: PSO
 Q&A

3. Genetic algorithms are example of

A: heuristic
B: Evolutionary algorithm
C: ACO
D: PSO
 Q&A

4. Parameters that affect GA

A: initial population
B: selection process
C: fitness function
D: all of these
 Q&A

4. Parameters that affect GA

A: initial population
B: selection process
C: fitness function
D: all of these
 Q&A

5. EV is dominantly used for solving ___.

A: optimization problems
B: NP problem
C: simple problems
D: none of these
 Q&A

5. EV is dominantly used for solving ___.

A: optimization problems
B: NP problem
C: simple problems
D: none of these
Q&A

1. Matrix crossover is also known as _________

A.One dimensional
B.Two dimensional
C.Three dimensional
D.None of the above

103
Q&A

1. Matrix crossover is also known as _________

A.One dimensional
B.Two dimensional
C.Three dimensional
D.None of the above

104
Q&A

2. Idea of genetic algorithm came from

A: machines
B: Birds
C: ACO
D: genetics

105
Q&A

2. Idea of genetic algorithm came from

A: machines
B: Birds
C: ACO
D: genetics

106
Q&A

3. Chromosomes are actually ?

A: line representation
B: String representation
C: Circular representation
D: all of these

107
Q&A

3. Chromosomes are actually ?

A: line representation
B: String representation
C: Circular representation
D: all of these

108
Q&A

4. what are the parameters that affect GA are/is

A: selection process
B: initial population
C: both a and b
D: none of these

109
Q&A

4. what are the parameters that affect GA are/is

A: selection process
B: initial population
C: both a and b
D: none of these

110
Q&A

5. Survival is ___ approach.

A: deteministic
B: non deterministic
C: semi deterministic
D: none of these

111
Q&A

5. Survival is ___ approach.

A: deteministic
B: non deterministic
C: semi deterministic
D: none of these

112
 Q&A

a. 24
b. 576
c. 14.4
d. 49.2

113
 Q&A

a. 24
b. 576
c. 14.4
d. 49.2

114
Q&A

115
Q&A

Ans: Cross Over

116
Q&A

1. Genetic algorithm is first introduce by_______.

A.charles darwin
B.john holland
C.gregor johan mendel
D.none of these

117
Q&A

1. Genetic algorithm is first introduce by_______.

A.charles darwin
B.john holland
C.gregor johan mendel
D.none of these

118
Q&A

2. Genetic algorithm belong to the family of method in the

A.artifical intelligence
B.optimization area
C.complete enumerat
D.Non computer based

119
Q&A

2. Genetic algorithm belong to the family of method in the

A.artifical intelligence
B.optimization area
C.complete enumerat
D.Non computer based

120
Q&A

3. What is the name of the process that represents modified elements

of the DNA?
A.Selection
B.Mutation
C.Recombination
D.None of the above

121
Q&A

3. What is the name of the process that represents modified elements

of the DNA?
A.Selection
B.Mutation
C.Recombination
D.None of the above

122
Q&A

4. Which of the following is the best representation of individual

genes?
A.Coding
B.Conversion
C.Encoding
D.None of the above

123
Q&A

4. Which of the following is the best representation of individual

genes?
A.Coding
B.Conversion
C.Encoding
D.None of the above

124
Q&A

5. Which of the following is not a specified method used for selecting

the parents?
A.Tournament Selection
B.Steady-state
C.Elitism
D.Boltzmann selection

125
Q&A

5. Which of the following is not a specified method used for selecting

the parents?
A.Tournament Selection
B.Steady-state
C.Elitism
D.Boltzmann selection

126
Q&A

6. Matrix crossover is also known as _________

A.One dimensional
B.Two dimensional
C.Three dimensional
D.None of the above

127
Q&A

6. Matrix crossover is also known as _________

A.One dimensional
B.Two dimensional
C.Three dimensional
D.None of the above

128
12/12/14 CSE510, Lovely Professional University, Phagwara