Sign in to follow this  

Knapsacks?

This topic is 3739 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi Really don't know how to put this simple but I give it a try. In my line of profession there exist a problem that very much resembles a knapsack problem that today are solved either manually or with some quite expensive tools that make static analysis of the problem. The knapsacks are equal in size. The gadgets to put in the knapsacks has a bunch of different properties such as size, priority and so on. In the end you want to minimize the number of sacks (almost true in this case) but still bring ALL the gadgets along. It is also nice to group gadgets by priority and other parameters. Just recently I figured that it might be possible use AI (or more specific GA) to solve this problem. What I look for here is any ideas/ suggestions around this quite vauge problem. Is GA suitable for solving a knapsacklike problem? Has it been done before? I appriciate any input. // Thanks // Javelin

Share this post


Link to post
Share on other sites
Genetic algorithms are suitable for almost any problem. Are they optimal... well, almost never. ;)

It would be very easy to develop a reasonable GA for this problem. First, devise a way of rating the fitness a candidate solution, eg. negative points for each sack used, positive points for grouping them, etc. Then work out how to implement the crossover and mutation operators, the former combining aspects of 2 solutions, the latter providing a modification on 1 solution. Then you're pretty much set.

However, the Wikipedia article indicates that there are other approaches, which I assume are more likely to be optimal, so I'd hesitate to recommend a GA approach if this is an important question.

Share this post


Link to post
Share on other sites
Grouping genetic algorithms are designed for exactly this sort of problem. They use specialized encodings and mutation operators to search the space of partitions of the items. They can be effective since once implemented it is easy to change around the objective function and constraints and they can find pretty good solutions for NP-hard problems.

Share this post


Link to post
Share on other sites

This topic is 3739 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this