当染色体中的基因不唯一时，如何在遗传算法中应用交叉排序？

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：实现这种染色体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

的一种方法是按照正常进行，如果遇到元素丢失，请复制原始元素（来自第一作者对我问题的回复）。

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

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 }