CODEWITHSUNDEEP
algorithmdynamic-programmingcomputer-sciencegenetic-algorithmknapsack-problem
dalglish
dalglish

Reputation: 63

Is it better to use genetic algorithm to solve the 0-1 Knapsack problem?

The Knapsack problem is a combinatorial optimization problem where one has to maximize the bene t of objects in a knapsack without exceeding its capacity. We know that there are many ways to solve this problem, genetic algorithm, dynamic programmming, and greedy method. I want to know what is the advantage and disadvantage to use the genetic algorithm comparing with dynamic programming? Space complexity, time complexity, and optimality?

Upvotes: 2

Views: 953

Answers (1)

artemis
artemis

Reputation: 7281

So in order to answer this, it is important to consider what you think is the most important: Speed or Accuracy

Genetic algorithms do not guarantee finding the most optimal solution, however, they typically run very quickly.

Some quick descriptions of a Genetic Algorithm might yield:

  • It is an estimation function and does not guarantee finding the globally optimal solution
  • It typically runs very fast (both in memory usage and complexity)
  • Actual calculations are hard, since genetic algorithms are typically problem specific and chaotic in nature. A good base for what its complexity might look like: O( O(Fitness) * (O(mutation) + O(crossover)))

However, Dynamic Programming does guarantee to find the most optimal solution, granted with a much longer run time. Some quick descriptions of Dynamic Programming might yield:

  • It is an exact function -- guarantees convergence on the most globally optimal solution
  • High memory usage and a very long run time
  • Complexity for knapsack 01 problem is something like: O(numItems * knapsackCapacity), and memory complexity like O(knapsackCapacity) (credits to this post for that)

If you are asking what is preferred, that is subject specific. If you want a good enough guess quickly, GA is probably the way to go. But if you need a guaranteed and verifiable solution, DP is the way to go.

This should satisfy a basic comparison.

Upvotes: 3

Related Questions