algorithm - 遗传算法：如何在“子集”问题中进行交叉？

Question

我有一个问题，我试图用遗传算法来解决。问题是选择 100 个整数的某个子集（比如 4 个）（这些整数只是代表其他东西的 id）。顺序无关紧要，问题的解决方案是一组整数而不是有序列表。我有一个很好的健身功能，但在交叉功能方面遇到了麻烦。

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

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

Answer 1

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

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

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

Answer 2

有时让您的解决方案“越界”是有益的，这样您的搜索将更快地收敛。与其让一组 4 个唯一整数成为您的染色体的要求，不如让整数的数量（及其唯一性）成为适应度函数的一部分。

Answer 3

由于顺序无关紧要，只需将所有数字收集到一个数组中，对数组进行排序，丢弃重复项（通过将它们与链表断开连接，或将它们设置为负数，或其他方式）。随机排列数组并取前 4 个数字。

Answer 4

我真的不知道您对“典型交叉”的意思是什么，但我认为您可以使用类似于通常用于排列的交叉：

• 从第一个父项中获取m个整数（ m < n，其中 n 是集合中的整数个数）
• 扫描第二个并用（nm）空闲的整数填充您的子集（不在子集中）。

这样，您将拥有来自第一个父级的n 个整数和来自第二个父级的nm个整数，而不会重复。

对我来说听起来像是一个有效的交叉:-)。

我想不在有序集合上执行任何步骤（或使用迭代器，其中返回元素的顺序与整数的自然排序以某种方式相关）可能是有益的，否则更小或更大的数字将有更高的机会进入孩子使您的搜索有偏见。

如果它是最好的方法取决于你要解决的问题......

Answer 5

为了组合集合 A 和 B，您可以选择结果集合 S交集并包含在并集中，并且将具有预期的基数 4。