我目前正在编写一个遗传算法来解决一个可以被认为类似于knapsack problem的问题,但区别因素是我在多个“卡车”上存储物品,它们的值/重要性基于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()完美地生成第一个“最适合”值。第二个和第三个值保持它们初始化为“population[0].fitness”的状态,并显示出来。
我试图改变育种结构,育种的选择标准,因为我相信如果没有包含不同值的染色体,它将保持初始化状态出于同样的原因,我也测试过使用更大的群体,所以我相信他们一定是我的代码有问题。
非常感谢您的帮助。
最佳答案
一。关于代码的注释。
你应该将min1
,min2
和min3
初始化为一个高于健身最大值的值,因为在Global.p.population[0].fitness
是人口中最适合的情况下,你将永远找不到第二个和第三个BEST,因为在这种情况下,没有一个人的健身度低于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对个体符合这个标准但是会有一些人你找不到他们,大多数人你会找到他们。
随着基因数量的增加,这一比例下降每次你在染色体上加一个基因,你就要乘以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%左右。
所以问题是在一个种群中,没有足够的个体对符合这个标准。
三。另一种设计算法的方法。
在你的算法中,你似乎把一个人看作一辆卡车我会用另一种方法设计算法。
我会考虑将一个基因作为一个项目的卡车编号,如果需要,
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中。
因此,在不比较基因的情况下选择第二和第三好的个体是可能的,只需检查适应度。
关于c# - 基于重量和值(value)的遗传算法可将 cargo 存储在3辆卡车中,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40385398/