KHULNA UNIVERSITY

ECE Discipline

ASSIGNMENT
On
Genetic Algorithm

Course Title: Engineering Analysis

Course Code: ECE 5301
 SUBMITTED TO SUBMITTED BY

Dr. Md. Maniruzzaman Pranta Paul

Professor Student Id: MSc 210916
ECE Discipline, Year: 1st
Khulna University, Khulna Term: 1st

Date of Submission: 30th August, 2023

 Questions Set

Set 1
1.a)what is genetic algorithm?Draw the flowchart of it. 1+3=4
b) How many rules genetic algorithm uses? 3
c) What are the differences between classical algorithm and genetic algorithm? 3
d) What two requirements should a problem satisfy in order to be suitable for solving it by a GA?

Set 2 Set 3
a. What is the knapsack problem? 2 a. What are the limitations of genetic algorithm? 4
b. Briefly describe how can we implement b. What is crossover in genetic algorithm?
knapsack using genetic algorithm with necessary Describes different types of crossover in genetic
diagrams. 10 algorithm. 2+6=8
Set 4 Set 5

a. Consider the problem of finding the Suppose a genetic algorithm uses

shortest route through several cities,such that chromosomes of the form x = abcdefgh
each city is visited only once and in the end with a fixed length of eight genes. Each
return to the starting city (the Travelling gene can be any digit between 0 and 9.
Salesman problem). Suppose that in order to
Let the fitness of individual x be
solve this problem we use a genetic
algorithm, in which genes represent links calculated as: f(x) = (a + b) − (c + d) +
between pairs of cities. For example, a link (e + f) − (g + h) , and let the initial
between London and Paris is represented by a population consist of four individuals
single gene ‘LP’. Let also assume that the with the following chromosomes:
direction in which we travel is not important, • x1 = 6 5 4 1 3 5 3 2
so that LP = P L.
• x2 = 8 7 1 2 6 6 0 1
How many genes will be in the alphabet of
the algorithm? 5 • x3 = 2 3 9 2 1 2 8 5
• x4 = 4 1 8 5 2 0 9 4
b. Describe Lamarckian Mode and
Baldwinian Model. 7
a. Evaluate the fitness of each
individual, showing all your workings,
and arrange them in order with the
fittest first and the least fit last. 4
b. Can you say whether it will be able
to reach the optimal solution without
the mutation operator? 4
c.Find the value of the maximum a. Suggest what chromosome
fitness.4 could represent an individual in
this algorithm? 2
Set 6 b. What could be the alphabet of
A budget ariline company operates 3 this algorithm? What is its size? 2
plains and employs 5 cabin crews. Only c. What is the fitness function for
one crew can operate on any plain on a this problem. 2
single day, and each crew cannot work
for more than two days in a row. The d. How many solutions are in this
company uses all planes every day. A problem? Is it necessary to use
Genetic Algorithm is used to work out Genetic Algorithms for solving it?
the best combination of crews on any
particular day. What if the company operated
more plains and employed more
crews? 6
Set 1 Answers
a. The genetic algorithm is a method for solving both constrained and unconstrained optimization
problems that is based on natural selection, the process that drives biological evolution.
This flow chart outlines the main algorithmic steps.

b. The genetic algorithm uses three main types of rules at each step to create the next generation from the
current population:
• Selection rules select the individuals, called parents, that contribute to the population at the next
generation. The selection is generally stochastic, and can depend on the individuals' scores.
• Crossover rules combine two parents to form children for the next generation.
• Mutation rules apply random changes to individual parents to form children.
Set 1 Answers

c. The genetic algorithm differs from a classical, derivative-based, optimization

algorithm in two main ways, as summarized in the following table:

Classical Algorithm Genetic Algorithm

Generates a single point at each Generates a population of points at

iteration. The sequence of points each iteration. The best point in the
approaches an optimal solution. population approaches an optimal
solution.

Selects the next point in the sequence Selects the next population by
by a deterministic computation. computation which uses random
number generators.

Typically converges quickly to a local Typically takes many function

