當染色體中的基因不唯一時，如何在遺傳算法中應用交叉排序？

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 }