News for hackers. Stuff that matters.
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.

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.

There are no comments on this comment yet.