solution. evaluations to converge. May or may
not converge to a local or global
minimum.
Set 1 Answers
d. What two requirements should a problem satisfy
in order to be suitable for solving it by a GA?
GA can only be applied to problems that satisfy the
following requirements:
• The fitness function can be well–defined.
• Solutions should be decomposable into steps
(building blocks) which could be then encoded as
chromosomes.
Set 2 Answers
The Knapsack Problem
The Knapsack problem is an optimization problem that deals with filling up a knapsack with a bunch of
items such that the value of the Knapsack is maximized. Formally, the problem statement states that, given
a set of items, each with a weight and a value, determine the items we pack in the knapsack with a
constrained maximum weight that the knapsack can hold, such the the total value of the knapsack is
maximum.
The Genetic Process
The basic idea behind the Genetic Algorithm is to start with some candidate Individuals (solutions chosen
at random) called Population. The initial population is the zeroth population, which is responsible for the
spinning of the First Generation. The First Generation is also a set of candidate solutions that evolved from
the zeroth generation and is expected to be better.
Set 2 Answers
• Knapsack using Genetic Algorithm
Set 2 Answers
Set 2 Answers
Set 2 Answers
Set 3 Answers
What are the limitations of the genetic algorithm?
Like any other algorithm, genetic algorithms also have their own set of limitations. The first limitation is
that these algorithms are computationally expensive because the evaluation of each individual
necessitates the training of a model. The second problem faced with these algorithms is that they are
ineffective in tackling minor problems. Another issue with these algorithms is that their stochastic nature
can take a long time to converge, and improper implementation may cause the algorithm to converge to
an unsatisfactory result. Also, in a genetic algorithm, the quality of the final answer is not guaranteed. In
these algorithms, the repetitive calculation of the fittest values may cause specific issues with computing
hurdles.
Crossover in Genetic Algorithm
Crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from
one generation to the next. Crossover is sexual reproduction. Two strings are picked from the mating pool
at random to crossover in order to produce superior offspring.
Different types of crossover :
Single Point Crossover: A crossover point on the parent organism string is selected. All data beyond that
point in the organism string is swapped between the two parent organisms. Strings are characterized by
Positional Bias.
Set 3 Answers

Two-Point Crossover : This is a specific case of a

N-point Crossover technique. Two random points
are chosen on the individual chromosomes (strings)
and the genetic material is exchanged at these
points.
Set 4 Answers
• Lamarckian Model
• The Lamarckian Model essentially says that the traits which an individual acquires in his/her lifetime
can be passed on to its offspring. It is named after French biologist Jean-Baptiste Lamarck.
• Even though, natural biology has completely disregarded Lamarckism as we all know that only the
information in the genotype can be transmitted. However, from a computation view point, it has
been shown that adopting the Lamarckian model gives good results for some of the problems.
• In the Lamarckian model, a local search operator examines the neighborhood (acquiring new traits),
and if a better chromosome is found, it becomes the offspring.

