c# - TSP遗传算法中的交叉操作

Question

我正在尝试用遗传算法解决旅行商问题（TSP）。我的基因组是图中顶点的排列（推销员的路径）。

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

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

score 12 · Accepted Answer

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

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

score 8 · Accepted Answer

与其使用标准 GA 交叉技术（如MusiGenesis 所述），不如使用有序交叉来解决旅行推销员问题。

通常的方法不适用于 TSP，因为适应度函数对进化路线中不同城市的相对位置非常敏感，而不是它们的绝对位置。例如，如果您要访问所有欧洲首都，那么最短的路线实际上并不取决于您是访问布拉迪斯拉发 1 号、2 号还是 9 号。更重要的是您在访问维也纳之前或之后立即访问它，而不是访问赫尔辛基、雅典和介于两者之间的其他 6 个首都。

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

score 4 · Accepted Answer

这是您正在寻找的 C# 程序方法。

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

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

编辑：在重新阅读这个问题时，我明白你为什么问它，或者更确切地说，为什么你想要一个“不，你不想交叉”的答复；-)
你的基因组直接与图表本身相关（没有错有了这个，先验的），但这带来了大多数交叉offsrpings将不可行的障碍，因为它们可能有重复的节点（访问同一个城市两次或更多）并且缺少节点（未能访问某些城市）。 ..此外，可行的交叉将影响相似的图，因此与突变会发现的相比，可能只是增加搜索量......
嗯......然后可能会交叉，在这个特定的实现中不会对算法有太大帮助（并且确实占用了它的大部分 CPU 来创建、测试并经常丢弃交叉后代，通过提供更多迭代和更慢的冷却速度可以更好地使用 CPU ……）。除非！您会找到一种执行交叉操作的聪明方法；-)

score 3 · Accepted Answer

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

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

只有你知道你的算法的有效性规则，所以只有你可以指定一个有效的交叉方法（除非你想为你的基因组结构分享更多的验证规则细节）。

score 2 · Accepted Answer

这是我在 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;
}

score 1 · Accepted Answer

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

例子：

之前：BCDEF GH

之后：一个FEDCB GH

score 0 · Accepted Answer

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

AAAAAAAAAA
BBBBBBBBBB

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

AAABBBBBBB
BBBAAAAAAA

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

AAABBBBBAA
BBBAAAAABB

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

AAABBBABAA
BBBAAAAABB

关于如何在遗传算法中实现交叉并没有真正的硬性规则，就像生物世界中的进化没有任何硬性的规则一样。任何工作，工作。

c# - TSP遗传算法中的交叉操作

7 回答 7

Related

Reference