複数の内側のナップザックとフィットネスの計算

Question

私の頭を傷つけると間違っているかもしれません。

基本的にはナップザック問題ですが、修正されました。いろいろな重量のアイテムがセットに入っています。あなたは3つのナップザックに20個の容量を入れなければなりません。

私はすべての項目を袋にランダムに初期化するコードを持っています。つまり、私は20以上20未満20と等しい袋を持つことができます。問題は、アイテムがすべて追加されているので、私の合計得点はすべての人口で同じですので、変異することは不可能です。例えば

、

• KnapsackA 1つのスコア= 72
• KnapsackA 2スコア= 50
• KnapsackA 3スコア= 10

Iは、4つの集団を持っている場合、その手段ゲノムの他のオブジェクトには、ナップザックの間に異なるスコアのようなナップザックがありますが、合計は同じになります。

• KnapsackB 1つのスコア= 80
• KnapsackB 2スコア= 18
• KnapsackB 3スコア= 34

私はちょうど私がランダムにランダムに生成するコードを実行することができるという考えを持っていました初期化ではなく第1世代のアイテムを再割り当てするための番号ですが、間違っている可能性もあります。 。

私は一番低いゲノムを削除して残りのものを突然変異させることができるように、ユニークなスコア（フィットネスの評価）を計算するにはどうすればよいですか？

スコアの容量は常に同じです。

（他のフォーラムでのxポスト）

Answer 1

は商品のナップザックの外にあることを可能にするために、情報の異なる符号化を使用することができます。例えば、私はアイテムを示すために、ナップザック項目の数、及び0として遺伝子を検討する

任意ナップザックではない：

gene[0] = 1 (item 0 is in knapsack 1) 
gene[1] = 0 (item 1 is not in any knapsack) 
gene[2] = 3 (item 2 is in knapsack 3) 
gene[3] = 2 (item 3 is in knapsack 2) 
gene[4] = 1 (item 4 is in knapsack 1) 

だから個人が3のための可能な解決策を表しますナップザック。そしてあなたは、例えば、人口100人を持つことができます。

この情報のコード化によって、突然変異および再生の計算は容易である。

遺伝子を突然変異させるには、[0,3]の範囲の乱数である新しい値を割り当てなければなりません。例えば、突然変異アルゴリズムは：

n = number of genes 
mutation_rate = 0.01 // it means a mutation rate of 1% 
For i from 0 to n-1 
    r = random real number between 0.0 and 1.0 
    If(r < mutation_rate) 
    gene[i] of new individual = (random integer number) modulo 4 
    Else 
    gene[i] of new individual = gene[i] of original individual 
    EndIf 
EndFor 

あなたが再生を実現したい場合は、単に最初の個々の遺伝子の半分、及び第二の個別の遺伝子の反対の半分を選択する必要があります。

n = number of genes 
For i from 0 to n-1 
    r = random integer number 
    If(r modulo 2 == 0) 
    gene[i] of new individual = gene[i] of first individual 
    Else 
    gene[i] of new individual = gene[i] of second individual 
    EndIf 
EndFor 

あなたは、より効率的に最初に計算することよりも、子供を2人の突然変異した子どもたちを計算し、それを変異させるためには、ひとつのパッケージ内に2つの先例アルゴリズムを組み合わせることができます。

私はフィットネス機能の専門家ではありませんが、あなたは次のものからインスピレーションを受けることができます。これは非常に基本的なものであり、ナップザックを可能な限り埋める必要があるという事実を考慮してください。この適応度関数の場合は、フィットネスの高い値は、より良いソリューションです：

n = number of genes 

fitness = 0 

weight_noknapsack = 0 
weight_knapsack1 = 0 
weight_knapsack2 = 0 
weight_knapsack3 = 0 

For i from 0 to n-1 
    Switch gene[i] 

    case 0: weight_noknapsack += item[i].weight 

    case 1: weight_knapsack1 += item[i].weight 

    case 2: weight_knapsack2 += item[i].weight 

    case 3: weight_knapsack3 += item[i].weight 

    EndSwitch 
EndFor 

If(weight_knapsack1 <= MAX_WEIGHT_KNAPSACK1) 
    fitness += weight_knapsack1 
EndIf 
If(weight_knapsack2 <= MAX_WEIGHT_KNAPSACK2) 
    fitness += weight_knapsack2 
EndIf 
If(weight_knapsack3 <= MAX_WEIGHT_KNAPSACK3) 
    fitness += weight_knapsack3 
EndIf 

それはフィットネスを計算し、私はよりよい適応度関数があるかもしれないと思います。