遗传算法中的交叉操作在TSP问题中的应用
关键洞见是将排列表示为其反演序列，即对于每个元素，在
a[i]中存储有多少个大于的元素在排列中左边。与直接表示不同，a[i]上的唯一约束是局部的，即a[i]不能大于N-i。这意味着两个有效的反演序列的简单交叉始终会产生两个有效的反演序列-无需特殊处理重复元素。与MusiGenesis所述的标准GA交叉技术不同，对于旅行商问题，最好使用有序交叉技术。
通常的方法对于TSP并不奏效，因为适应度函数对演化路线中不同城市的相对位置非常敏感，而不是它们的绝对位置。例如，如果您要访问所有欧洲首都，最短的路线实际上并不取决于您首先、第二或第九次访问布拉迪斯拉发。更重要的是，在访问赫尔辛基、雅典和其他6个首都之间，您是在立即访问维也纳之前或之后访问它，而不是在这些首都之间进行游览。
当然，正如mjv也指出的那样，传统的交叉操作也会在您的路线中引入重复。如果一个父母将巴黎放在第2个位置，而另一个父母将巴黎放在第14个位置，交叉可能会导致一个进化路线两次访问巴黎（并错过另一个城市），而另一个进化路线则根本不访问它。有序交叉遗传算子不会遇到这个问题。它保留元素并修改排序。
这里有一个关于你所寻找的内容的C#程序方法。
关于实现交叉的兴趣（或缺乏兴趣），它完全取决于您的实现将使用的特定选择逻辑（和/或评估函数本身，例如它是否包括对改进速度的评估）。在许多情况下，交叉操作将“从砧板上解救出”一些在图形的某个区域中有效/最优但在其他方面“卡住”的解决方案。这并不是说如果整体算法足够慢且涵盖了解决方案空间的很大比例，同样的解决方案可能不会被重新发现，但是交叉也可能增加这些发现（和/或让您陷入另一个局部最小值;-)）
虽然不是直接相关的，但对于任何研究GA的人来说都值得注意的是GA的原始“终极”实验，由RSA著名的Alderman教授进行，他使用实际的DNA分子[转换成C程序 - 只是开玩笑]解决了一个相关的图问题，即哈密顿图。
编辑：再次阅读问题，我明白你为什么提出了这个问题，或者更准确地说，你想要得到“不需要交叉”回答的原因。你的基因组直接与图形相关联（a priori，这没有什么问题），但这会导致大多数交叉后代无法生存，因为它们可能具有重复节点（两次或更多访问同一城市）和缺少节点（未能访问某些城市）......此外，可行的交叉将影响类似的图形，因此可能仅仅是增加搜索的增量，而相比之下，突变可以发现更多的结果......嗯......那么也许在这种特定的实现方式中，交叉并不能帮助算法很多（实际上占用了其大部分CPU来创建、测试和丢弃交叉后代，而这些CPU最好用于提供更多的迭代和更慢的冷却速率...）。除非！你找到了一种聪明的方法来执行交叉操作；-）
交叉的目的是通过组合新的基因组合来扩大进化搜索空间。
进化过程所需的唯一真正标准是交叉的产物包含两个父代的部分，并且表示一个有效的基因组。
只有您知道算法的有效性规则，因此只有您可以指定适用的交叉方法（除非您想分享更多有关基因组结构验证规则的细节）。
2
这篇论文详细解释了部分映射交叉的理论，下面是我的代码。
//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
int[] genes = new int[father.Genes.Length];
int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
father.Genes.CopyTo(genes, 0); //give child all genes from the father
for (int i = 0; i < genes.Length; i++) //create the map
{
map[genes[i]] = i;
}
//int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
{
int temp = crossoverPoint1;
crossoverPoint1 = crossoverPoint2;
crossoverPoint2 = temp;
}
//Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
{
int value = mother.Genes[i];
int t = genes[map[value]]; //swap the genes in the child
genes[map[value]] = genes[i];
genes[i] = t;
t = map[genes[map[value]]]; //swap the indices in the map
map[genes[map[value]]] = map[genes[i]];
map[genes[i]] = t;
}
Individual child = new Individual(genes);
return child;
}
当我在大学上第一门课程时，我在进行一些计算（大约30页）来研究各种遗传算法操作符对解决方案收敛的影响。我记得，对于TSP问题，交叉不是最好的解决方案，更适合的解决方案是变异，即反转子序列顶点。
例如:
之前: ABCDEFGH
之后: AFEDCBGH
2
AAAAAAAAAA
BBBBBBBBBB
重新组合这两个“父”序列的一种方法是随机选择一个交叉点（比如位置3），得到这两个“子”序列：
AAABBBBBBB
BBBAAAAAAA
或者，您可以随机选择两个交叉点（比如3和8），得到这两个序列：
AAABBBBBAA
BBBAAAAABB
为了增加趣味性和变异性，您还可以引入偶发点突变的可能性：
AAABBBABAA
BBBAAAAABB
在遗传算法中，实现交叉的方式并没有硬性规定，就像生物世界中的进化一样，并没有真正的硬性规则。只要有效果，就可以使用。
2
原文链接