Solving 0-1 Knapsack Problem using Genetic Algorithm

    4 Votes

The main goal of this project is to find a solution of 0-1 knapsack problem using  genetic algorithms. The 0-1 knapsack problem is a combinatorial optimization problem which seeks to maximize the benefit of objects in a knapsack without exceeding its capacity. Due to the nature of the problem it is not possible to use exact methods for large instances. Genetic algorithms provide efficient , effective techniques for optimization applications. In this project we use Genetic Algorithms to solve the 0-1 Knapsack problem where one has to maximize the benefit of objects in a knapsack without exceeding its capacity. Since the Knapsack problem is an NP problem, approaches such as dynamic programming, backtracking, branch and bound, etc. are not very useful for solving it. Genetic Algorithms definitely rule them all and prove to be the best approach in obtaining solutions to problems traditionally thought of as computationally in feasible such as the knapsack problem. 

Advantages And Disadvantages Of Using GA

Advantage of GA's is in their parallelism. GA is travelling in a search space with more individuals (and with genotype rather than phenotype) so they are less likely to get stuck in a local extreme like some other methods. They are also easy to implement. Once you have some GA, you just have to write new chromosome (just one object) to solve another problem. With the same encoding you just change the fitness function and it is all. On the other hand, choosing encoding and fitness function can be difficult. Disadvantage of GA's is in their computational time. They can be slower than some other methods. But with today’s computers it is not so big problem.

Knapsack Problem (KP)

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. It is not known how the name "knapsack problem" originated, though the problem was referred to as such in the early works of mathematician Tobias Dantzig suggesting that the name could have existed in folklore before a mathematical problem had been fully defined. The KP problem is an example of a combinatorial optimization problem, which seeks for a best solution from among many other solutions. It is concerned with a knapsack that has positive integer volume (or capacity) V. There are n distinct items that may potentially be placed in the knapsack. Item i has a positive integer volume Vi and positive integer benefit Bi. In addition, there are Qi copies of item i available, where quantity Qi is a positive integer satisfying 1 = Qi = 8. Let Xi determines how many copies of item i are to be placed into the knapsack. 

Feasibility Study

Genetic algorithms has been used for difficult problems (such as NP-hard problems), for machine learning and also for evolving simple programs. They have been also used for some art, for evolving pictures and music. Advantage of GAs is in their parallelism. GA is travelling in a search space with more individuals (and with genotype rather than phenotype) so they are less likely to get stuck in a local extreme like some other methods. They are also easy to implement. Once we have some GA, then we can write new chromosome (just one object) to solve another problem. With the same encoding we can just change the fitness function and it is all. On the other hand, choosing encoding and fitness function can be difficult. 

Economic Feasibility

The economic analysis is to determine the benefits and savings that are expected from a candidate system and compare them with costs. The system we have proposed is economically feasible, as the organization possesses the hardware and software resources required for the functioning of the system. Any additional resources, if required, can also be easily acquired. The cost of the proposed system is considerably very low.

Technical Feasibility

It centers on the existing computer system and to what extent it can support the proposed addition. We have used C++ programming language to implement our application. The main advantage of C++ include a clean object oriented approach. The minimum requirement of the proposed system includes 1,1MB of memory for the 1,000 item, and still less than 3,5MB for the 10,000 item problem sets. 

Operational Feasibility

The system operation is the longest phase in the development cycle of a system. So, This particular configuration is well suited for the 1,000 item test case, but may not be the best for other ones as there are more crossover techniques available in this implementation.

Behavioral Feasibility

Genetic Algorithms have shown to be well suited for high-quality solutions to larger NP problems and currently they are the most efficient ways for finding an approximately optimal solution for optimization problems. They do not involve extensive search algorithms and do not try to find the best solution, but they simply generate a candidate for a solution, check in polynomial time whether it is a solution or not and how good a solution it is. Genetic Algorithms do not always give the optimal solution, but a solution that is close enough to the optimal one.

Please go through the attached mini project report for more info.

Attachments:
Download this file (Solving  0-1 Knapsack Problem using Genetic Algorithm.pdf)Solving 0-1 Knapsack Problem using Genetic Algorithm[Mini Project Report]219 Kb

Popular Videos

communication

How to improve your Interview, Salary Negotiation, Communication & Presentation Skills.

Got a tip or Question?
Let us know

Related Articles

Travel Planner using Genetic Algorithm
Data Recovery and Undeletion using RecoverE2
PC CONTROLLED ROBOTIC CAR
Routino Router Algorithm
Data Leakage Detection
Scene Animation System Project
Data Structures and Algorithms Visualization Tool
Paint Program in C
Software Watermarking Project
Android Gesture Recognition
Internet working between OSI and TCP/IP Network Managements with Security Features Requirements
Web Image Searching Engine Using SIFT Algorithm
Remote Wireless Sensor Networks for Water Quality Monitoring Requirements
Ranking Spatial Data by Quality Preferences
Scalable Learning Of Collective Behaviour
Computational Metaphor Extraction And Interpretation
Designing a domain independent Rules Engine For Business Intelligence
Graph Colouring Algorithm
Gesture Based Computing
Facial Expression Detection