• Baldwinian Model
• The Baldwinian model is an intermediate idea named after James Mark Baldwin (1896). In the
Baldwin model, the chromosomes can encode a tendency of learning beneficial behaviors. This
means, that unlike the Lamarckian model, we don’t transmit the acquired traits to the next
generation, and neither do we completely ignore the acquired traits like in the Darwinian Model.
• The Baldwin Model is in the middle of these two extremes, wherein the tendency of an individual to
acquire certain traits is encoded rather than the traits themselves.
• In this Baldwinian Model, a local search operator examines the neighborhood (acquiring new traits),
and if a better chromosome is found, it only assigns the improved fitness to the chromosome and
does not modify the chromosome itself. The change in fitness signifies the chromosomes capability
to “acquire the trait”, even though it is not passed directly to the future generations.
Set 4 Answers
• Consider the problem of finding the shortest route through several
cities,such that each city is visited only once and in the end return to
the starting city (the Travelling Salesman problem). Suppose that in
order to solve this problem we use a genetic algorithm, in which genes
represent links between pairs of cities. For example, a link between
London and Paris is represented by a single gene ‘LP’. Let also assume
that the direction in which we travel is not important, so that LP = P L.
How many genes will be in the alphabet of the algorithm?
• Answer: The alphabet will consist of 45 genes. Indeed, each of the 10
cities can be connected with 9 remaining. Thus, 10 × 9 = 90 is the
number of ways in which 10 cities can be grouped in pairs. However,
because the direction is not important (i.e. London–Paris is the same as
Paris–London) the number must be divided by 2. So, we shall need
90/2 = 45 genes in order to encode all pairs. In general the formula for
n cities is:n(n − 1)/2
Set 5 Answers
Suppose a genetic algorithm uses chromosomes of the form x = abcdefgh
with a fixed length of eight genes. Each gene can be any digit between 0
and 9. Let the fitness of individual x be calculated as:
f(x) = (a + b) − (c + d) + (e + f) − (g + h) ,
and let the initial population consist of four individuals with the following
chromosomes:
x1 = 6 5 4 1 3 5 3 2
x2 = 8 7 1 2 6 6 0 1
x3 = 2 3 9 2 1 2 8 5
x4 = 4 1 8 5 2 0 9 4
a) Evaluate the fitness of each individual, showing all your workings, and
arrange them in order with the fittest first and the least fit last.
Answer:
f(x1) = (6 + 5) − (4 + 1) + (3 + 5) − (3 + 2) = 9
f(x2) = (8 + 7) − (1 + 2) + (6 + 6) − (0 + 1) = 23
f(x3) = (2 + 3) − (9 + 2) + (1 + 2) − (8 + 5) = −16
f(x4) = (4 + 1) − (8 + 5) + (2 + 0) − (9 + 4) = −19
b. Can you say
whether it will be able to reach the optimal solution without the mu-
tation operator?
Answer: No, the algorithm will never reach the optimal solution
without mutation. The optimal solution is xoptimal = 9 9 0 0 9 9 0 0. If
mutation does not occur, then the only way to change genes is by
applying the crossover operator. Regardless of the way crossover is
performed, its only outcome is an exchange of genes of parents at
certain positions in the chromosome. This means that the first gene in
the chromosomes of children can only be either 6, 8, 2 or 4 (i.e. first
genes of x1, x2, x3 and x4), and because none of the individuals in the
initial population begins with gene 9, the crossover operator alone will
never be able to produce an offspring with gene 9 in the beginning.
One can easily check that a similar problem is present at several other
positions. Thus, without mutation, this GA will not be able to reach
the optimal solution.
C. Find the value of the
maximum fitness.
Answer: The optimal solution should have a chromosome that gives
the maximum of the fitness function
max f(x) = max [(a + b) − (c + d) + (e + f) − (g + h)] .
Because genes can only be digits from 0 to 9, the optimal solution
should be:
xoptimal = 9 9 0 0 9 9 0 0 ,
and the maximum fitness is
f(xoptimal) = (9 + 9) − (0 + 0) + (9 + 9) − (0 + 0) = 36
Set 6 Answers
A budget ariline company operates 3 plains and employs 5 cabin crews. Only
one crew can operate on any plain on a single day, and each crew cannot
work for more than two days in a row. The company uses all planes every
day. A Genetic Algorithm is used to work out the best combination of crews
on any particular day.
a) Suggest what chromosome could represent an individual in this algo-
rithm?
Answer: On each day, a solution is a combination of 3 cabin crews
assigned to 5 airplanes. Thus, a chromosome of 3 genes could be used
in this algorithm with each gene representing a crew on a certain plain.
b) Suggest what could be the alphabet of this algorithm? What is its
size?
Answer: The alphabet of genes representing the crews can be used.
Thus, its size is 5.
c) Suggest a fitness function for this problem.
Answer: You may come up with different versions, but it is impor-
tant for the fitness to take into account the condition that cabin crews
cannot work more than 2 days in a row. For example, the fitness func-
tion can take into account how many days each crew has left before
a day off (e.g. 1 or 0). The fitness could be calculated as the sum of
these numbers for all drivers in the chromosome.
d) How many solutions are in this problem? Is it necessary to use Genetic
Algorithms for solving it? What if the company operated more plains
and employed more crews?
Answer: The number of solutions is the number of times 3 crews
can be selected out of 5 without replacement and without taking into
account their order. The first crew can be selected in 5 different ways,
the second in 4 ways and the third in 3 different ways. These numbers
multiplied together will give us total number times how 3 crews can be
selected randomly out of 5: 5 × 4 × 3 = 60 times. However, there are
6 possible combinations in which 3 crews can be ordered, and because
the order does not matter the answer is 60/6 = 10. Thus, there are 10
possible solutions for this problem.
It is not really necessary to use GA for a problem with such a small
population, because solutions can be checked explicitly. However, as
the number of crews and airplanes increases, so does the number of
solutions, and the use of GA can be the only option. In fact, if n is
the number of cabin crews and k ≤ n is the number of airplanes, then
the number of solutions is
n!
/ k!(n − k)! .
For example, if the company operated 10 airplanes and employed 20
cabin crews, then the number of solutions would be
20!
10! / (20 − 10)! = 184, 756
Thank You