2

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?

dalglish
  • 53
  • 5

1 Answers1

3

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.

artemis
  • 6,857
  • 11
  • 46
  • 99
  • If this answered your question, don't forget to mark it as correct to help other users :) – artemis Apr 24 '19 at 15:26
  • I am thinking that maybe a hybrid of Rough Sets and Genetic Algorithm can help find the optimal solution. Still not sure. – dalglish Apr 25 '19 at 04:28
  • @dalglish You're probably right, and I didn't really make an attempt to pseudocode either in this situation. In my experience, I have not found GA to reliably get me the optimal solution. So, in theory (academics) it usually does not work, but in practice, "close enough" is often times good enough so GAs are used quite often. It really depends on the scope of your problem, because a GA ***can*** result in the optimal solution, it is just not guaranteed. – artemis Apr 25 '19 at 11:32