7

我目前正在尝试实现一个非常简单的遗传算法示例。

有一次，你必须用两个数字（父母）做一个“交叉”（生物学）才能得到一个“孩子”。

你可以在这里找到 CrossOver 的解释：

如何“交叉”两个字符串（1234 & abcd -> 12cd & ab34）

（第二个插图，更简单的“单点”交叉是我想要做的。）

染色体（父母和孩子）是数字，但“交叉”将是一个位操作。

我找到了一个“染色体”的解决方案，如下所示：

  • 将位 X 向右移动（>>>运算符）
  • 然后将位再次移动 X 位置，但这次向左移动（<<运算符）

所以这将保留一条染色体的末端，并用 0 填充开头。

但我真的不知道如何解决另一条染色体的问题，然后也做交叉。

（一旦我保留染色体的开头/结尾并用 0 填充其余部分，可能是 XOR。）

或者我什至应该从另一个角度解决这个问题？

4

2 回答 2

4

如果交叉的分数是 p（例如，p = .25），那么这应该有效：

mask1 = ((0xffff >> 16*p) << 16*p)
mask2 = 0xffff ^ mask1
output1 = (input1 & mask1) ^ (input2 & mask2)
output2 = (input1 & mask2) ^ (input2 & mask1)

几点注意事项：

  • 这只是伪代码。你可能想要一些演员表。
  • 这对 p 的处理与您在上面的评论中对它的处理不同。（只需将 p 替换为 1-p 即可得到您对 p 的定义。）
于 2012-07-29T01:11:24.740 回答
1

一种天真的方法是使用 4 个局部变量：

int chromatid1Start;
int chromatid1End;
int chromatid2Start;
int chromatid2End;

然后，将输入分配给chromatid1前两个变量和chromatid2后两个变量。

chromatid1Start = chromatid1;
chromatid1End = chromatid1;
chromatid2Start = chromatid2;
chromatid2End = chromatid2;

对染色单体变量执行右移Start直到交叉点，然后左移完全相同的量。在End染色单体变量上，左移到交叉点，然后右移完全相同的量。

chromatid1Start = (chromatid1Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid1End = (chromatid1End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);
chromatid2Start = (chromatid2Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid2End = (chromatid2End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);

这样，您可以将一个的开头与另一个的结尾交叉：

int daughterChromatid1 = chromatid1Start + chromatid2End;
int daughterChromatid2 = chromatid2Start + chromatid1End;
于 2012-07-29T01:16:10.873 回答