# 0/1 knapscak Problem

This problem asks you to apply the GA to the well-known 0/1 knapsack problem. The 0/1 knapsack

problem is defined as follows:

Input

• n: The number of items is denoted by n.

• si and vi: Each item has two parameters that define it: size and value. The size of ith

item is si, the value of ith item is vi. We number the items from 1 to n (not from 0).

• C: The total capacity of our knapsack is denoted by C. The total size of all items in

the knapsack must not be greater than C.

Decide what items to take so that you maximize the total value of the items you take, but

also make sure that the total size of the items you took does not exceed C.

a) Propose a way to encode potential solutions for knapsack (each potential solution represents a

particular subset of the n items). Explain your encoding and explain why your encoding will

work.

b) Propose a fitness function to use. The fitness function must return a number for every possible

binary string in your representation and the best solution to the problem (best subset of items

satisfying the maximum size) must have the maximum achievable fitness. Argue that your

2

fitness function works. Hints: (1) treat solutions that fit in the knapsack differently than those

that do not fit, (2) there should be pressure toward taking more items with bigger value as long

as the capacity is not exceeded, (3) there should be pressure to take items of smaller size if

capacity is exceeded.

c) Implement and incorporate the proposed approach into your GA implementation.

d) Test the proposed approach on the following three instances of the knapsack problem:

(i) n = 50, C = 50, si = 2, vi = i.

(ii) n = 50, C = 50, si = i, vi = 1.

(iii) n = 50, C = 50, si = 1, vi = 1.

Provide the results of your tests, which should consist of three things:

• Settings used in the GA to solve the problem (crossover method, pc, pm, N). It’s up to you

what parameters and operators you use, but you should try to make it work and reliably

find the global optimum in all test cases.

• The number of evaluations until the solution was found.

• The optimal selection of items (can describe in words).

Kemahiran: Kajian Saintifik

Tentang Majikan:
( 3 ulasan ) St Charles, United States

ID Projek: #1554116