如何在二维数组中执行交叉 - 遗传算法

Question

我有以下两条染色体，表示为一个二维数组。

// First chromosome
[
  [ 12 45 23 ]
  [ 34 01 89 ]
  [ 33 90 82 ]
]

// Second chromosome
[
  [00 45 89 ]
  [00 00 34 ]
]

染色体的限制在于染色体数组中的每个数组必须保持完整。例如，在第一个染色体[ 12 45 23 ]中，该数组必须保持完整。考虑到这一点，我认为在上述染色体结构中进行交叉的方法是随机选择水平交叉点。例如以下内容:

// First produced off-spring
[
  [ 12 45 23 ] // First chromosome
  [ 00 00 34 ] // Second chromosome
]

// Second produced off-spring
[
  [ 00 45 89 ] // Second chromosome
  [ 34 01 89 ] // First chromosome
  [ 33 90 82 ] // First chromosome
]

这是在行必须保持不变的2D染色体数组上执行突变的正确方式吗？ 如果是，这种方法有特定的名称吗？或者这属于“单点”交叉吗？

- Corbuk

---

这非常依赖于你要解决的问题。没有这些信息，很难说。 - Todor Balabanov

Answer 1

这个方法有特定的名称吗？或者它属于单点交叉吗？

在关于可变长度遗传算法的各种论文中，它被称为“单点交叉”。

对于可变长度染色体，通常会更一般地提出单点交叉：您可以为每个染色体选择一个不同的交叉点。例如：

C1 = [ A1, A2, A3, A4, A5, A6]

C2 = [ B1, B2, B3, B4]

选择交叉点 1 作为 C1 的交叉点，选择交叉点 3 作为 C2 的交叉点，您将得到：

C1 = [ A1 | A2, A3, A4, A5, A6]

C2 = [ B1, B2, B3 | B4]


C1' = [A1 B4]
C2' = [B1, B2, B3, A2, A3, A4, A5, A6]

这使染色体长度开始增长。根据具体问题，这可能是一个要求或仅仅是膨胀（在这两种情况下，您可能需要在适应度函数中考虑这一点）。

“这是对必须保持行完整性的2D染色体数组执行突变的正确方法吗？”

这是一个简单的方法（所以是一个好方法）。均匀交叉是另一种简单的方法。 可变长度基因组有意义的交叉：可变长度交叉的意义（本杰明·哈特和凯文·沃里克，IEEE进化计算期刊，第11卷，第1期，2007年2月）描述了其他有趣（更复杂）的可能性。

最好的交叉方法非常特定于问题。

- manlio