selection - 遗传算法中比赛选择的多次迭代

Question

嘿，伙计们，我对锦标赛选择的多次迭代如何工作感到有些困惑。

我知道您开始选择随机配对（或 k 个成员）并将获胜者放入交配池。你继续这样做，直到交配池被填满。

但是，我不确定之后会发生什么。

我们只是开始在交配池中随机交配吗？然后通过从新一代中选择随机对来重新开始选择过程？

谢谢。

Answer 1

我已经编写了很多这样的通用算法，以至于我创建了一个框架来避免一次又一次地编写相同的代码。

对于交配池，这取决于您正在寻找的个体类型，您正在寻找的解决方案，以及如果您有办法以某种方式将个体组合在一起，那么他们更有可能产生更好的个体。

你可以使用随机交配，但这会给你“更糟糕”的解决方案——更糟糕的是，你不知道它们是否会产生更好的个体。它仍然是很好的解决方案，当我开始编写这些算法时，我总是使用随机交配，但是在从 2 个旧个体中得到一个新个体后，我立即比较了 3 个的性能，并丢弃了最差的，最终得到有时有 2 位父母（并丢弃 1 秒大的孩子），或者以 1 位父母和 1 位孩子告终。

但是为了更高效，并且如果您知道如何组合个体以便他们产生更好的解决方案（这可能非常棘手），您可以使用亲和力函数，它需要 2 个个体并返回他们之间的亲和力。棘手的部分是确定亲和力。根据问题的不同，它可能会有很大的不同。例如，如果我考虑旅行商问题，我在交配相似度较低的个体时得到了最好的解决方案。所以我的亲和力函数返回 1 - 相似度。

这样，我可以将迭代次数减少 80% 并获得非常好的解决方案。

但请记住，池越大，执行亲和函数所需的时间就越长——亲和函数可以是 O(n²)，甚至 O(n³)，在这种情况下，它可能是算法的瓶颈。在这种情况下，最好使用随机交配。

总之，随机交配是好的——毕竟，我们可以说它在现实生活中是这样工作的——但如果你知道如何计算两个人之间的亲和力，你可以用它来减少迭代次数需要得到一个好的解决方案。请记住，计算亲和性可能非常复杂（我什至猜想计算给定池的最佳亲和性是 NP 完全的）。

Answer 2

这不是一个好建议，但是...

但是，我不确定之后会发生什么。

做你想做的。您可以将它们全部变异......或者您可以将您在锦标赛中挑选的每一对配对。使用效果最好的。要有创意。

正如本论坛上的其他人所指出的那样：关于 GA 的肮脏小秘密在于它更像是艺术而不是科学。

此外，要获得真正好的建议，您需要更好地描述您想要解决的问题。

Answer 3

传统上，在找到锦标赛获胜者后，他们会形成下一代。在此之后，所有的变异、选择等过程都在循环中继续进行。