4

I use ga (matlab optimization tool) to solve the backpack problem. I wrote a simple fitness function with hardcoded weight-value array: 

function fitness = bp_fitness(x)

% This function computes the fitness value for the 0-1 knapsack problem
% x: The current chromosome
% max_capacity: maximum capacity of the knapsack
% items: a two-dimensional array that holds the weight and value
% of each item respectively.

items = [8 15;2 16;5 20; 1 5;13 50;10 35;3 14;4 17;12 40;7 25;
     6 10;18 65;15 50;11 34;9 12;14 20;8 16;19 70;13 30;6 10;
     43 1;18 65;15 50;31 24;3 16;24 42;8 16;21 4;30 10;6 10;
     8 15;2 16];

max_capacity = 350;

overalweight = sum(x*items(:,1));

if overalweight > max_capacity
    fitness = 0;
else
    fitness = -1*sum(x*items(:,2));
end

and everything works ok. The question is, how to apply penalty for chromosomes, that doesn't fit the backpack? I've found this:

n the case of the backpack problem, the penalty can be calculated by multiplying the weight above the limit by the highest possible value to weight ratio.

K = max(vi / wi ) + c penalty = K * max[∑(w x )−W;0]

but I don't know how to implement this formula correctly. I've tried:

if overalweight > max_capacity
    k = max(items(:,2)./items(:,1))+1;
    penalty = k * (overalweight - max_capacity);
    fitness = -1*(sum(x*items(:,2)) - penalty);
    fprintf('fit = %i\n',-1*fitness);
else
    fitness = -1*sum(x*items(:,2));
end

This way there's no difference in the optimization results between two functions at all, which makes me think I did something wrong. Hope someone can help me here.

user1691399
  • 69
  • 2
  • 7
  • It may be that you are getting on both cases a very optimized result and thats why you dont see any difference with or wihtout penalty – Ander Biguri Nov 24 '14 at 10:37
  • @AnderBiguri, so I need to change the items or parameters to see it? – user1691399 Nov 24 '14 at 12:04
  • 1
    Yes, it would be nice. Try to get some data that would fit badly and test with and without penalty. – Ander Biguri Nov 24 '14 at 12:11
  • @anonymous why did you bounty this question? As Ander mentioned above, it might very well be a problem with the data, not the code. As the OP hasn't been around for half a year, I doubt we'll get any data or information on why this code doesn't produce the correct results. You probably would've been better off asking about your own implementation, where you could provide data. – Adriaan Dec 09 '16 at 07:23
  • When I was in school, I remember trying to out optimize code in this regard. The issue with something like this is often that the compiler is so good that it optimizes both solutions to equal quality runtime machine code. – Sethmr Dec 15 '16 at 20:44

0 Answers0