当染色体中的基因不唯一时，如何在 GA 中应用顺序交叉？

Question

在遗传算法 (GA) 中，顺序交叉 (OX) 通常适用于具有独特基因的染色体。根据此 paper，OX 使用以下指令应用于看起来像这样 {3, 1, 2, 1, 1} 的染色体：

(a) Randomly choose two cut-off points in the string.

(b) Copy the elements of the first parent that are found between the two
    cutoff points in the first offspring.

(c) Copy the elements that still have not been included in the first offspring
    as follows:

    (c.1) Start from the second cutoff point of the second parent.

    (c.2) Copy the elements not included in the first offspring, respecting
          the order in which the elements appear in the second parent.

    (c.3) Once the list of the second parent is finished, continue with the
          first elements (as in a circular arrangement).

(d) The second offspring is created in a similar way (steps b and c), inverting
    the role of the parents.

本文讨论的问题是广义最小生成树问题 (GMSTP)，其中图被划分为顶点簇，每个簇中仅需要一个顶点构造 MST。论文中染色体中的每一个元素代表一个簇，元素的每一个值都是簇中选择的节点来构建GMST。

OX 保留了父代 2 中的基因顺序。这可以在例如在使用 GA 解决旅行商问题 (TSP) 时，其中染色体的每个值代表一个节点（一个城市）。但是，当谈到 GMSTP 时，我对它很模糊，因为集群的顺序总是相同的。

[编辑]

OX 示例：

Parent1 = { 1 2 3 4 5 6 7 8 9 }
Parent2 = { 3 2 8 1 4 9 6 5 7 }

after 2 random cut-off points

Parent1: { 1 2 | 3 4 5 6 | 7 8 9 }
Parent2: { 3 2 | 8 1 4 9 | 6 5 7 }

Copy genes between the two cut-off points of the 1st parent
Child1:  { x x | 3 4 5 6 | x x x }

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point,
excluding genes already in the child as well as preserving order 
Child1:  { 1 9 | 3 4 5 6 | 7 2 8 }

(Do the same for Child2 swapping the parents)

现在，尝试在这组基因上应用 OX：

Parent1: { 3 1 2 1 1 }
Parent2: { 3 2 2 1 4 }

I do not see a way of doing that, however, researchers said they used OX here.

Answer 1

在此类染色体上实施 OX 的一种方法是照常进行，如果遇到缺失元素，则复制原始元素（来自第一作者对我的问题的回答）。

用新指令解决问题中的例子如下：

Parent1 = { 3 1 2 1 1 }
Parent2 = { 3 2 2 1 4 }

after 2 random cut-off points

Parent1: { 3 | 1 2 | 1 1 }
Parent2: { 3 | 2 2 | 1 4 }

Copy genes between the two cut-off points of the 1st parent
Child1:  { x | 1 2 | x x }

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point,
excluding genes already in the child as well as preserving order 
Child1:  { x | 1 2 | 4 3 }

Copy original values to the missing elements
child1:  { 3 | 1 2 | 4 3 }

The same for Child2 swapping the rules of the parents
child2:  { 3 | 2 2 | 1 3 }

当染色体中的基因不唯一时，如何在 GA 中应用顺序交叉？

How do I apply order crossover in GA when genes in chromosomes are not unique?

genetic-algorithm