我正在实现我心爱的“遗传算法”。很明显,在每次选择,交叉和突变后,种群数量大量增加。但是生物也死亡,对吗?但是,算法中没有我们都知道的此类规定。
所以,我的问题是,为什么我们不简单地从种群本身中消除某些适应性较低的生物(并同时合并适者论的生存)?为什么要承担他们的负担并浪费资源(在我们的案例中是记忆)?
[此外,我的所有想法都是基于Peter Norvig的AI书中给出的算法的3页说明,所以也许我的问题已经得到解决。我需要了解这些情况。
另外,这是我在这个平台上的第一个问题,社区,请不要对我严厉!
通过设计,遗传算法通过根本不包括后代的基因来消除集合中最弱的解决方案。
摘要:假设算法正在选择为下一代选择,组合和变异的解决方案。每个解决方案都放在飞镖板上,但是更好的解决方案会在飞镖板上占用更多空间,因此,当算法将飞镖扔掉时,就更有可能打出更合适的解决方案。实际上,它甚至可能多次击中相同的解决方案。
一旦它从飞镖板上获得其解决方案集(通常与原始设置相同,但是可能包含多个击中相同解决方案的飞镖的重复项),请采用此设置,并通过随机切换零件来“突变”它们解决方案。然后,您可以在一个非常性感的过程中“配对”解决方案,在该过程中,您将新一代中的随机解决方案的一部分纳入其中,并将它们组合成最终的一代集。
然后重复此过程。
没有飞镖击中的解决方案会发生什么?这完全取决于您的语言和数据结构,但它们可能只是垃圾收集的对象。
ArrayList<Float> normalize(ArrayList<Float> inputArray){
float sum = 0;
ArrayList<Float> outputArray = new ArrayList<Float>();
for(int i = 0; i < inputArray.size(); i++){
sum += inputArray.get(i);
}
for(int i = 0; i < inputArray.size(); i++){
outputArray.add(inputArray.get(i)/sum);
}
return outputArray;
}
ArrayList<Float> pick(ArrayList<ArrayList> parents, ArrayList<Float> fitness){
float searchVal = random(0, 1);
float fitTotal = 0;
int fitIndex = 0;
while(searchVal > fitTotal && fitIndex < fitness.size()){
fitTotal += fitness.get(fitIndex);
fitIndex++;
}
if(fitIndex != 0){
return parents.get(fitIndex-1);
}
else{
return parents.get(0);
}
}
此代码包含两种方法;归一化方法和挑选方法。
normalize方法采用每个解决方案的适应度,然后将其“规范化”为一个数组,其中每个适应度除以总数。这将导致每个适应性水平占总数的百分比。它们全部加起来为一。
然后,pick方法将这个标准化数组与父级解决方案的数组一起使用(必须以适合水平的顺序在同一顺序中),并随机选择一个0-1,并且该数字将与特定的适应度匹配级别,算法将“拾取”要复制的父对象。
您会注意到,适用性水平较高的解决方案更有可能被“挑选”
对于下一代想要的每种生物,都应重复这种“拾取”方法。
OP提到他们了解飞镖板的类比,并想知道将不良品完全从飞镖板上清除是否有用。首先,挑选不良后代的机会很小,但是像这样的手动修剪也可以。
我可以看到,当您不希望拥有解决方案的非常糟糕的特征,并且不希望将它们放入下一个集合时,这很有用。