0

我正在尝试使用遗传算法 DLL解决DARP 问题。

问题是，尽管它有时会提出正确的解决方案，但有时却没有。尽管我使用了一个非常简单的问题版本。当我检查算法评估的基因组时，我发现它对同一个基因组进行了多次评估。

为什么它多次评估相同的值？如果不这样做会不会更有效率？

4

5 回答 5

2

对同一染色体进行两次评估与在一个群体（或不同群体）中多次使用同一染色体是有区别的。第一个可能可以有效地避免；第二个，也许不是。

考虑：

在某些一代 G1 中，您将 0011 和 1100 交配，将它们从中间穿过，幸运并且未能使任何基因发生突变，最终得到 0000 和 1111。您评估它们，将它们放回种群中以备下一个生成，并继续算法。

然后在一些较晚的 G2 代中，您在第一个索引处将 0111 和 1001 配对，并且（再次忽略突变）最终得到 1111 和 0001。其中一个已经被评估过，那么为什么要再次评估呢？特别是如果评估该函数非常昂贵，如果您负担得起内存，最好保留一个哈希表（或类似的）来存储先前评估的结果。

但！仅仅因为您已经为染色体生成了一个值，并不意味着您不应该将它自然地包含在未来的结果中，允许它进一步突变或允许它与同一种群的其他成员交配。如果你不这样做，你实际上是在惩罚成功，这与你想要做的完全相反。如果一条染色体代代相传或重新出现，这强烈表明它是一个很好的解决方案，如果它是局部最大值而不是全局最大值，一个精心挑选的变异算子将采取行动将其赶出。

于 2012-10-02T18:05:35.680 回答
1

为什么 GA 可能评估同一个人的基本解释正是因为它是非指导性的，因此重新创建以前看到（或同时看到）的基因组是可以预期的。

更有用的是，您的问题可以解释为两件不同的事情：

  1. 与评估适应度函数相关的高成本，可以通过对基因组进行散列来减轻，但要以内存为代价。这是可以想象的，但我从未见过。通常 GAs 搜索高维空间，所以你最终会得到一个非常稀疏的散列。

  2. 许多或所有成员都收敛到一个或几个模式的群体：在某些时候，你的基因组的多样性将趋于 0。这是预期的结果，因为算法已经收敛到它找到的最佳解决方案。如果这种情况发生得太早，结果平庸，则表明您陷入了局部最小值，并且您过早地失去了多样性。

在这种情况下，研究输出以确定发生了两种情况中的哪一种：

  1. 你失去了多样性，因为特别适合的人赢得了很大比例的父母彩票。或者，
  2. 你不会获得多样性，因为随着时间的推移，人口是相当静态的。

在前一种情况下，您必须保持多样性。确保不太适合的人获得更多机会，可能通过减少营业额或缩放适应度函数。

在后一种情况下，您必须增加多样性。确保您向种群注入更多的随机性，可能是通过增加突变率或增加营业额。

（当然，在这两种情况下，您最终确实希望随着 GA 在解决方案空间中收敛而减少多样性。所以您不只是想“调高所有刻度”并转移到蒙特卡洛搜索。）

于 2012-09-30T18:20:11.157 回答
0

根据您 GA 的具体情况，您可能在连续种群中拥有相同的基因组。例如，精英主义从每个种群中保存了最好的或n 个最好的基因组。

从计算的角度来看，重新评估基因组是低效的。避免这种情况的最简单方法是HasFitness为每个基因组放置一个布尔标志。您还可以为每个基因组编码创建一个唯一的字符串键，并将所有适应度值存储在字典中。此查找可能会变得非常昂贵，因此仅在您的适应度函数足够昂贵以保证查找的额外费用时才建议这样做。

于 2012-09-30T18:45:34.273 回答
0

撇开精英主义不谈，遗传算法不会重复评估同一个基因组。你所看到的是相同的基因组被再生和重新评估。这是因为每一代都是一组新的基因组，之前可能已经或可能没有被评估过。

为避免重新评估，您需要保留一份已产生的基因组列表及其适用性。要访问适合度，您需要将每个新人口与列表进行比较，当它不在列表中时，您需要对其进行评估，并将其添加到列表中。

由于现实世界的应用程序有数千个参数，因此您最终会存储数百万个基因组。然后，搜索和维护变得非常昂贵。所以每次只评估基因组可能会更快。

于 2012-10-09T14:32:15.100 回答
0

基本上遗传算法包括

  • 初始种群（大小 N）
  • 适应度函数
  • 变异操作
  • 交叉操作（通常对 2 个个体进行，通过提取他们基因组的某些部分并将其组合成新个体）

在每一步它

  1. 选择随机个体
  2. 执行交叉导致新个体
  3. 可能进行突变（改变随机个体中的随机基因）
  4. 使用适应度函数评估所有新旧个体
  5. 选择 N 最适合作为下一次迭代的新种群

算法在达到适应度函数的阈值时停止，或者在最后 K 次迭代中种群没有变化。

因此，它可能不会停在最佳解决方案上，而是停在局部最大值上。

一部分人口可以从一次迭代到另一次迭代保持不变，因为它们可能具有良好的适应度函数值。由于突变，也有可能“退回”到以前的基因组。

有很多技巧可以让遗传算法更好地工作：选择合适的种群编码到基因组中，找到一个好的适应度函数，玩交叉和变异比率。

于 2012-09-30T15:05:16.070 回答