遺傳算法：交叉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 

如果我要編碼揹包問題的二進制表示的染色體，inersection將是一個與運算。設定差異的分期手術會是什麼？此外，我只是想知道這種類型的交叉可能是什麼原因，如果這種類型的交叉與其他常見的交叉技術如單點交叉或雙點交叉有優勢。

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（通常^）