algorithm - 遺伝的アルゴリズムによるバックパック (ナップザック)。フィットネス機能にペナルティを追加する方法

Question

ga (matlab 最適化ツール) を使用して、バックパックの問題を解決します。ハードコーディングされた重み値配列を使用して、単純なフィットネス関数を作成しました。

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

すべてが正常に動作します。問題は、バックパックに収まらない染色体にペナルティを適用する方法です。私はこれを見つけました：

バックパックの問題の場合、ペナルティは、制限を超える重量に重量比に対する可能な最大値を掛けることによって計算できます。

K = max(vi / wi ) + c ペナルティ = K * max[∑(wx )−W;0]

しかし、この式を正しく実装する方法がわかりません。私はもう試した：

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

この方法では、2 つの関数間で最適化の結果に違いがまったくないため、何か間違ったことをしたと思います。誰かがここで私を助けてくれることを願っています。