Computer Science and Engineering Department
Artificial Intelligence (UCS-411)
Lab Assignment-5
1 Solve the given 0/1 knapsack problem by considering the following points:
Name Weight Value
A 45 3
B 40 5
C 50 8
D 90 10
Chromosome is a 4-bit string. – {xA xB xC xD}
Population size = 4, Maximum Capacity of the bag (W) = 100.
First two fittest chromosomes selected as it is. 3rd and 4th fittest use for one-point crossover in
the middle followed by single bit mutation of first offspring.
Bits chosen for mutation follows this cyclic order (xD, xC, xB, xA).
Initial population: {1 1 1 1, 1 0 0 0, 1 0 1 0, 1 0 0 1}.
Output the result after 10 iterations.
2 A thief enters a house for robbing it. He can carry a maximal weight of 9 kg into his bag. There
are 4 items in the house with the following weights and values. The thief has to plan the items he
should take to maximize the total value if he either takes the item completely or leaves it
completely?
Item Item Name Weight (in Kg) Value (in $)
A Mirror 2 3
B Silver Nugget 3 5
C Painting 4 7
D Vase 5 9
The problem is solved using Genetic Algorithm with population size 4 and each individual
encoded as {XA, XB, XC, XD} where Xi ={0,1 } and i=A, B, C, D.
Consider initial population as 1111, 1000, 1010, and 1001.
Generate the population for next iteration as follows: Select the 1st and 2nd fittest individual as it
is in the next iteration. Apply 1-point crossover in the middle between 3rd and 4th fittest
chromosome followed by single bit mutation of first offspring (produced through crossover). Bit
chosen for mutation follows this cyclic order {XC,XA,XD,XB}
Output the result after four iterations.
3 Consider the following 2-SAT problem with 4 Boolean variables a, b, c, d:
F=(¬a∨d)𝖠(c∨b) 𝖠 ( ¬c∨¬d) 𝖠 ( ¬d∨¬b) 𝖠 (¬a∨¬d)
The MOVEGEN function to generate new solution be arbitrary changing value of any one
variable
Let the candidate solution be of the order (abcd) and the initial candidate solution be (1111).
Let heuristic to evaluate each solution be number of clauses satisfied in the formula.
Apply Simulated Annealing (Consider T= 500 and cooling function = T-50)
(Assume the following 3 random numbers:0.655,[Link])
Accept every good move and accept a bad move if probability is greater than 50%.
