TSP遗传算法中的交叉操作
我正试图用遗传算法解决旅行商问题（TSP）
我的基因组是图中顶点的排列（推销员的路径）。
我该怎样对基因组进行交叉操作？
我在哪里可以找到C＃中我的问题的实现？
你应该检查Gokturk Ucoluk的“TSP避免特殊交叉和突变的遗传算法解决方案”。 PDF 在这里 。 它概述了排列的特殊交叉算子，并提出了一种巧妙的排列表示，它可以很好地与标准交叉相结合（即交叉两个排列总是产生两个排列）。
关键的见解是将置换表示为其反转序列，即对于每个元素i ，在a[i]存储多于i的多于i元素在置换中的左边。 与直接表示不同，对a[i]的唯一约束是局部的，即a[i]不能大于N - i 。 这意味着两个有效反演序列的简单交叉总是产生两个有效的反演序列 – 不需要对重复元素进行特殊处理。
而不是使用标准的GA交叉技术（如MusiGenesis所述 ），最好使用有序交叉来解决旅行商问题 。
通常的方法对于TSP来说效果不好，因为适应度函数对进化路线中不同城市的相对位置非常敏感，而不是它们的绝对位置。 例如，如果您访问所有欧洲首都，最短的路线并不取决于您是否访问布拉迪斯拉发1日，2日或9日。 更重要的是，您在访问维也纳之前或之后立即访问它，而不是访问赫尔辛基，雅典和其他6个国家的首都。
当然，正如mjv也指出的那样 ，传统的交叉也会在你的路线中引入重复。 如果父母一方拥有位置2的巴黎而另一方拥有位于第14位的巴黎，则交叉可能会导致一条进化路线两次访问巴黎（并错过另一个城市），另一条进化路线根本不访问巴黎。 有序的交叉遗传算子不会遇到这个问题。 它保留元素并修改排序。
这是针对您所寻找的C＃程序方法。
关于实现交叉的兴趣（或缺乏），这一切都取决于您的实现将使用的特定选择逻辑（和/或评估函数本身，例如，如果它包括对改进速度的评估） 。 在许多情况下， 交叉操作将“从斩波块中拯救”一些在图形区域中有效/最佳但在某些方面“卡在”其他区域的解决方案 。 这并不是说如果整体算法足够缓慢且覆盖了解决方案空间的很大一部分，则可能不会重新发现相同的解决方案，但交叉也可能会增加这些发现（和/或让您陷入困境）另一个当地最小值;-)）
与GA观察者没有直接相关但值得注意的是，GA的原始“终极”实验是由Alderman教授（RSA成名）在GA中进行的最终“终极”实验，他使用了实际的DNA分子[进入C程序 -只是开个玩意儿来解决相关的图形问题，哈密顿图的问题。
编辑 ：在重新阅读问题时，我理解你为什么要问它或者更确切地说为什么你喜欢“不，你不想要交叉”的回复 😉
你的genonme与图表本身直接相关 （没有任何错误， 先验 ），但是这带来了大多数交叉解密不可行的障碍，因为它们可能有重复的节点（访问同一个城市两次或更多）并且缺少节点（未能访问某些城市）……此外，可行的交叉将影响类似的图表，因此可能只是逐步增加搜索，与突然发现的相比…
嗯…然后可能交叉， 在这个特定的实现中将无法帮助算法 （并且确实需要大量的CPU来创建，测试并经常丢弃交叉后代，CPU将更好地用于提供更多的迭代，更慢的冷却速度 ……）。 除非！ 你找到了一种巧妙的交叉操作方式;-)
交叉的目的是通过将新的基因组组合在一起来扩展进化搜索空间。
进化过程所需的唯一真正标准是交叉的产物包含两个亲本的部分并代表有效的基因组。
只有您知道算法的有效性规则，因此只有您可以指定一个可行的交叉方法（除非您想要为您的基因组结构共享validation规则的更多细节）。
以下是我在GA for TSP中所谓的“部分映射交叉”方法的精确实现。
这是一篇论文，它解释了理论上的部分映射交叉，下面是我的代码。
//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; }
当我在大学的第一门课程时，我正在做一些关于各种GA运营商对解决方案融合的影响的计算（大约需要30页）。 我记得，交叉不是TSP的最佳解决方案，更合适的解决方案是突变，它是顶点子序列的反转。
例：
之前： BCDEF GH
之后： FEDCB GH
遗传算法中的“交叉”只是指混合两个“基因序列”的任意方式，每个“基因序列”代表一个问题的特定解决方案（序列如何映射到解决方案取决于您）。 因此，例如，假设您的人口由以下两个序列组成：
AAAAAAAAAA BBBBBBBBBB
重新组合这两个“父”序列的一种方法是随机选择交叉点（例如，位置3），从而产生这两个“子”序列：
AAABBBBBBB BBBAAAAAAA
或者，您可以随机选择两个交叉点（例如，3和8），从而产生以下两个序列：
AAABBBBBAA BBBAAAAABB
为了有趣和额外的变化，您还可以介绍偶尔发生点突变的可能性：
AAABBBABAA BBBAAAAABB
关于如何在遗传算法中实现交叉，实际上并没有任何硬性规则，就像在生物世界中没有任何关于进化论的硬性规则一样。 无论什么有效，都有效。