CSE422: Artificial Intelligence
Assignment 2
Genetic Algorithm
Question 1:
Object Profit Weight
A 7 3
B 3 2
C 12 6
D 5 8
E 4 5
F 16 1
G 20 4
Maximum weight = 20
The above problem is a 0/1 Knapsack problem. Here there are 7 different objects labelled from A
to G. The objective of this problem is to carry the different objects in your bag in such a way
such that the profit is maximized. But you have to make sure that your bag does not exceed the
maximum weight i.e. the maximum weight that this bag can carry is less than or equal to 15.
Remember you can carry an object exactly once. Now it is your job to use Genetic Algorithm to
solve this problem.
This study source was downloaded by 100000853497421 from CourseHero.com on 07-20-2023 01:19:19 GMT -05:00
https://www.coursehero.com/file/103965724/Solvepdf/
, 1. Encode the problem and create an initial population of 4 different chromosomes (2
marks)
Answer:
Firstly, we will create random populations on the basis of the object taken. If taken we will
put 1 otherwise 0
1 0 0 0 1 1 1
1 0 0 1 1 0 1
1 0 1 0 0 1 1
1 1 0 1 0 1 1
2. Think of an appropriate fitness function to this problem and give proper justification. (2
marks)
Here, as a fitness function we will collaborate on profit and weight. Firstly we will calculate
the sum of profits and the sum of weights.
If sum of weight <= maximum weight, return fitness= (sum of profits)
Else return fitness=0
This study source was downloaded by 100000853497421 from CourseHero.com on 07-20-2023 01:19:19 GMT -05:00
https://www.coursehero.com/file/103965724/Solvepdf/
Assignment 2
Genetic Algorithm
Question 1:
Object Profit Weight
A 7 3
B 3 2
C 12 6
D 5 8
E 4 5
F 16 1
G 20 4
Maximum weight = 20
The above problem is a 0/1 Knapsack problem. Here there are 7 different objects labelled from A
to G. The objective of this problem is to carry the different objects in your bag in such a way
such that the profit is maximized. But you have to make sure that your bag does not exceed the
maximum weight i.e. the maximum weight that this bag can carry is less than or equal to 15.
Remember you can carry an object exactly once. Now it is your job to use Genetic Algorithm to
solve this problem.
This study source was downloaded by 100000853497421 from CourseHero.com on 07-20-2023 01:19:19 GMT -05:00
https://www.coursehero.com/file/103965724/Solvepdf/
, 1. Encode the problem and create an initial population of 4 different chromosomes (2
marks)
Answer:
Firstly, we will create random populations on the basis of the object taken. If taken we will
put 1 otherwise 0
1 0 0 0 1 1 1
1 0 0 1 1 0 1
1 0 1 0 0 1 1
1 1 0 1 0 1 1
2. Think of an appropriate fitness function to this problem and give proper justification. (2
marks)
Here, as a fitness function we will collaborate on profit and weight. Firstly we will calculate
the sum of profits and the sum of weights.
If sum of weight <= maximum weight, return fitness= (sum of profits)
Else return fitness=0
This study source was downloaded by 100000853497421 from CourseHero.com on 07-20-2023 01:19:19 GMT -05:00
https://www.coursehero.com/file/103965724/Solvepdf/
