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:
• 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.
Similarly as in the first problem, your task consists of the following subtasks:
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
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
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).
1 pekerja bebas membida secara purata $90 untuk pekerjaan ini
PhD Candidate in Computer Science. Experience in various optimization algorithms. I'll provide working code and report to answer to all questions that you've stated in Project description.