python - 使用部分匹配交叉进行遗传算法时处理重复项

Question

我是遗传算法的新手，正在研究 python 实现。我已完成交叉步骤并尝试部分匹配交叉。对于我的最终输出，我希望得到一个不包含重复数字的列表。然而，在某些情况下，我会引入重复项。 例如，获取列表

配合 1 [1,2,3,5,4,6]

伴侣 2 [6,5,4,3,2,1]

如果交叉部分是[3,5,4] -> [4,3,2]

那么映射前的后代就变成了[1,2,4,3,2,6]。我对该算法的理解是交叉外的映射是4 -> 3、5 -> 3 和2 -> 4。但是，这会导致 [1,4,4,3,2,6] 的输出有重复项并且缺少 5。

如何解决这个问题？前4会变成5吗？这将如何扩展到可能引入多个重复项的更大列表？

Answer 1

我不确定您是否正确实现:

对于部分匹配交叉( see explanation )，如果您的交叉点是示例中建议的 2 和 5，那么您只能获得

offspring1 = [6, 2, 3, 5, 4, 1]
offspring2 = [1, 5, 4, 3, 2, 6]

如果您从 mate1 中选择 3,5,4 并按照 mate2 的顺序填充其余部分，您将得到后代 1，但如果您选择 4,3,2从 mate2 开始，按照 mate 1 的顺序填写其余部分，你将得到后代 2

请参阅下面的实现:

mate1 = [1,2,3,5,4,6]
mate2 = [6,5,4,3,2,1]


crossoverpoint1 = 2
crossoverpoint2=5
child = []

#fill in the initial genes in order of mate1
count = 0
for i in mate1:
    if(count == crossoverpoint1):
        break
    if(i not in mate2[crossoverpoint1:crossoverpoint2]):
        child.append(i)
        count= count+1

#select the genes within the crossover points from mate2          
child.extend(mate2[crossoverpoint1:crossoverpoint2])

#fill in the remaining genes in order of mate1
child.extend([x for x in mate1 if x not in child])

print(child)

输出:

[1, 5, 4, 3, 2, 6]

获得offspring1，将mate1交换为mate2。 您还可以尝试不同的交叉点，如果有帮助请告诉我