algorithm - 遗传算法 : How to do crossover in "subset" problems?

Question

我有一个问题想用遗传算法解决。问题是选择 100 个整数的某个子集(比如 4)(这些整数只是代表其他东西的 id)。顺序无关紧要，问题的解决方案是一组整数而不是有序列表。我的适应度函数很好，但在交叉函数方面遇到了问题。

我希望能够使以下两条染色体交配:

[1 2 3 4] 和[3 4 5 6] 变成有用的东西。显然我不能使用典型的交叉函数，因为我最终可能会在我的 child 中得到重复项，这将代表无效的解决方案。在这种情况下最好的交叉方法是什么。

Answer 1

只需忽略出现在两个 集合中的任何元素(即在它们的交集中)，即在两个集合中保持这些元素不变。

其余元素形成两个不相交的集合，您可以对其应用几乎任何随机变换(例如，随机交换一些对)而不会重复。

这可以被认为是对两个集合进行排序和对齐，以便匹配元素彼此面对并应用一种标准交叉算法。