algorithm - 只有选择和变异的遗传算法与爬山算法有何相同之处？

Question

考虑一个仅使用选择和变异（无交叉）的遗传算法。这与爬山算法有何相似之处？

我在一篇文章中找到了这个说法，但我似乎不明白为什么？

Answer 1

这种说法是有风险的，很难看到。我相信许多人不一定（或完全）同意它。

可能是真的情况

相信这句话的作者想说的是，可以只用变异和选择来实现爬山算法。

想象一下，您的染色体 (X) 的每个突变都可以提高或降低您的适应度函数 (Y) 的值（想象它是身高）。我们想找到 Y 最大的 X。

1. 我们将染色体 (X) 放入池中
2. 我们突变染色体（X）并寻找（Y）的改进。
3. 突变后仅选择产生最高 (Y) 的染色体并重复步骤 1-2 20 次。

因为在每个阶段你都在拒绝糟糕的值——你将能够获得（几乎）Y 的最大值。

我想这就是作者想要表达的意思。

可能是假的情况

当突变在很大程度上影响染色体时 - 算法不会轻易收敛到最大值。这是当染色体中的太多基因在每次突变时受到影响时；

当突变后的染色体与其原始基因组不相似时 - 你只是在引入噪音。在效果上，它有点像使用 (X) 的随机生成器来找到最大值 (Y)。每次你变异 (X) 时，你都会得到一些与原来无关的东西。您可能会找到最大价值，但这与爬山无关。

Answer 2

没有交叉的爬山算法和遗传算法都是局部搜索技术。从这个意义上说，它们是相似的，但我不会说它们是相同的。

爬山有不同的形式，但都有一些遗传算法没有的属性：

• 有一个定义明确的邻居函数（给定一种解决方案可以枚举所有邻居）
• 除非取消，只要发现改进，算法就会继续（而不是在固定的代数之后）
• 在迭代期间，只有一个解决方案（不是解决方案池）

在实践中，选择一个好的邻居函数会对爬山算法的有效性产生巨大影响。在这里，您有时可以使用额外的领域知识。

据我所知，在遗传算法中，领域知识不用于变异器。大多数情况下，他们使用简单的技术，例如翻转位或向数字添加随机噪声。

爬山可以作为一种没有任何随机性的确定性算法很好地工作。根据您的问题，这可能是关键属性，也可能不是。如果不是，那么随机重启爬山通常会带来更好的结果。

总之，如果你使用没有交叉的遗传算法，你最终会得到一个相当糟糕的局部搜索算法。我希望一个好的爬山算法能够胜过它，特别是在你处于严格时间限制（实时系统）的情况下。