c# - 多重内背包及适应度计算

Question

在这个问题上摸不着头脑，我可能会认为它是错误的。

基本上是背包问题，但有所修改。你有一组不同重量的元素，你要将它们放在三个背包中，每个背包可容纳 20 个。

我有代码可以随机初始化麻袋中的所有元素。这意味着我可以有超过 20、少于 20 和等于 20 的袋子。问题是所有项目都被添加因此我的总分对所有人口都是相同的，因此不可能变异。

例如，

• KnapsackA 1 分 = 72
• KnapsackA 2 得分 = 50
• KnapsackA 3 分 = 10

如果我有四个人口，这意味着我会有其他带有背包的基因组对象，例如这些背包之间的分数不同，但总数将相同。

• KnapsackB 1 分 = 80
• KnapsackB 2 得分 = 18
• KnapsackB 3 得分 = 34

我只是想我可以运行一个代码来随机生成一个随机数来重新分配第一代的项目而不是在初始化时，但我也可能是错的。 .

我该如何计算一个独特的分数(评估适应度)，这样我就可以移除最低的基因组并在剩余的基因组上进行变异？

分数 - 容量始终是相同的数字。

(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

您可以将两个先例算法合二为一，以便比先计算一个 child 然后再对其进行变异更有效地计算两个个体的变异后代。

我不是健身功能方面的专家，但我认为您可以从以下内容中得到启发，这是非常基本的，只需考虑到背包必须尽可能多地装满这一事实。对于这个适应度函数，适应度值越高，解越好:

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

它计算适应度，但我认为可能有更好的适应度函数。