遗传算法:如何在"子集"问题中进行交叉？

Question

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

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

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

Answer 1

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

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

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