TSP遗传算法中的交叉操作

Question

我正在尝试使用 旅行推销员问题 (TSP) ://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">遗传算法。我的基因组是图中顶点的排列（推销员的路径）。

我应该如何对我的基因组进行交叉操作？

在哪里可以找到我的问题的 C# 实现？

Answer 1

您应该检查“避免特殊交叉的 TSP 的遗传算法解决方案和突变”作者：Gokturk Ucoluk。它概述了排列的特殊交叉运算符，并提出了一种与标准交叉配合良好的排列的巧妙表示（即，交叉两个排列总是产生两个排列）。

关键的见解是将排列表示为其反转序列，即对于每个元素i，在a[i]中存储有多少个元素大于i code> 在排列中位于 i 的左侧。与直接表示不同，对a[i]的唯一约束是局部的，即a[i]不能大于N - i。这意味着两个有效反转序列的简单交叉总是产生两个有效反转序列 - 不需要对重复元素进行特殊处理。

Answer 2

而不是使用标准的 GA 交叉技术（如 概述） MusiGenesis），最好使用有序交叉进行旅行推销员问题。

通常的方法对于 TSP 来说效果不太好，因为适应度函数对进化路线中不同城市的相对位置而不是它们的绝对位置非常敏感。例如，如果您要访问所有欧洲国家的首都，那么最短路线并不真正取决于您是否访问第一、第二或第九个布拉迪斯拉发。更重要的是您访问它访问维也纳之前或之后立即而不是访问赫尔辛基、雅典和 6其间的其他首都。

当然，正如 mjv 也指出的，传统的交叉也会在你的路线中引入重复。如果一个父母将巴黎置于位置 2，另一父母将巴黎置于位置 14，则交叉可能会导致一条进化路线访问巴黎两次（并错过另一个城市），而另一条进化路线则根本不访问该城市。有序交叉遗传算子不会遇到这个问题。它保留元素并修改顺序。

Answer 3

这是C# 程序方法，可满足您的需求。

关于实现交叉的兴趣（或缺乏兴趣），这一切都取决于您的实现将使用的特定选择逻辑（和/或评估函数本身，如果例如它包含一个改进速度的评估）。在许多情况下，交叉操作将“从砧板中拯救出来”一些在图表的某个区域中有效/最佳但在其他区域中“卡住”的解决方案。这并不是说，如果整体算法足够慢并且覆盖了解决方案空间的很大一部分，则可能不会重新发现相同的解决方案，但交叉也可能会增加这些发现（和/或让您陷入困境）另一个局部最小值;-) )

与研究 GA 的人不直接相关但值得注意的是 GA 中的原始“终极”实验 Alderman 教授（RSA 出名）在 GA 中的原始“终极”实验，他使用了实际的 DNA 分子 [一个 C 程序 - 开玩笑] 来解决相关的图问题，即哈密尔顿图问题。

编辑：在重新阅读问题时，我理解您为什么问这个问题，或者更准确地说为什么您想要“不，您不想交叉”回复； -)
你的基因组直接与图本身联系在一起（这没有什么问题，先验），但这带来了一个障碍，即大多数交叉offsrpings都不可行，因为它们可能有重复的节点（访问同一城市两次或多次）并且缺少节点（未能访问某些城市）...此外，可行的交叉会影响相似的图，因此与会发现什么突变...
嗯……那么也许交叉，在这个特定的实现中不会对算法有太大帮助（并且确实需要大量的CPU来创建、测试和经常使用）丢弃交叉后代，通过提供更多迭代和较慢的冷却速度可以更好地使用CPU...）。除非！您找到了执行交叉操作的巧妙方法;-)

Answer 4

交叉的目的是通过汇集新的基因组组合来扩展进化搜索空间。

进化过程所需的唯一真正标准是交叉的产物包含父母双方的部分并代表有效的基因组。

只有您知道算法的有效性规则，因此只有您可以指定有效的交叉方法（除非您想分享基因组结构验证规则的更多详细信息）。

Answer 5

这是我在 TSP 的 GA 中对所谓的“部分映射交叉”方法的具体实现。

这里是一篇解释部分映射交叉的论文理论上，下面是我的代码。

//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;
}

Answer 6

当我在大学上第一门课程时，我正在做一些关于各种 GA 算子对解收敛的影响的计算（大约花了 30 页）。我记得交叉并不是TSP的最佳解决方案，更合适的解决方案是变异，即顶点子序列的反转。

示例：

之前：ABCDEFGH

之后：AFEDCBGH

Answer 7

遗传算法中的“交叉”只是指混合两个“遗传序列”的任意方式，每个“遗传序列”代表问题的特定解决方案（序列如何映射到解决方案取决于您）。因此，举例来说，假设您有一个由以下两个序列组成的群体：

AAAAAAAAAA
BBBBBBBBBB

重新组合这两个“父”序列的一种方法是随机选择一个交叉点（例如位置 3），从而产生这两个“子”序列：

AAABBBBBBB
BBBAAAAAAA

或者，您可以随机选择两个交叉点（例如 3 和 8），从而产生这两个序列：

AAABBBBBAA
BBBAAAAABB

为了有趣和额外的可变性，您还可以引入偶尔点突变的可能性：

AAABBBABAA
BBBAAAAABB

实际上没有任何硬性和-关于如何在遗传算法中实现交叉的快速规则，就像生物世界中没有任何严格的规则来管理进化一样。无论什么有效，都有效。