排列交叉算子（遺傳算法）問題，當沒有1對1的映射

Question

這不是家庭作業，純粹是爲了我的項目。

我正在實施用於遺傳算法的排列交叉算子（解決旅行推銷員，其中每個數字代表城市指數），並且當沒有1比1的邊界情況時，我遇到了一些問題映射。

考慮下面的兩個基因組，並假設最後兩個條目被切換。因此，5被映射到6，而6被映射到7.因此，當我點擊數字6時會發生什麼 - 我應該將其更改爲5還是7，並且這可能導致城市被訪問兩次的無效巡視。

//initial case 
GenomeA: [ 2, 3, 1, 4, 0, 7, 5, 6 ] 
GenomeB: [ 1, 2, 0, 3, 4, 5, 6, 7 ] 

5 <--> 6 
6 <--> 7 

//after mapping 
GenomeA: [ 2, 3, 1, 4, 0, 6, 6, 7 ] 
GenomeB: [ 1, 2, 0, 3, 4, 6, 5, 6 ] 

我應該隨機選擇其他號碼，如果號碼已被映射？或者我不應該切換任何已經映射的數字嗎？

例如，

a) Evaluate first set of numbers (5 <--> 6) 
b) Since 5 has not been mapped, map 5 to 6 and vice versa 
c) Evaluate second set of numbers (6 <--> 7) 
d) Since 6 is already mapped to 7, ignore this set of numbers 

Answer 1

我發現一種簡單的方法，以產生在多個映射的情況下，合法的後代（5 < - > 6 < - > 7）。

a) First check if any number outside the substring exchanged ("originalNumber" is contained within the mapping 
b) Let the mapped value of "originaNumber" be called "replacement" 
c) Check if "replacement" is also contained within the mapping (if it is, this implies that there will be a clash if we set "originalNumber" to "replacement") If it isn't, simply set "originalNumber" to "replacement" 
d) Otherwise, find the mapped value of "replacement" and set "originalNumber" to it.