将部分匹配交叉用于遗传算法时处理重复项

Question

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

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

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

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

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

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

Answer 1

我不确定你是否正确实施：

for Partially Matched Crossover (see explanation)，如果你的交叉点是2和5，那么你只能得到

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

如果你从 mate1 select 3,5,4 并按照 mate2 的顺序填充其余部分，你将得到后代 1 但如果你从 mate2 select 4,3,2 并填充其余的按照配偶 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。您也可以尝试不同的交叉点，如果有帮助请告诉我

将部分匹配交叉用于遗传算法时处理重复项

Handling duplicates when using Partially Matched Crossover for Genetic Algorithm

python

optimization

genetic-algorithm

evolutionary-algorithm