根据重量和价值将物品存储在 3 辆卡车中的遗传算法
Genetic Algorithm to store Items in 3 trucks, based on weight and value
我目前正在编写一个遗传算法来解决一个可以被认为类似于 knapsack problem 的问题，但不同之处在于我将项目存储在多个 "trucks" 上，它们的 value/importance 基于 1 = 最重要，3 = 最不重要。
我是如何使用二进制整数数组来执行此操作的，0 = 不在卡车上，1 = 在卡车上。
在大多数情况下，程序似乎在做它需要做的事情。除了当我比较染色体以找到每一代最好的三个个体染色体时。个人是没有染色体可以包含相同的项目，因为该项目一次只能在一辆卡车上。
这是我用来比较染色体的函数：
private int[] getBestSolution(int count)
{
int[] Genes = new int[3];
int min1 = Global.p.population[0].fitness;
int min2 = Global.p.population[0].fitness;
int min3 = Global.p.population[0].fitness;
int ref1 = 0;
int ref2 = 0;
int ref3 = 0;
bool areSame = true;
//searches for the first "Fittest" chromosome and stores to ref1
for (int i = 0; i < Global.population; i++)
{
if (min1 > Global.p.population[i].fitness)
{
min1 = Global.p.population[i].fitness;
ref1 = i;
}
}
//searches for 2nd fittest, while also checking they are different
for (int i = 0; i < Global.population; i++)
{
areSame = arrayCompare(Global.p.population[ref1].chromosome, Global.p.population[i].chromosome);
if(areSame == true)
{
continue;
}
if (min2 > Global.p.population[i].fitness)
{
min2 = Global.p.population[i].fitness;
ref2 = i;
}
}
//Searches for 3rd fittest while checking that it is different from the first two
for (int i = 0; i < Global.population; i++)
{
areSame = arrayCompare(Global.p.population[ref1].chromosome, Global.p.population[i].chromosome);
if (areSame == true)
{
continue;
}
areSame = arrayCompare(Global.p.population[ref2].chromosome, Global.p.population[i].chromosome);
if(areSame == true)
{
continue;
}
if (min3 > Global.p.population[i].fitness)
{
min3 = Global.p.population[i].fitness;
ref3 = i;
}
}
//stores the reference of each chromosome and return
Genes[0] = ref1;
Genes[1] = ref2;
Genes[2] = ref3;
return Genes;
}
这是我用来将染色体与之前选择的染色体进行比较以确保它们不包含相同值的函数。
public bool arrayCompare(int[] a, int[] b)
{
for (int i = 0; i < a.Length; i++)
{
if ((a[i] == 1) && b[i] == 1)
{
return true;
}
}
return false;
}
我通过在代码的不同点使用断点并检查值是什么与预期值是什么，将问题缩小到导致问题的这两个函数。
最后，回到问题本身。 getBestSolution() 完美地生成第一个 "fittest" 值。第二个和第三个值保持为它们初始化为 "population[0].fitness" 的值并显示。
我试图改变育种结构，育种的选择标准，因为我相信如果没有包含不同值的染色体，它将保持初始化状态。出于同样的原因，我也测试过使用更大的人口，所以我相信他们一定是我的代码有问题。
非常感谢任何帮助。
1。关于您的代码的注释。
您应该将 min1、min2 和 min3 初始化为高于适应度最大值的值，因为在这种情况下 Global.p.population[0].fitness 是种群中最好的适应度，你永远找不到第二和第三好的，因为在这种情况下，没有人的适应度低于 Global.p.population[0].fitness.
2。您正在使用的基因的概率。
我可能是错的，但这是我对你描述的问题的理论。
在随机分布中，对于 1 个基因，两个个体的基因值共有 4 种可能的组合。在这 4 种组合中，有 3 种组合中两个人没有共同的基因集 1。
Individual 1 Individual 2 Match criterion Probability
Combination 1: 0 0 Yes 25% |
Combination 2: 0 1 Yes 25% | 75%
Combination 3: 1 0 Yes 25% |
Combination 4: 1 1 No 25%
这意味着对于只有一个基因的个体，你有75%的机会找到两个符合条件的个体。换句话说，如果你比较 100 个个体的基因，你会发现平均有 75 对个体符合标准。但是会有一些人群您找不到它们，而大多数人群您会找到它们。
随着基因数量的增加，百分比会下降。每次向染色体添加 1 个基因时，您必须将符合标准的个体百分比乘以 75/100。每次加2个基因，都要乘以56,25/100的百分比。
Number of genes percentage of individuals matching the criterion
1 75,00%
2 56,25% = 75,00 * 75,00 / 100
4 31,64% = 56,25 * 56,25 / 100
6 17,79% = 31,64 * 56,25 / 100
8 10,01% = 17,79 * 56,25 / 100
[...]
16 1%
表示16条基因的染色体，100人的群体，平均有1对符合条件的个体。如果您想要 3 个人符合标准，则百分比会更小。对于6个基因，找到这3个个体的概率应该在1.5%左右。
所以问题是在总体中，没有足够多的个体对符合标准。
3。另一种设计算法的方法。
在您的算法中，您似乎将个人视为卡车。我会用另一种方式设计算法。
我会将基因视为物品的卡车编号，如果需要，0 表示该物品没有指定的卡车：
gene[0] = 1 (item 0 is in truck 1)
gene[1] = 0 (item 1 is not in any truck)
gene[2] = 3 (item 2 is in truck 3)
gene[3] = 2 (item 3 is in truck 2)
gene[4] = 1 (item 4 is in truck 1)
通过这种信息编码，第二和第三好的人可以比最好的人在同一辆卡车上拥有一件物品。例如：
first best individual:
----------------------
truck1: item1 item2
truck2: item3 item4
truck3: item5 item6 item7
not in any truck: item0
second best individual:
-----------------------
truck1: item1 item3
truck2: item2 item5
truck3: item4 item6
not in any truck: item0 item7
在此示例中，item1 始终在 truck1 中，item6 始终在 truck3 中。
所以可以select第二和第三好的个体不比较基因，只检查适应度
我目前正在编写一个遗传算法来解决一个可以被认为类似于 knapsack problem 的问题，但不同之处在于我将项目存储在多个 "trucks" 上，它们的 value/importance 基于 1 = 最重要，3 = 最不重要。
我是如何使用二进制整数数组来执行此操作的，0 = 不在卡车上，1 = 在卡车上。
在大多数情况下，程序似乎在做它需要做的事情。除了当我比较染色体以找到每一代最好的三个个体染色体时。个人是没有染色体可以包含相同的项目，因为该项目一次只能在一辆卡车上。
这是我用来比较染色体的函数：
private int[] getBestSolution(int count)
{
int[] Genes = new int[3];
int min1 = Global.p.population[0].fitness;
int min2 = Global.p.population[0].fitness;
int min3 = Global.p.population[0].fitness;
int ref1 = 0;
int ref2 = 0;
int ref3 = 0;
bool areSame = true;
//searches for the first "Fittest" chromosome and stores to ref1
for (int i = 0; i < Global.population; i++)
{
if (min1 > Global.p.population[i].fitness)
{
min1 = Global.p.population[i].fitness;
ref1 = i;
}
}
//searches for 2nd fittest, while also checking they are different
for (int i = 0; i < Global.population; i++)
{
areSame = arrayCompare(Global.p.population[ref1].chromosome, Global.p.population[i].chromosome);
if(areSame == true)
{
continue;
}
if (min2 > Global.p.population[i].fitness)
{
min2 = Global.p.population[i].fitness;
ref2 = i;
}
}
//Searches for 3rd fittest while checking that it is different from the first two
for (int i = 0; i < Global.population; i++)
{
areSame = arrayCompare(Global.p.population[ref1].chromosome, Global.p.population[i].chromosome);
if (areSame == true)
{
continue;
}
areSame = arrayCompare(Global.p.population[ref2].chromosome, Global.p.population[i].chromosome);
if(areSame == true)
{
continue;
}
if (min3 > Global.p.population[i].fitness)
{
min3 = Global.p.population[i].fitness;
ref3 = i;
}
}
//stores the reference of each chromosome and return
Genes[0] = ref1;
Genes[1] = ref2;
Genes[2] = ref3;
return Genes;
}
这是我用来将染色体与之前选择的染色体进行比较以确保它们不包含相同值的函数。
public bool arrayCompare(int[] a, int[] b)
{
for (int i = 0; i < a.Length; i++)
{
if ((a[i] == 1) && b[i] == 1)
{
return true;
}
}
return false;
}
我通过在代码的不同点使用断点并检查值是什么与预期值是什么，将问题缩小到导致问题的这两个函数。
最后，回到问题本身。 getBestSolution() 完美地生成第一个 "fittest" 值。第二个和第三个值保持为它们初始化为 "population[0].fitness" 的值并显示。
我试图改变育种结构，育种的选择标准，因为我相信如果没有包含不同值的染色体，它将保持初始化状态。出于同样的原因，我也测试过使用更大的人口，所以我相信他们一定是我的代码有问题。
非常感谢任何帮助。
1。关于您的代码的注释。
您应该将 min1、min2 和 min3 初始化为高于适应度最大值的值，因为在这种情况下 Global.p.population[0].fitness 是种群中最好的适应度，你永远找不到第二和第三好的，因为在这种情况下，没有人的适应度低于 Global.p.population[0].fitness.
2。您正在使用的基因的概率。
我可能是错的，但这是我对你描述的问题的理论。
在随机分布中，对于 1 个基因，两个个体的基因值共有 4 种可能的组合。在这 4 种组合中，有 3 种组合中两个人没有共同的基因集 1。
Individual 1 Individual 2 Match criterion Probability
Combination 1: 0 0 Yes 25% |
Combination 2: 0 1 Yes 25% | 75%
Combination 3: 1 0 Yes 25% |
Combination 4: 1 1 No 25%
这意味着对于只有一个基因的个体，你有75%的机会找到两个符合条件的个体。换句话说，如果你比较 100 个个体的基因，你会发现平均有 75 对个体符合标准。但是会有一些人群您找不到它们，而大多数人群您会找到它们。
随着基因数量的增加，百分比会下降。每次向染色体添加 1 个基因时，您必须将符合标准的个体百分比乘以 75/100。每次加2个基因，都要乘以56,25/100的百分比。
Number of genes percentage of individuals matching the criterion
1 75,00%
2 56,25% = 75,00 * 75,00 / 100
4 31,64% = 56,25 * 56,25 / 100
6 17,79% = 31,64 * 56,25 / 100
8 10,01% = 17,79 * 56,25 / 100
[...]
16 1%
表示16条基因的染色体，100人的群体，平均有1对符合条件的个体。如果您想要 3 个人符合标准，则百分比会更小。对于6个基因，找到这3个个体的概率应该在1.5%左右。
所以问题是在总体中，没有足够多的个体对符合标准。
3。另一种设计算法的方法。
在您的算法中，您似乎将个人视为卡车。我会用另一种方式设计算法。
我会将基因视为物品的卡车编号，如果需要，0 表示该物品没有指定的卡车：
gene[0] = 1 (item 0 is in truck 1)
gene[1] = 0 (item 1 is not in any truck)
gene[2] = 3 (item 2 is in truck 3)
gene[3] = 2 (item 3 is in truck 2)
gene[4] = 1 (item 4 is in truck 1)
通过这种信息编码，第二和第三好的人可以比最好的人在同一辆卡车上拥有一件物品。例如：
first best individual:
----------------------
truck1: item1 item2
truck2: item3 item4
truck3: item5 item6 item7
not in any truck: item0
second best individual:
-----------------------
truck1: item1 item3
truck2: item2 item5
truck3: item4 item6
not in any truck: item0 item7
在此示例中，item1 始终在 truck1 中，item6 始终在 truck3 中。
所以可以select第二和第三好的个体不比较基因，只检查适应度