遗传算法:如何对独特元素的有序集合进行交叉？

Question

这个问题建立在another one的基础上。

我们如何有效地在由独特元素的有序集合形成的染色体上实现交叉操作？

两个这样的双亲染色体是{'a','b','c','d'}和{'e','f','a','b'}；而这些双亲的两个可能的子染色体是{'e','f','c','d'}和{'a','f','c','b'}。

Answer 1

你可以尝试一种统一的交叉。

通常，Uniform Crossover在两个亲本之间使用固定的混合比例，操作者评估亲本染色体中的每个基因，以0.5的概率进行交换。

使用Python语法：

import random

p = [['a','b','c','d'], ['e','f','a','b']]    # parents

for i in range(len(p[0])):
   offspring.append(p[random.randint(0, 1)][i])

​

​

给定唯一性约束，必须修改基本方案：

import random

p = [['a','b','c','d'], ['e','f','a','b']]    # parents

for i in range(len(p[0])):
    if p[1][i] in p[0]:    # cannot risk crossover, keep basic gene
        offspring.append(p[0][i])
    else:                  # standard uniform crossover
        offspring.append(p[random.randint(0, 1)][i])

约束被“自动”满足，并且您有了一个更小的搜索空间。

注意，交叉在某种程度上绑定到第一个父代(p[0])，并且我们得到了有限数量的变体：

CHROMOSOME FREQUENCY
abcd       *************************
efcd       ************************
ebcd       ************************
afcd       ************************

在这方面，一个小的改进是：

if p[1][i] in offspring or p[1][i] in p[0][i:]:
    offspring.append(p[0][i])
else:
    offspring.append(p[random.randint(0, 1)][i])

和

CHROMOSOME FREQUENCY
efcd       ******
afcd       ************
efad       ******
ebcd       ************
efcb       ******
efab       ******
ebad       ************
abcd       *************************
afcb       ************

但是这个“诀窍”只对一些父母有效。例如，交换父母：

p = [['e','f','a','b'], ['a','b','c','d']]

你又有了：

CHROMOSOME FREQUENCY
efcd       *************************
efcb       ************************
efad       *************************
efab       ************************

edge recombination operator是另一种可能性：

ERO通过查看边而不是顶点来创建类似于一组现有路径(父路径)的路径。它的主要应用是用于遗传算法中的交叉，当需要具有非重复基因序列的基因型时，例如用于旅行推销员问题。

(不确定这是你的情况)

Answer 2

是。那是个十字架。就这么做吧。假设元素在同一位置，只要您通过选择一个点进行交叉，然后在该点之后交换数组，您就不会重复元素。

但是，这是一种遗传算法，如果你制造了错误的东西，它无论如何都应该消失，所以你不必担心保持某种强制的纯度。无论如何，它只是解决了适应度函数的改进问题。

Answer 3

最简单的解决方案是选择一个介于0和父母长度之间的随机指数。让我们将该索引命名为n。

然后只需将第一个父元素的前n个元素放在子元素中，然后是第二个父元素的其余长度-n个元素。

在这里查看我是如何实现crossover方法的：

https://github.com/amihaiemil/eva/blob/master/src/main/java/com/amihaiemil/eva/util/BinaryArraySolution.java

还有一个“交叉概率”，它基本上是一个介于0和1之间的随机数，它决定了父母是否有孩子。如果它们不能有孩子，则返回两个中最好的一个。