title: Backpack (knapsack) by means of genetic algorithm. How to add penalty to the fitness func
body: <p>I use ga (matlab optimization tool) to solve the backpack problem. I wrote a simple fitness function with hardcoded weight-value array: </p>
  
  <pre><code>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 &gt; max_capacity
      fitness = 0;
  else
      fitness = -1*sum(x*items(:,2));
  end
  </code></pre>
  
  <p>and everything works ok. The question is, how to apply penalty for chromosomes, that doesn't fit the backpack? I've found this:</p>
  
  <blockquote>
    <p>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.</p>
    
    <p>K = max(vi / wi ) + c
    penalty = K * max[∑(w x )−W;0]</p>
  </blockquote>
  
  <p>but I don't know how to implement this formula correctly.
  I've tried:</p>
  
  <pre><code>if overalweight &gt; 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
  </code></pre>
  
  <p>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.</p>