Re:Genetic Algorithm for Knapsack Problem
by joakleaf on Wednesday June 19, 2013 @09:35AM
(#5905423)
In reality this is a subset sum problem (unless I overlooked weights on the appetizers).
Rather than using the GA for this, there are extremely efficient dynamic programming methods available (in pseudo-polynomial time). References on the Wikipedia page (https://en.wikipedia.org/wiki/Knapsack_problem).
Since GA is a metaheuristic, it is really great if you don't know how to tackle a problem more efficiently. But like most metaheuristics, not really an ideal method for optimization.
Rather than using the GA for this, there are extremely efficient dynamic programming methods available (in pseudo-polynomial time). References on the Wikipedia page (https://en.wikipedia.org/wiki/Knapsack_problem).
Since GA is a metaheuristic, it is really great if you don't know how to tackle a problem more efficiently. But like most metaheuristics, not really an ideal method for optimization.
To get a better visual sense of what GAs do wrong, take a look at: http://www.demo.cs.brandeis.edu/pr/buildable/crane/
You can see that the bridges and cranes have redundant bricks, are not straight, and just generally messy. However, GA gets the job done.
There is a lot of enthusiasm over GAs, but it is just a refined form of random search, and not that different from Simulated Annealing.