遗传算法中多个孩子的繁殖父母

Question

我正在使用一系列教程，用 javascript 构建我的第一个遗传算法。

我正在为本调度教程构建一个稍微简单的结构 http://www.codeproject .com/KB/recipes/GaClassSchedule.aspx#Chromosome8，但我遇到了育种问题。

我有 60 个个体，现在我选择前两个个体进行繁殖，然后随机选择一些其他个体与前两个个体进行繁殖，我最终不会得到相当少量的父母吗相当快？

我认为，如果我将前两个结果与接下来的 20 个结果中的每一个相乘，我不会在解决方案中取得太大进展。

这是正确的吗？有没有普遍接受的方法来做到这一点？

Answer 1

我在 此处 有一个 Javascript 遗传算法示例。

您的方法的一个问题是，您总是通过将前 2 个个体交配来扼杀种群的多样性。这永远不会很好，因为它太贪婪，而且你实际上一开始就违背了遗传算法的目的。

就是我实现与精英主义交配的方式（这意味着我保留一定比例的未改变的最适合个体并随机交配所有其余个体），我将让代码来说话：

// save best guys as elite population and shove into temp array for the new generation
for(var e = 0; e < ELITE; e++) {
   tempGenerationHolder.push(fitnessScores[e].chromosome); 
}

// randomly select a mate (including elite) for all of the remaining ones
// using double-point crossover should suffice for this silly problem
// note: this should create INITIAL_POP_SIZE - ELITE new individualz
for(var s = 0; s < INITIAL_POP_SIZE - ELITE; s++) {
   // generate random number between 0 and INITIAL_POP_SIZE - ELITE - 1
   var randInd = Math.floor(Math.random()*(INITIAL_POP_SIZE - ELITE));

   // mate the individual at index s with indivudal at random index
   var child = mate(fitnessScores[s].chromosome, fitnessScores[randInd].chromosome);

   // push the result in the new generation holder
   tempGenerationHolder.push(child);
}

这 评论得相当好，但如果您需要任何进一步的指导，请询问（这里是 github 存储库，或者您可以在上面的 url 上查看源代码）。我多次使用这种方法（精英主义），对于基本场景，它通常效果很好。

希望这有帮助。

Answer 2

当我过去实现遗传算法时，我所做的就是总是概率性地选择父母 - 也就是说，你不一定会选择获胜者，但你会根据更好的程度来选择获胜者的概率他们比其他人都好（基于适应度函数）。

我不记得支持它的论文的名称，但有一个数学证明，“排名”选择比“比例”选择收敛得更快。如果您尝试查找“遗传算法选择策略”，您可能会发现一些相关内容。

编辑：
更具体地说，既然pedalpete问了，有两种选择算法：一种基于排名，一种基于适应度比例。考虑具有 6 个解决方案和以下适应度值的群体：

Solution   Fitness Value
A          5
B          4
C          3
D          2
E          1
F          1

在排名选择中，您将采用前 k 个（例如 2 或 4）并将它们用作下一代的父母。在比例排名中，为了形成每个“孩子”，您可以根据适应度值随机选择父母：

Solution   Probability
A          5/16
B          4/16
C          3/16
D          2/16
E          1/16
F          1/16

在此方案中，F可能最终成为下一代的父母。如果群体规模较大（例如 100 - 可能更大或更小，具体取决于搜索空间），这意味着底部解决方案有时将成为父解决方案。这没关系，因为即使是“糟糕”的解决方案也有一些“好的”方面。

Answer 3

保持绝对适应的个体被称为精英主义，它确实往往会导致更快的收敛，这可能是也可能不是你想要的，这取决于问题的适应度情况。如果更快的收敛可以减少寻找可接受的解决方案所需的工作量，那么它是好的，但如果这意味着您最终会得到局部最优值并忽略更好的解决方案，那么它就很糟糕。

完全随机选择其他父母的效果不会很好。您需要某种机制，使更适合的候选人比较弱的候选人更有可能被选择。您可以使用多种不同的选择策略，每种策略都有不同的优点和缺点。 此处描述了一些主要内容。通常，您将使用轮盘赌选择或锦标赛选择。

至于将精英个体与其他父母中的每一位结合起来，这是破坏种群变异的一个方法（以及消除先前保存的最佳候选者）。

如果你采用精英主义，保持精英个体不变（这就是精英主义的要点），然后将其他父母配对（可能包括也可能不包括部分或全部精英个体，具体取决于他们是否也被选为父母）通过选择策略）。每个父母只会交配一次，除非它被选择策略多次挑选出来。

Answer 4

您的方法可能会受到过早收敛的影响。不过，还有许多其他选择技术可供选择。您可能希望考虑的更流行的方法之一是锦标赛选择。

不同的选择策略提供不同程度的“选择压力”。选择压力是指策略坚持选择最佳计划的强度。如果每次都选择绝对最佳的程序，那么您的算法实际上就成为爬山者；它将陷入局部最优，无法导航到健身景观中的其他峰值。另一方面，完全没有适应度压力意味着算法将盲目地随机地在适应度景观中跌跌撞撞。因此，面临的挑战是尝试为您正在解决的问题选择一个具有足够（但不过大）选择压力的操作员。

锦标赛选择运算符的优点之一是，只需修改锦标赛的规模，您就可以轻松调整选择压力的水平。较大的比赛会带来更大的压力，较小的比赛会带来更少的压力。