algorithm - 遗传算法，无重复数据交叉

Question

我正在创建一个遗传算法，但刚好遇到一个问题，让我们举个例子。我有一个数字列表:[2, 3, 6, 8, 9, 1, 4] 代表我的数据。我的问题的最佳解决方案取决于列表中数字的顺序。所以我有两个解决方案:S1 [2, 3, 9, 8, 1, 6, 4] 和 S2 [1, 6, 4, 3, 9, 2, 8]

如果我对 S1 和 S2 进行基本交叉，我可能会得到这样的解决方案:child [2, 3, 9, 8, 9, 2, 8] 我们可以看到该解决方案很糟糕，因为我复制数据。

问题是我如何在没有重复这些数据的情况下实现进化(如此交叉)？

谢谢。

Answer 1

您将需要一个交叉运算符，例如 Ordered Crossover (OX1)可以在没有重复数据的情况下执行交叉:

OX1: A randomly selected portion of one parent is mapped to a portion of the other parent. From the replaced portion on, the rest is filled up by the remaining genes, where already present genes are omitted and the order is preserved.

你也应该注意突变，因为它可以改 rebase 因顺序，在这种情况下你可以使用像 Reverse Sequence Mutation (RSM) 这样的突变运算符。 .

In the reverse sequence mutation operator, we take a sequence S limited by two positions i and j randomly chosen, such that i<j. The gene order in this sequence will be reversed by the same way as what has been covered in the previous operation.