遗传算法：0-1背包的交叉

Question

我正在按照遗传算法方法解决背包问题 here。我知道他们使用了直接值编码方案而不是二进制表示。交叉函数如下：

def cxSet(ind1, ind2):
"""Apply a crossover operation on input sets. The first child is the
intersection of the two sets, the second child is the difference of the
two sets.
"""
temp = set(ind1)                # Used in order to keep type
ind1 &= ind2                    # Intersection (inplace)
ind2 ^= temp                    # Symmetric Difference (inplace)
return ind1, ind2

如果我将背包问题的染色体编码为二进制表示，则交集将是一个 AND 运算。集合差异的类似操作是什么？

此外，我只是想知道这种交叉背后的基本原理是什么，以及这种交叉是否比其他常用交叉技术（如单点交叉或两点交叉）有优势。

Answer 1

解决此类事情最简单的方法就是做一个小例子：

s1 = {1, 2, 3, 4} => 11110000
s2 = {3, 4, 5, 6} => 00111100
s1 intersect s2 = {3, 4} => 00110000
s1 difference s2 = {1, 2, 5, 6} => 11001100

由此我们得出以下位运算符：

相交：s1 和 s2（通常 &）
区别：s1异或s2（通常^）

遗传算法：0-1背包的交叉

Genetic Algorithm: Crossover for 0-1 Knapsack

algorithm

knapsack-problem

crossover