Knapsack approximation algorithm6/11/2023 ![]() ![]() The best result was achieved for Large problems where our genetic algorithm achieved a score 4.4% higher on average than the approximation algorithm for knapsack instances of 50 items and a score 7.1% higher for knapsack instances of 10 items. In the interest of time we used /2 generations to approximate the results of the algorithm. In all three cases our algorithm beat popular greedy approximation algorithms as long as the number of generations was in the vicinity of where n is the number of items in the knapsack. We begin by defining a scope for the problem by diving knapsack problems into 3 categories: small items relative to weight (Small), large items relative to weight (Large), and both small and large items relative to weight (Mixed Bag). To extract relevant insights from our results, we narrowed down the domain of our problem. We used both an exact dynamic programming algorithm and the 2-Approximation Algorithm as benchmarks to measure our preformance and inform our design decisions. To achieve the best results, we designed our own genetic algorithm framework and tailored each part of the algorithm to meet our specific needs, using thousands of example problems to test our algorithm. Genetic algorithms are a good fit for combinatorial optimization problem, and thus for the 0-1 knapsack problem. If a genetic algorithm solution can match or exceed current approximation algorithms, current applications of the knapsack problem, such as efficient resource allocation, could be better solved using our algorithm. The task is important because the 0-1 knapsack problem lies in the set of problems with no known polynomial time solution. Our task is to generate approximation solutions to instances of the 0-1 knapsack problem based on improving generations in a genetic algorithm. tar.gz Project MembersĪditi Agarwal, Ronit Basu, Lukas Gross, Darren HwangĮECS 349 Northwestern University Abstract Approximation Algorithms on Knapsack 0-1 EECS 349 Final Project View on GitHub Download. Approximation Algorithms on Knapsack 0-1 Genetic Algorithms vs. ![]()
0 Comments
Leave a Reply. |