Abstract
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(n3) 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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of 2014 IEEE International Conference on Advanced Communication, Control and Computing Technologies, ICACCCT 2014 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 1120-1125 |
| Number of pages | 6 |
| ISBN (Electronic) | 9781479939145 |
| DOIs | |
| Publication status | Published - 23-01-2015 |
| Event | 2014 IEEE International Conference on Advanced Communication, Control and Computing Technologies, ICACCCT 2014 - Ramanathapuram, Tamil Nadu, India Duration: 08-05-2014 → 10-05-2014 |
Conference
| Conference | 2014 IEEE International Conference on Advanced Communication, Control and Computing Technologies, ICACCCT 2014 |
|---|---|
| Country/Territory | India |
| City | Ramanathapuram, Tamil Nadu |
| Period | 08-05-14 → 10-05-14 |
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications
- Control and Systems Engineering