genetic-algorithm - 为什么遗传算法不能解决像 RSA 因式分解这样的问题？

Question

前段时间我对 GA 非常感兴趣，我对它们进行了相当多的研究。我使用 C++ GAlib 编写了一些程序，我对它们在几秒钟内解决其他难以计算的问题的能力感到非常惊讶。它们似乎是一种很棒的蛮力技术，它的工作方式非常智能且适应性强。

我正在读 Michalewitz 的一本书，如果我没记错名字的话，它似乎都是基于 MIT 证明的模式定理。

我还听说它不能真正用于解决诸如分解 RSA 私钥之类的问题。

有人可以解释为什么会这样吗？

Answer 1

遗传算法一点也不聪明，它们是非常贪婪的优化器算法。他们都围绕着同一个想法工作。你有一组点('一群人')，你用随机算子将这个组转换成另一个组，偏向于最佳改进的方向('变异+交叉+选择')。重复直到它收敛或者你厌倦了，那里没有什么聪明的。

要使遗传算法发挥作用，新的点群的表现应该接近于之前的点群。很少的扰动应该不会产生什么变化。如果在对一个点进行小幅扰动后，您得到一个表示性能完全不同的解的点，那么该算法无异于随机搜索，这是一种通常不是很好的优化算法。在 RSA 的情况下，如果您的点直接是数字，则是 YES 或 NO，只需稍微翻转...代码搜索点作为数字的位"