Solving the 0–1 Knapsack problem using Genetic Algorithm and Rough Set Theory

This paper describes a hybrid algorithm to solve the 0–1 Knapsack Problem using the Genetic Algorithm combined with Rough Set Theory. The Knapsack problem is a combinatorial optimization problem where one has to maximize the benefit of objects in a knapsack without exceeding its capacity. There are other ways to solve this problem, namely Dynamic Programming and Greedy Method, but they are not very efficient. The complexity of Dynamic approach is of the order of O(n
³
) whereas the Greedy Method doesn't always converge to an optimum solution
^[2]
. The Genetic Algorithm provides a way to solve the knapsack problem in linear time complexity
^[2]
. The attribute reduction technique which incorporates Rough Set Theory finds the important genes, hence reducing the search space and ensures that the effective information will not be lost. The inclusion of Rough Set Theory in the Genetic Algorithm is able to improve its searching efficiency and quality.