1

这个问题建立在另一个问题之上。

我们如何有效地对由唯一元素的有序集合形成的染色体进行交叉操作？

两个这样的亲本染色体将是{'a','b','c','d'}和{'e','f','a','b'}; 并且这些父母的两个可能的子染色体是{'e','f','c','d'}和{'a','f','c','b'}。

4

3 回答 3

2

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

一般来说，均匀交叉使用两个亲本之间的固定混合比，操作员评估亲本染色体中的每个基因以进行交换，概率为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       ************************

边缘重组算子是另一种可能性：

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

（不确定是你的情况）

于 2016-03-08T09:06:51.547 回答
1

是的。那是一个交叉点。去做。假设元素位于同一个位置，只要您通过选择一个点然后交换超出该点的数组进行交叉，您就不会复制元素。

但是，那它是一种遗传算法，不管你做错了什么，它无论如何都会消失，所以你不必担心保持某种强制的纯洁性。无论如何，它只会解决适应度函数的改进。

于 2016-03-08T07:19:51.153 回答
0

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

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

看看我是如何在这里实现交叉方法的：

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

还涉及一个“交叉概率”，基本上是 0 到 1 之间的随机数，这表明父母是否有孩子。如果他们不能生孩子，则返回 2 个中最好的一个。

于 2016-04-28T11:42:15.193 回答