Styjun

Incremental Ranges!

Is it legal in the UK for politicians to lie to the public for political gain?

How to skip replacing first occurrence of a character in each line?

Accidentally renamed tar.gz file to a non tar.gz file, will my file be messed up

Did Darth Vader wear the same suit for 20+ years?

Finding x,y coordinates where y is largest

Importance sampling estimation of power function

How would you say “AKA/as in”?

Why don’t airliners have temporary liveries?

How can I instantiate a lambda closure type in C++11/14?

PhD student with mental health issues and bad performance

Does an ice chest packed full of frozen food need ice? 18 day Grand Canyon trip

Does the first version of Linux developed by Linus Torvalds have a GUI?

Is there any word or phrase for negative bearing?

How to supress loops in a digraph?

What is the purpose of building foundations?

C SIGINT signal in Linux

Payment instructions from HomeAway look fishy to me

How bad would a partial hash leak be, realistically?

Who operates delivery flights for commercial airlines?

Why is the relationship between frequency and pitch exponential?

Smooth switching between 12v batteries, with toggle switch

Is the decompression of compressed and encrypted data without decryption also theoretically impossible?

Secure offsite backup, even in the case of hacker root access

Evaluation function for modified knapsack problem

Forming Dynamic Programming algorithm for a variation of Knapsack ProblemOptimal way of filling 2 knapsacks?Bounded knapsack special case - small individual item weight is small compared to the number of itemsKnapsack algorithm for two bags1/0 Knapsack Variation with Weighted EdgesGetting object list in KnapsackVariant of KnapsackUnderstanding knapsack solutionResource Allocation Optimization - Variation of Multiple KnapsackIs there an algorithm that can solve this variation of the Knapsack Problem?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;

0

I'm trying to solve a modified version of the knapsack problem using a hill climbing algorithm, but I can't find a good evaluation function. In this version of the knapsack problem the sum of the weights of all objects in the solution must be equal (not <=) to the knapsack's capacity and the sum of their costs must be maximized.

I've tried several evaluation functions but none of them worked:

1. I've tried to minimize the expression __abs(sum_of_weights_in_solution - knapsack's capacity)__. Obviously it didn't work because this expression does't take into account the object's costs, but at least it provides a solution which fills the knapsack
   


2. I've tried to minimize this expression: __abs(sum_of_weights_in_solution - knapsack's capacity) - sum_of_costs_in_solution__. This one is better but still it doesn't always find the optimal solution even after 10^6 iterations on a knapsack with 10 objects, and I think that's because I can't really treat the cases where the sum of the weights of objects is > than the knapsack's capacity

artificial-intelligence knapsack-problem hill-climbing

share|improve this question

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  This is a rather incomplete description. It's a heuristic, of course a lot can go wrong in terms of your solutions. You did not specify your moves or whatever is being done inbetween evaluations. I don't get your reasoning: your objective treats both directions of error but of course the direction-information is lost in the pure objective. Who knows how you generate your moves. Where does the expectation of reaching a global opt come from? It's a non-convex prob and pure hill-climbing sounds like local-optimization (again related a lot to your moves).
  
  – sascha
  Mar 24 at 15:53
  
  

  
  
  
  

add a comment | 

0

I'm trying to solve a modified version of the knapsack problem using a hill climbing algorithm, but I can't find a good evaluation function. In this version of the knapsack problem the sum of the weights of all objects in the solution must be equal (not <=) to the knapsack's capacity and the sum of their costs must be maximized.

I've tried several evaluation functions but none of them worked:

1. I've tried to minimize the expression __abs(sum_of_weights_in_solution - knapsack's capacity)__. Obviously it didn't work because this expression does't take into account the object's costs, but at least it provides a solution which fills the knapsack
   


2. I've tried to minimize this expression: __abs(sum_of_weights_in_solution - knapsack's capacity) - sum_of_costs_in_solution__. This one is better but still it doesn't always find the optimal solution even after 10^6 iterations on a knapsack with 10 objects, and I think that's because I can't really treat the cases where the sum of the weights of objects is > than the knapsack's capacity

artificial-intelligence knapsack-problem hill-climbing

share|improve this question

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  This is a rather incomplete description. It's a heuristic, of course a lot can go wrong in terms of your solutions. You did not specify your moves or whatever is being done inbetween evaluations. I don't get your reasoning: your objective treats both directions of error but of course the direction-information is lost in the pure objective. Who knows how you generate your moves. Where does the expectation of reaching a global opt come from? It's a non-convex prob and pure hill-climbing sounds like local-optimization (again related a lot to your moves).
  
  – sascha
  Mar 24 at 15:53
  
  

  
  
  
  

add a comment | 

I'm trying to solve a modified version of the knapsack problem using a hill climbing algorithm, but I can't find a good evaluation function. In this version of the knapsack problem the sum of the weights of all objects in the solution must be equal (not <=) to the knapsack's capacity and the sum of their costs must be maximized.

I've tried several evaluation functions but none of them worked:

1. I've tried to minimize the expression __abs(sum_of_weights_in_solution - knapsack's capacity)__. Obviously it didn't work because this expression does't take into account the object's costs, but at least it provides a solution which fills the knapsack
   


2. I've tried to minimize this expression: __abs(sum_of_weights_in_solution - knapsack's capacity) - sum_of_costs_in_solution__. This one is better but still it doesn't always find the optimal solution even after 10^6 iterations on a knapsack with 10 objects, and I think that's because I can't really treat the cases where the sum of the weights of objects is > than the knapsack's capacity

artificial-intelligence knapsack-problem hill-climbing

share|improve this question

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

share|improve this question

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

share|improve this question

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

edited Mar 24 at 14:55

Gilles Heinesch

1,3921824

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11

asked Mar 24 at 14:42

Geo BaditaGeo Badita

11