algorithm - 遗传算法 : Crossover for 0-1 Knapsack

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

鉴于此，我们提出了以下位运算符:

1. 相交:s1 和 s2(通常是 &)

2. 差异:s1 XOR s2(通常是^)