排列交叉算子（遗传算法）问题，当没有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.