13

我正在尝试解决我的排列中遗传算法中的交叉问题。假设我有两个 20 个整数的排列。我想交叉他们生两个孩子。父母内部有相同的整数，但顺序不同。

例子：

Parent1: 
 5 12 60 50 42 21 530 999 112 234 15 152 601 750 442 221 30 969 113 134
Parent2: 
 12 750 42 113 530 112 5 23415 60 152 601 999 442 221 50 30 969  134 21

就这样吧——我怎样才能得到这两个孩子？

4

4 回答 4

5

您正在寻找的是有序交叉。这里有关于旅行商问题的解释。

下面是一些实现部分映射交叉 (PMX) 变体的Java 代码。

于 2013-01-20T01:42:54.173 回答
4

交叉的选择取决于整数的顺序或绝对位置对适应度是否重要。在HeuristicLab (C#) 中，我们实现了文献中的几个流行的，包括：OrderCrossover（2 个变体）、OrderBasedCrossover、PartiallyMatchedCrossover、CyclicCrossover（2 个变体）、EdgeRecombinationCrossover (ERX)、MaximalPreservativeCrossover、PositionBasedCrossover 和 UniformLikeCrossover。它们的实现可以参考 HeuristicLab.Encodings.PermutationEncoding 插件中的科学资源一起找到。ERX 仅对 TSP 或类似 TSP 的问题有意义。CX 是基于位置的，PMX 部分是位置部分是基于顺序的，但更倾向于位置。OX 完全基于订单。

请注意，我们的实现假设具有从 0 到 N-1 的整数的连续编号排列。您必须首先将它们映射到此范围。

于 2013-01-20T09:31:28.700 回答
2

根据我对遗传算子的研究和实现。许多类型的交叉运算符用于顺序编码（即不允许重复基因，如在TSP中）。总的来说，我喜欢认为有两个主要的家庭：

ERX 系列

邻域列表用于存储双亲中每个节点的邻居。然后，仅使用列表生成孩子。众所周知，ERX更尊重和等位基因传递，这基本上意味着基因之间的联系不太可能被打破。

类 ERX 算子的示例包括：边缘重组 (ERX)、边缘 2、边缘 3、边缘 4 和广义分区交叉 (GPX)。

类似 OX 的分频器

选择了两个交叉点。然后，点之间的基因在两个父母之间交换。由于不允许重复，因此每个交叉都提出了一种避免/消除重复的技术。这些交叉运营商比 ERX 更具破坏性。

类 OX 交叉的示例：阶交叉 (OX)、最大防腐交叉 (MPX) 和部分映射交叉 (PMX)。

第一族（ERX）在普通遗传算法中表现更好。而第二类更适合混合遗传算法或模因算法（使用局部搜索）。这篇论文详细解释了它。

于 2016-03-20T00:16:27.100 回答
1

在旅行销售代表问题 (TSP) 中，您希望订单访问城市列表，并且您希望每个城市仅访问一次。如果您直接在基因组中对城市进行编码，那么简单的交叉或突变通常会生成无效的行程。

我曾经想出一种解决这个问题的新方法：我没有直接在基因组中编码解决方案，而是编码了一个可以重新排序规范值列表的转换。

给定基因组 [1, 2, 4, 3, 2, 4, 1, 3]，您将从任意顺序的城市列表开始，比如按字母顺序：

  1. 亚特兰大
  2. 波士顿
  3. 芝加哥
  4. 丹佛

然后，您将从基因组中获取每对值并交换这些位置的城市。因此，对于上面的基因组，您将交换 1 和 2 中的那些，然后是 4 和 3 中的那些，然后是 2 和 4 中的那些，最后是 1 和 3 中的那些。您最终会得到：

  1. 丹佛
  2. 芝加哥
  3. 波士顿
  4. 亚特兰大

使用这种技术，您可以使用任何类型的交叉或变异操作，并且仍然始终获得有效的游览。如果基因组足够长，则可以探索整个解决方案空间。

我已经将它用于 TSP 和其他优化问题，并取得了很大的成功。

于 2016-02-16T16:58:21.310 回答